2
$\begingroup$

I want to efficiently solve the following optimization problem: \begin{align} \min &\quad \left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2 + \lambda\left\|\mathbf{x}\right\|_1\\ \text{Subject to}& \quad A\mathbf{x} \leq c, \end{align}

where $\mathbf{x}\in \mathbb{R}^{n\times 1}$, for big values of $n$. I tried coordinate descend, but it doesn't work. I also don't want to formulate it as QP and use interior-point methods because they are slow. Any idea?

  • 0
    Apparently, the problem has been solved recently: Peng Zeng, Yu Zhu, and Tianhong He, Linearly Constrained Lasso with Application in Glioblastoma Data. I haven't read it yet, but it looks like they have designed a LARS type algorithm.2012-07-31
  • 0
    Also any Lasso algorithm with projecting to constraint set after each iteration also should work.2012-08-01
  • 0
    @mirror2image, Wouldn't projecting onto the constraints be solving a Non Negative Least Squares?2017-08-23
  • 0
    @Taha, When you say efficiently, what do you mean? I can write a MATLAB code to solve it yet on one step I will need MATLAB's [`quadprog()`](https://www.mathworks.com/help/optim/ug/quadprog.html). Is that OK?2017-08-23

3 Answers 3