 Forum index » Science and Technology » Math » num-analysis
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 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 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 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. 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
(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.  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 26, 2019 5:09 am | All times are GMT Forum index » Science and Technology » Math » num-analysis
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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