Minimizing sum constrained on $\ell_1$ and $\ell_2$ norms

41 Views Asked by At

I want to minimize $\displaystyle\sum_{i=1}^r\hat{\lambda}_i$ under the constraints $\displaystyle\sum_{i=1}^r\hat{\lambda}_i^2\ge\sum_{i=1}^r(\lambda_i-\varepsilon)^2,$ $\hat{\lambda}_i\ge 0$ and $\hat{\lambda}_i\le \lambda_i+\varepsilon.$

Here $\varepsilon$ can be assumed to be small, in particular $\dfrac{\varepsilon}{\lambda_{\min}}\le c$ for some small constant $c.$

I wrote the Lagrangian to be

$$L(\mu,\mu_{1i},\mu_{2i})=\displaystyle\sum_{i=1}^r\hat{\lambda}_i-\mu\sum_{i=1}^r\hat{\lambda}_i^2+\sum_{i=1}^r\mu_{1i}\hat{\lambda}_i-\sum_{i=1}^r\mu_{2i}\hat{\lambda}_i$$

The stationary conditions are $\hat{\lambda}_i=\dfrac{1+\mu_{1i}-\mu_{2i}}{2\mu}.$

I am guessing that the dual variables for the nonnegativity constraints will be all zero, and that the optimal point should have $\hat{\lambda}_i=\lambda_i+\varepsilon$ for some of the points and the other points should be such that the $\ell_2$ condition is satisfied with an equality.

But I cannot formalize my argument. I can also work with a good lower bound for the value. In that regard, it can also be useful if you can help me write the dual correctly.