The following is problem 4.11(b) on p. 193 of Boyd and Vandenberghe's Convex Optimization, Cambridge University Press, 2004.
Let $A \in \mathbb{R}^{m\times n}$, and $b \in \mathbb{R}^n$. For every $y \in \mathbb{R}^m$, define $\|y\|_1 := |y_1|+\cdots+|y_m|$. Formulate the following problem as a linear programming problem: minimize $\|Ax-b\|_1$.
Following is a proposed solution I have found on the Internet.
Denote by $\mathbf{1}$ the $n$-dimentional vector all of whose components are equal to $1$, and write $v \preceq w$ iff $v_1\leq w_1,\ \dots,\ v_m\leq w_m$.
Then the given problem is equivalent to the following linear program.
$$
\begin{align*}
\text{minimize}\quad & \mathbf{1}^Ts\\
\text{subject to}\quad & Ax – b \preceq s\\
& Ax – b \succeq s.
\end{align*}
$$Explanation: assume that $x$ is fixed in this problem, and we optimize only over $s$. Denote $A$'s $k$th row by $a_k$. Then the constraints say that $-s_k \leq a_kx – b_k \leq s_k$ for each $k$, i.e. $s_k \geq |a_kx-b_k|$. The objective function of the linear program is separable, so we achieve the optimum over $s$ by choosing $s_k = |a_kx-b_k|$, and obtain the optimal value $p^*(x) = \|Ax-b\|_1$. Therefore, optimizing over $t$ and $s$ simultaneously is equivalent to the original problem.
Please help me understand the following issue. The solution says that the objective function of the linear program is separable, but I don't see why this is true: if the constraints broke down into $a_k[0,\dots,0,x_k,0,\dots,0]^T-b_k\leq s_k$ for every $k$, then I would agree that the objective function is separable and that the linear program can be solved by solving $n$ independent linear programs, one for each $x_k$, and then adding the solutions together to get a solution to the original linear program. However, this is not the case: the same $x$ is used in all the constraints $a_kx-b_k\leq s_k$, and therefore who says that the solutions to the $n$ subproblems can be combined to form a feasible point to the original linear program?
And, by the way, is there a formal definition of what a separable objective function is in the context of linear programming, since I couldn't find such a definition in Boyd and Vandenberghe's textbook.
Best Answer
They do not mean that you can solve for $x$ separately.
The argument begins with the assumption that $x$ is fixed. The post was trying to prove that the formulation is equivalent to the original problem.