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.

$\endgroup$
1
  • 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$ May 28, 2015 at 8:29

1 Answer 1

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}$

$\endgroup$
6
  • $\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$
    – Set
    May 28, 2015 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$ May 28, 2015 at 17:28
  • $\begingroup$ SOCP can certainly handle most commonly used regularization schemes. $\endgroup$ May 28, 2015 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$
    – Set
    May 28, 2015 at 17:39
  • $\begingroup$ What are other known smooth approximations to $ {L}_{1} $ norm? $\endgroup$
    – Royi
    Aug 19, 2017 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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