Quadratic problem solving with absolute value constraint - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:46:44Z http://mathoverflow.net/feeds/question/76420 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76420/quadratic-problem-solving-with-absolute-value-constraint Quadratic problem solving with absolute value constraint unknown (google) 2011-09-26T13:19:40Z 2011-10-10T21:26:22Z <p>Hello,</p> <p>I have been trying to solve a problem of the form : </p> <p><code>$\max_x\quad -\tfrac{1}{2}x^TAx + b^Tx - C\sum_i |x_i|$</code></p> <p>without the C term it is a simple quadratic problem, but I haven't been able to find any reasearch paper related to this kind of problem solving.</p> <p>If you could share your opinion on this problem it would be greatly appreciated</p> <p>best regards edit : A is a positive-definite matrix</p> http://mathoverflow.net/questions/76420/quadratic-problem-solving-with-absolute-value-constraint/76431#76431 Answer by Gilead for Quadratic problem solving with absolute value constraint Gilead 2011-09-26T16:33:18Z 2011-09-26T17:16:36Z <p>Well, you have a non-smooth unconstrained problem but there exists a standard reformulation of the absolute function into linear constraints.</p> <p><code>\begin{align} &amp;\max_{x} -\frac{1}{2}x^T A x + b^T x - C \sum_{i} z_{i}\\ s.t.\quad &amp; z_{i} = s_{i}^{+} + s_{i}^{-}, \quad \forall i\\ &amp; x_{i} = s_{i}^{+} - s_{i}^{-}, \quad \forall i\\ &amp; s_{i}^{+}, s_{i}^{-} \geq 0, \quad \forall i\\ \end{align}</code></p> <p>with $A \succ 0$.</p> <p>Mind you, this formulation may not give you the correct results if you decide to add constraints on $x_{i}$; if you are constraining $x_{i}$, you may need to reformulate this into a Mixed Integer Quadratic Program (MIQP). </p> http://mathoverflow.net/questions/76420/quadratic-problem-solving-with-absolute-value-constraint/77747#77747 Answer by suVRit for Quadratic problem solving with absolute value constraint suVRit 2011-10-10T21:26:22Z 2011-10-10T21:26:22Z <p>After your edit, the problem becomes equivalent to the convex problem:</p> <p>$$\min x^TAx - b^Tx + C\|x\|_1$$</p> <p>This is a very-well studied problem, and here are the keywords that will help you find algorithms and papers that solve it:</p> <ol> <li>Iterative soft-thresholding</li> <li>L1-LS (L1 regularized least squares)</li> <li>Forward Backward Splitting</li> <li>LASSO</li> <li>Also see <a href="http://www.di.ens.fr/~mschmidt/Software/L1General/L1General.html" rel="nofollow">Mark Schmidt's webpage</a></li> </ol> <p>Good luck.</p>