I am trying to determine how the following simple L1 objective can be written as a linear program:
Minimize $(\| Mx – p \|_1) + (\| Mx – q \|_1)$ wrt to $x$ such that $\| x \|_1 = 1$ and all elements of $x$ are nonnegative. $M$ is a matrix, and $x$, $p$, and $q$ are column vectors. $\|\cdot\|_1$ is the L1 norm.
A linear program takes the form:
\begin{array}{ll}
\text{Find a vector} & \mathbf x \\
\text{that maximizes} & \mathbf c^T\mathbf x \\
\text{subject to} & A\mathbf x \le \mathbf b \\
\text{and } & \mathbf x \ge \mathbf 0.
\end{array}
So to enforce the constraint that $\| x \|_1 = 1$, $b = [1, -1]^T$ and $A$ would be a matrix with the first row being all 1's and the second row being all -1's. But what would be $c$?
Thank you for any guidance or feedback.
Best Answer
To represent $\|Mx-p\|_1$ in the objective function, we want a term for the absolute value of $(Mx-p)_i$ (the $i^{\text{th}}$ component of $Mx-p$).
$(Mx-p)_i$ itself is a linear function of $x$, but its absolute value is not. However, we can ask for $y_i \ge |(Mx-p)_i|$ by asking that $y_i \ge (Mx-p)_i$ and $y_i \ge -(Mx-p)_i$. Here, $y_i$ is a new variable we introduce just for this component of the objective function.
When doing this for all $n$ components of $Mx-p$, we have the vector inequalities $y \ge Mx-p$ and $y \ge -(Mx-p)$. These can be phrased in block matrix form as $$ \begin{bmatrix} M & -I \\ -M & -I \end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} \le \begin{bmatrix}p \\ -p\end{bmatrix}. $$ Once we have the variables $y_1, \dots, y_n$ defined in this way, we have $y_1 + y_2 + \dots + y_n \ge \|Mx-p\|_1$, so when we minimize, $y_1 + y_2 + \dots + y_n$ will be equal to $\|Mx-p\|_1$.
We can handle $\|Mx-q\|_1$ similarly, introducing a third variable vector $z$ (so the matrix of inequalities will get fatter and taller). The objective function will just be in terms of the $y$ and $z$ vectors.