Huber penalty function in linear programming form

Question

I am trying to solve problem 6.3(b) of Boyd & Vandenberghe's Convex Optimization:

Express the following minimization as a QP, LP, SOCP or SDP $$ \min_{\mathbf{x}}\sum\limits_{i=0}^K \phi(\mathbf{a}_i^T \mathbf{x}-\mathbf{b})$$ where $$\phi(u) = \begin{cases} u^2 & |u| \leq M \\ M(2|u|-M) \quad & |u| > M \end{cases}$$

---

I have no idea on how to start this. Any help would be greatly appreciated.

Answer 1

One of the reasons we like the Huber penalty is that it is the "Moreau-Yosida regularization" of the absolute value function, which means that \begin{equation*} \phi(y) = \inf_u \quad | u | + \frac{1}{2M} (u - y)^2. \end{equation*}

So, your optimization problem can be written as \begin{equation*} \operatorname*{minimize}_{x} \quad \sum_i \inf_{u_i} \, |u_i | + \frac{1}{2M} (u_i - a_i^T x + b)^2 \end{equation*} which is equivalent to \begin{equation*} \operatorname*{minimize}_{x,u_1,\ldots,u_K} \quad \sum_i |u_i| + \frac{1}{2M} (u_i - a_i^T x + b)^2. \end{equation*} Now you can deal with the absolute value terms using the standard trick of introducing variables $t_i$ that satisfy the constraints $|u_i| \leq t_i$ (or in other words, $u_i \leq t_i$ and $-u_i \leq t_i$).