Reformulating $\arg\min |x|$.

Question

Is it possible to reformulate next optimization problem $\arg\min |x|$ in terms of constrained minimization problem with twice continuously differentiable functions.

As an example of such transformation: $\arg\min \max_{i-1,\dots,m} (a_i^T x + b_i)$ is equivalent to minimize t subject to $a_i^Tx + b_i \le t, i = 1, \dots, m$

fidbc · Accepted Answer · 2013-02-23T23:39:15.557

1

You can try rewriting the absolute value as $|x|=\max\{x,-x\}$. Using the transformation you mention you are left with:

\begin{align} \min &t \\ \text{s.t.}\\ x&\leq t\\ -x&\leq t. \end{align}

edited Feb 23 '13 at 23:39

answered Feb 23 '13 at 23:06

fidbc

909

score 1 · Answer 2 · answered Feb 23 '13 at 23:13

1

\begin{align} \min &f(x) \\s.t.\\|g(x)|\leq 0\\ &\downarrow \\ \min &f(x)\\s.t.\\g(x)&\leq 0\\-g(x)&\leq0 \end{align}

answered Feb 23 '13 at 23:13

Inquest

6,635

Reformulating $\arg\min |x|$.

2 Answers2