0
$\begingroup$

I am approximating the expression $\left\|Ax-b\right\|_1$ by the expression $$\text{minimize}\;\;\sum_i\sqrt{(a_i^Tx-b_i)^2+\varepsilon}$$ where $a_i$ is the $i^{th}$ row of $A$.

This function is convex, and I was wondering if there was a way to convert it into an SOCP, or if it's hopelessly nonlinear.

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ The original 1-norm minimization is easily transformed into an LP (or SOCP.) Why are you trying to turn this into an SOCP? $\endgroup$ – Brian Borchers May 28 '15 at 8:29
2
$\begingroup$

The original 1-norm minimization problem can easily be converted to an LP (SOCP) using standard techniques.

It is quite odd to convert the smoothed problem into an SOCP, but you could do this as follows:

Let

$u_{i}=[a_{i}^{T}x-b_{i} \;\; \sqrt{\epsilon}]^{T}$

And

$t_{i} \geq \| u_{i} \|_{2} $

Then,

$\min \sum_{i} t_{i}$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks, this makes sense. I'm curious what the reason is for having a differentiable 1-norm approx. if the original problem is so tractable. I'm guessing it's for when it's paired with another function, say acting as a regularizing component, is that correct? $\endgroup$ – Thoth May 28 '15 at 14:36
  • $\begingroup$ This smoothed approximation is not used very often in practice. When people first started working on SOCP 20 years ago, some researchers suggested that using this smoothing with a general nonlinear optimization routine might be a better way to solve SOCPs then using a primal-dual interior point method for SOCP. There is a paper about doing this by Robert Vanderbei using his code, LOQO. You could certainly try to use this approach to enforce a second order cone constraint within a more general purpose optimization solver. I am curious what context this idea came up in. $\endgroup$ – Brian Borchers May 28 '15 at 17:28
  • $\begingroup$ SOCP can certainly handle most commonly used regularization schemes. $\endgroup$ – Brian Borchers May 28 '15 at 17:29
  • $\begingroup$ This is exercise 6.4 in Boyd's Convex Optimization. Officially the problem is to obtain a bound on the error of the approximation, but I was also curious if the expression could be subsumed into SOCP. $\endgroup$ – Thoth May 28 '15 at 17:39
  • $\begingroup$ What are other known smooth approximations to $ {L}_{1} $ norm? $\endgroup$ – Royi Aug 19 '17 at 12:33

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.