2
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ I think the prime represents a transpose. Please format your equation better. $\endgroup$
    – Will Sawin
    Commented Sep 26, 2011 at 14:05
  • $\begingroup$ As written, the equation did not make sense. I reformatted it to make sense, please undo that if you think that I have incorrectly changed the problem. $\endgroup$
    – Suvrit
    Commented Sep 26, 2011 at 14:52
  • 1
    $\begingroup$ See 'Lasso regularization' or l-1 penalty. $\endgroup$
    – mikitov
    Commented Sep 26, 2011 at 15:34
  • $\begingroup$ It seems that if you maximize, you can make the above objective unbounded. Please revise your problem to make sure that it is precisely stated. @mikitov: this is not lasso. $\endgroup$
    – Suvrit
    Commented Sep 26, 2011 at 15:43
  • $\begingroup$ @Suvrit: It is a sparse regularization, indeed. $\endgroup$
    – mikitov
    Commented Sep 26, 2011 at 15:54

2 Answers 2

Reset to default
2
$\begingroup$

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:

  1. Iterative soft-thresholding
  2. L1-LS (L1 regularized least squares)
  3. Forward Backward Splitting
  4. LASSO
  5. Also see Mark Schmidt's webpage

Good luck.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is not an answer and should have been a comment. $\endgroup$
    – spurra
    Commented Oct 13, 2014 at 9:58
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .