Quadratic problem solving with absolute value constraint - MathOverflow

Quadratic problem solving with absolute value constraint

2011-09-26T13:19:40Z

Hello,

I have been trying to solve a problem of the form :

$\max_x\quad -\tfrac{1}{2}x^TAx + b^Tx - C\sum_i |x_i|$

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.

If you could share your opinion on this problem it would be greatly appreciated

best regards edit : A is a positive-definite matrix

Answer by Gilead for Quadratic problem solving with absolute value constraint

2011-09-26T16:33:18Z

Well, you have a non-smooth unconstrained problem but there exists a standard reformulation of the absolute function into linear constraints.

$ \begin{align} &\max_{x} -\frac{1}{2}x^T A x + b^T x - C \sum_{i} z_{i}\\ s.t.\quad & z_{i} = s_{i}^{+} + s_{i}^{-}, \quad \forall i\\ & x_{i} = s_{i}^{+} - s_{i}^{-}, \quad \forall i\\ & s_{i}^{+}, s_{i}^{-} \geq 0, \quad \forall i\\ \end{align} $

with $A \succ 0$.

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).

Answer by suVRit for Quadratic problem solving with absolute value constraint

2011-10-10T21:26:22Z

After your edit, the problem becomes equivalent to the convex problem:

$$\min x^TAx - b^Tx + C\|x\|_1$$

This is a very-well studied problem, and here are the keywords that will help you find algorithms and papers that solve it:

Iterative soft-thresholding
L1-LS (L1 regularized least squares)
Forward Backward Splitting
LASSO
Also see Mark Schmidt's webpage

Good luck.