L1 Objective as a Linear Program 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.
 A: 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.
A: $\min \{ y_p+y_q | Mx-p \le y_p, -(Mx-p) \le y_p, Mx-q \le y_q, -(Mx-q) \le y_q, e^T x = 1, x \ge 0\}$, where $e$ is a vector of ones.
