|
|
| 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
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
|
| 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
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 |
|
|
|
|
The time now is Thu Jun 21, 2018 8:20 am | All times are GMT
|
|
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
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
