Re: How to solve linear program with matrix variable ?
- From: Torsten Hennig <Torsten.Hennig@xxxxxxxxxxxxxx>
- Date: Fri, 14 Jul 2006 12:16:15 EDT
Torsten Hennig wrote:
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)).
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.
- References:
- Re: How to solve linear program with matrix variable ?
- From: Torsten Hennig
- Re: How to solve linear program with matrix variable ?
- Prev by Date: Re: LP problem conversion
- Next by Date: Re: Recommendation for numerical differentiation formulas?
- Previous by thread: Re: How to solve linear program with matrix variable ?
- Next by thread: Logistic time-step problem
- Index(es):
Relevant Pages
|
