# How to convert a matrix of decision variables in a vector for solving a linear programming problem?

I want to solve this problem :

find the minimum of the function F = sum(sum(A - Q*E)),

were A is an i x j matrix, Q is an i x k matrix and E is an k x j matrix. This is basically a least absolute deviation optimisation, where A are the data, Q are know coefficients and I'm searching for the matrix E.

Apparently it is possible to solve with linear programming, I read that I need to vectorize the matrix E, but I don't know what to do at this point... Can anyone give me some help please ? It will be great !

-
What modeling framework are you using to solve the problem? –  Michael Grant May 27 '13 at 14:11
@MichaelC.Grant : I tried to solve the problem with the linprog solver of Matlab but it appears that this is difficult (many data, many variables...)... –  Charles LL May 27 '13 at 18:50
As I mention below in my edited answer, you may find my software CVX useful for this. –  Michael Grant May 27 '13 at 20:52
@MichaelC.Grant : Thanks for your answers. Indeed, CVX is very useful for solving my problem ! I described my problem below, which is a typical minimization of a linear model for explaining Raman spectroscopy results. Despite my problem is a little large (A = 37*1501; E = 3*1501; Q = 37*3), CVX seems to converge well. Does the use of the professional version will improve the results, or does the "standard" CVX version is accurate for such problem ? I'm an academic member, and I use it for academic research... –  Charles LL May 28 '13 at 11:33
Yes, since this is an LP-representable problem, you might find MOSEK and/or Gurobi a better choice. Go grab the academic license and give it a try. I don't think you'll necessarily get significantly higher accuracy, but you might get faster performance. –  Michael Grant May 28 '13 at 12:59

I am going to assume that you actually want sum(sum(abs(A-Q*E))), since you said you want the least absolute deviation. I'm also going to offer some Matlab code in here since your expression looks like it is expressed in it.

It is common in optimization literature to define a linear operator $\mathop{\textbf{vec}}:\mathbb{R}^{m\times n}\rightarrow\mathbb{R}^{mn}$ which maps a matrix to a vector. Typically this is done "Fortran-style": that is, by stacking the columns one on top of another. For instance, suppose $A\in\mathbb{R}^{m\times n}$ is subdivided by its columns as follows: $$A=\begin{bmatrix} a_1 & a_2 & \dots & a_n \end{bmatrix}, \quad a_i\in\mathbb{R}^m,~i=1,2,\dots,n$$ Then $$\mathop{\textbf{vec}}(A)\triangleq\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix}\in\mathbb{R}^{mn}.$$ So that's really all you are doing here, on one hand. Not surprisingly, this operator is linear, so $\mathop{\textbf{vec}}(A\pm B)=\mathop{\textbf{vec}}(A)\pm\mathop{\textbf{vec}}(B)$ and $\mathop{\textbf{vec}}(\alpha A)=\alpha\mathop{\textbf{vec}}(A)$. In MATLAB, the colon notation gives you the $\mathop{\textbf{vec}}$ operator: A(:)

Now, you do have one challenge: what do do about $\mathop{\textbf{vec}}(QE)$? For this, you need to know about Kronecker products. In particular, you need to represent the matrix-matrix product in terms of the vectorized version of $E$, $\mathop{\textbf{vec}}(E)\in\mathbb{R}^{kj}$. For that you need the formula offered in the "Matrix equations" section of the Wikipedia page. Translated to your problem, you have: $$\mathop{\textbf{vec}}(QE)=(I_{jj}\otimes Q)\mathop{\textbf{vec}}(E).$$

In MATLAB, this computation is simply kron(eye(j),Q)*E(:)

In summary, create $\bar{A}=\mathop{\textbf{vec}}(A)$ (barA), $\bar{Q}=I\otimes Q$ (barQ), and define the variable $\bar{E}\triangleq \mathop{\textbf{vec}}(E)$ (barE), and your expression simply becomes sum(abs(barA-barQ*barE)). If you're really using MATLAB, this is just sum(abs(A(:)-kron(eye(j),Q)*E(:))).

EDIT: since you have confirmed that you intend to use MATLAB, may I recommend my software CVX. It is a modeling framework for convex optimization that does all of these contortions for you. Here, for instance, is the CVX model for this problem, including your condition that $E\geq 0$:

cvx_begin
variable E(k,j)
minimize(sum(sum(abs(A-Q*E))))
subject to
E >= 0
cvx_end


See that? No Kronecker products! Here's an alternate approach:

cvx_begin
variable E(k,j)
minimize(norm(vec(A-Q*E),"inf"))
subject to
E >= 0
cvx_end

-
Thank you very much for those precisions. This is exactly what I want to do, and, as you have guessed, with matlab. Ok, now I get it, I will try to apply that and see what will happens. –  Charles LL May 27 '13 at 14:47
OK, if you're using MATLAB, see my edit. It will make things a LOT easier. –  Michael Grant May 27 '13 at 20:50
Ok, I tried on a simple problem to use the L1-norm optimization applied with linear Programming described in Tarantola (2005). It work. Now I will try your software for comparison. Interestingly, the least absolute deviation optimization give me some strange results at the extremity of my problem, when the traditional linear least squares fit better... My problem is that I have for instance five Raman spectra, where two chemical species give me a signal which is different because their concentration are different. I assume that their Raman signal is linearly correlated with their concentration –  Charles LL May 28 '13 at 10:03
In view of this assumption, I can write that the matrix of my Raman spectra A is the linear sum of the concentration matrix Q and the unitary Raman spectrum of each specie E. @Michael C. Grant : my real problem is composed of 37 spectra, each one composed of 1501 data points... I know that I have three contributions in those spectra, arising from three different molecules... Do you think that your CVX software is suited for solving such large problem ? –  Charles LL May 28 '13 at 10:04

I assume that your double sum is the sum over rows then columns, or vice versa.

If we let $M=A-Q E$ then each element of $M$ is a linear function of the elements E, and so their sum is also a linear function.

Now you have specified no constraints on the values of $E$, so the problem is a simple algebra problem. I'll try to guess your actual question as one of the two following:

1) We want the elements of $E$ to be nonnegative. This gives us a simple linear program.

2) The sum is over the absolute values of the elements of $M$. (This is probably what you are asking about.) Here we introduce one variable for the absolute value of each element of $M$ and constrain it to be greater than the corresponding variable of $M$ and its negative. Minimizing the sum will force the value to be equal to the absolute value.

For example, if we name the matrix of absolute values $N$ then

[N_{1,1} \ge A_{1,1} - \sum_k A_{1,k} E_{k,1}] and [N_{1,1} \ge -A_{1,1} + \sum_k A_{1,k} E_{k,1}] and so forth. Your objective will be the sum of the elements of $N$.

If you mean something else, please be clearer.

-
Yes, I want to minimized the least absolute deviation defined as abs(Aij - Qik x Ekj), with Ekj >= 0. I know Qik and Aij are the data. According to linear programming, I can write : minimize sum(sum(Sij)), with Sij >= Aij - Qik x Ekj and Sij >= -(Aij - Qik x Ekj). Such a problem seems quite simple when E is a vector, but not direct when we deal with matrix... How I can overpass the matrix problem ? –  Charles LL May 27 '13 at 14:22
Because $S_{ij}$ is a linear function of the elements of $E$. Michael Grant has an abstract description of this. If we let $M_{ij}=A_{ij}-\sum_k Q_{ik}E_{kj}$ then $M_{ij}$ is just a linear function of the elements of $E$. You are essentially writing $E$ as a vector by pasting the columns together to create a new long column vector. –  deinst May 27 '13 at 14:42