Author 
Message 
Fan science forum beginner
Joined: 31 Dec 2005
Posts: 7

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



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

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



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

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



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

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



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
matlabmatrix 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 matlabvector 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 (k1)*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

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



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
matlabmatrix 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 matlabvector 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 (k1)*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 



The time now is Fri Oct 19, 2018 8:42 pm  All times are GMT

