FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
How to solve linear program with matrix variable ?
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Fan
science forum beginner


Joined: 31 Dec 2005
Posts: 7

PostPosted: Thu Jul 13, 2006 5:55 am    Post subject: How to solve linear program with matrix variable ? Reply with quote

Hi,

I am facing a problem to solve an LP with matrix variable, not vectors.


Can anybody give me some hint or references?

The problem is like,

min_X c' * (XA - AX) * 1
s.t. X>=0, BX >= C

where c and 1 are vectors, while A,B,C and X are matrices.

Thanks very very much.


Fan
Back to top
Torsten Hennig
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 136

PostPosted: Thu Jul 13, 2006 6:56 am    Post subject: Re: How to solve linear program with matrix variable ? Reply with quote

Quote:
Hi,

I am facing a problem to solve an LP with matrix >variable, not vectors.


Can anybody give me some hint or references?

The problem is like,

min_X c' * (XA - AX) * 1


multiplying out, this gives a scalar expression in the
matrix entries x_ij of the matrix X, so no problem

Quote:

s.t. X>=0, BX >= C

most probably, the >= is meant componentwise for the
matrix entries, i.e. (X)_ij >=0, (BX)_ij >= (C)_ij.
So if X,B and C are (nxn) matrices, you get a
total of 2*n^2 constraints (n^2 from X>=0 and
n^2 from BX>=C)

Quote:
where c and 1 are vectors, while A,B,C and X are >matrices.

Thanks very very much.


Fan
Back to top
Fan
science forum beginner


Joined: 31 Dec 2005
Posts: 7

PostPosted: Fri Jul 14, 2006 12:10 am    Post subject: Re: How to solve linear program with matrix variable ? Reply with quote

The problem is that I am using Matlab. The LP solver in Matlab can
only take the form like

min c'x
s.t. Ax<=b

How can I solve this in Matlab?

Thanks again.

Torsten Hennig wrote:
Quote:
Hi,

I am facing a problem to solve an LP with matrix >variable, not vectors.


Can anybody give me some hint or references?

The problem is like,

min_X c' * (XA - AX) * 1


multiplying out, this gives a scalar expression in the
matrix entries x_ij of the matrix X, so no problem


s.t. X>=0, BX >= C

most probably, the >= is meant componentwise for the
matrix entries, i.e. (X)_ij >=0, (BX)_ij >= (C)_ij.
So if X,B and C are (nxn) matrices, you get a
total of 2*n^2 constraints (n^2 from X>=0 and
n^2 from BX>=C)

where c and 1 are vectors, while A,B,C and X are >matrices.

Thanks very very much.


Fan
Back to top
Torsten Hennig
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 136

PostPosted: Fri Jul 14, 2006 11:28 am    Post subject: Re: How to solve linear program with matrix variable ? Reply with quote

Torsten Hennig wrote:
Quote:
Hi,

I am facing a problem to solve an LP with matrix >variable, not vectors.


Can anybody give me some hint or references?

The problem is like,

min_X c' * (XA - AX) * 1


multiplying out, this gives a scalar expression in the
matrix entries x_ij of the matrix X, so no problem


s.t. X>=0, BX >= C

most probably, the >= is meant componentwise for the
matrix entries, i.e. (X)_ij >=0, (BX)_ij >= (C)_ij.
So if X,B and C are (nxn) matrices, you get a
total of 2*n^2 constraints (n^2 from X>=0 and
n^2 from BX>=C)

where c and 1 are vectors, while A,B,C and X are >matrices.

Thanks very very much.


Fan

The problem is that I am using Matlab. The LP solver in >Matlab can
only take the form like

min c'x
s.t. Ax<=b

How can I solve this in Matlab?

Thanks again.

Hi,

first you should build a new solution _vector_ x_matlab
from your solution _matrix_ X by writing X
columnwise in x_matlab (if X is an (nxn)-matrix,
x_matlab now has length n^2 with column 1 of X
at positions 1 to n, column 2 of X at positions
(n+1) to 2*n etc.).
With this ordering of the solution vector, the
matlab-matrix A_matlab is a block matrix with the matrix
(-B) n times repeated on the diagonal and the (n^2xn^2)-
identity matrix at the bottom.
The matlab-vector b_matlab is the matrix (-C) written columnwise as a vector (like X was written columnwise
for the vector x_matlab) with n^2 zeros added at the
bottom.
(If you understand what I mean you should get a
matrix A_matlab of dimension (2*n^2 x n^2), a
vector x_matlab in matlab of dimension n^2 and
a vector b_matlab of dimension 2*n^2).
The (k-1)*n+i -th coefficient of the matlab vector
c_matlab is given by sum_{j=1}^n (c_i*a_kj - c_j*a_ji)
where c and A are the vector c and the matrix A
of your original problem formulation.

Best wishes
Torsten.
Back to top
Torsten Hennig
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 136

PostPosted: Fri Jul 14, 2006 4:16 pm    Post subject: Re: How to solve linear program with matrix variable ? Reply with quote

Torsten Hennig wrote:
Quote:
Hi,

I am facing a problem to solve an LP with matrix >variable, not vectors.


Can anybody give me some hint or references?

The problem is like,

min_X c' * (XA - AX) * 1


multiplying out, this gives a scalar expression in the
matrix entries x_ij of the matrix X, so no problem


s.t. X>=0, BX >= C

most probably, the >= is meant componentwise for the
matrix entries, i.e. (X)_ij >=0, (BX)_ij >= (C)_ij.
So if X,B and C are (nxn) matrices, you get a
total of 2*n^2 constraints (n^2 from X>=0 and
n^2 from BX>=C)

where c and 1 are vectors, while A,B,C and X are >matrices.

Thanks very very much.


Fan

The problem is that I am using Matlab. The LP solver in >Matlab can
only take the form like

min c'x
s.t. Ax<=b

How can I solve this in Matlab?

Thanks again.

Hi,

first you should build a new solution _vector_ x_matlab
from your solution _matrix_ X by writing X
columnwise in x_matlab (if X is an (nxn)-matrix,
x_matlab now has length n^2 with column 1 of X
at positions 1 to n, column 2 of X at positions
(n+1) to 2*n etc.).
With this ordering of the solution vector, the
matlab-matrix A_matlab is a block matrix with the matrix
(-B) n times repeated on the diagonal and the (n^2xn^2)-
identity matrix at the bottom.
The matlab-vector b_matlab is the matrix (-C) written >columnwise as a vector (like X was written columnwise
for the vector x_matlab) with n^2 zeros added at the
bottom.
(If you understand what I mean you should get a
matrix A_matlab of dimension (2*n^2 x n^2), a
vector x_matlab in matlab of dimension n^2 and
a vector b_matlab of dimension 2*n^2).

I assumed that B is (nxn). In general, B will be
of dimension (mxn) with m >> n. Then the remark in
brackets should read:
(If you understand what I mean you should get a
matrix A_matlab of dimension ((m*n+n^2) x n^2), a
vector x_matlab in matlab of dimension n^2 and
a vector b_matlab of dimension (m*n+n^2)).

Quote:
The (k-1)*n+i -th coefficient of the matlab vector
c_matlab is given by sum_{j=1}^n (c_i*a_kj - c_j*a_ji)
where c and A are the vector c and the matrix A
of your original problem formulation.

Best wishes
Torsten.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Mon Nov 20, 2017 11:29 am | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Diagonalizable matrix aline Math 0 Wed Nov 29, 2006 3:08 am
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts sign of the determinant of an augmented matrix? Mark Math 4 Thu Jul 20, 2006 1:30 am
No new posts spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am
No new posts mathematica: how to feed Solve output into Select? double d Math 12 Mon Jul 17, 2006 10:36 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.1289s ][ Queries: 16 (0.1018s) ][ GZIP on - Debug on ]