0
$\begingroup$

I want to convert the following problem into a linear program. $$ \min_{x \in \mathbb{R}^n} \qquad \lvert\lvert Ax - b \rvert\rvert_1$$

Here $A \in \mathbb{R}^{m\times n}$, $x \in \mathbb{R}^n$ and $b \in \mathbb{R}^m$

This was my train of thought so far:

By definition, the first norm is,

$$ \lvert \lvert y\rvert \rvert_1 = \lvert y_1\rvert + \lvert y_2 \rvert + ...+ \lvert y_n\rvert$$ Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable: $$ \lvert x \rvert = x^+ - x^- $$ I have no idea how to do this when the expression is in the format $\lvert a_i^Tx - b_i\rvert$ where $a_i^T$ is a row of the matrix $A$. (Yes I am dumb, I know it).

The best I could think of is adding a constraint $y = Ax -b$ and using $y$ as my variable:

\begin{align} \min_{y_i^+, y_i^- \in \mathbb{R}} \quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ \dots + y_m^+ + y_m^-\\ s.t. \quad & a_1^Tx - b_1 = y_1^+ - y_1^- \\ & a_2^Tx - b_2 = y_2^+ - y_2^- \\ & a_3^Tx - b_3 = y_3^+ - y_3^- \\ \vdots & a_m^Tx - b_m = y_m^+ - y_m^- \end{align}

This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Seems fine. Don't forget to include the nonnegative constraints for your $y_i^+$ and $y_i^-$.

Alternatively

$$\min \sum_{i=m}^n z_i$$

$$z_i \ge a_i^Tx-b_i$$

$$z_i \ge -(a_i^Tx-b_i)$$

$\forall i \in \{1, \ldots, m\}$.

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – PPGoodMan Dec 4 '18 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.