Linked Questions

8
votes
2answers
2k views

What Numerical Methods Are Known to Solve $ {L}_{1} $ Regularized Quadratic Programming Problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
2
votes
3answers
2k views

Orthogonal Projection onto the $ {L}_{\infty} $ Unit Ball

What is the Orthogonal Projection onto the $ {\ell}_{\infty} $ Unit Ball? Namely, given $ x \in {\mathbb{R}}^{n} $ what would be: $$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \...
5
votes
2answers
873 views

Proximal Mapping of Least Squares with $ {L}_{1} $ and $ {L}_{2} $ Norm Terms Regularization (Similar to Elastic Net)

I was trying to solve $$\min_x \frac{1}{2} \|x - b\|^2_2 + \lambda_1\|x\|_1 + \lambda_2\|x\|_2,$$ where $ b \in \mathbb{R}^n$ is a fixed vector, and $\lambda_1,\lambda_2$ are fixed scalars. Let $f =...
6
votes
3answers
1k views

$ {L}_{1} $ Regularized Unconstrained Optimization Problem

I am encountering an unconstrained minimization problem. The problem is of the form $$\min_x \frac{\|x-a\|_2^2}{2}+\lambda\|x\|_1$$ where $x,a \in R^n$ and $x$ is the optimization variable. $\...
1
vote
2answers
2k views

gradient norm of a simple function

In this answer Derivation of soft thresholding operator how can I derive that $\nabla(||x-b||_2^2)=b-x$?
3
votes
2answers
950 views

Closed Form Solution of $ \arg \min_{x} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\|x \right\|}_{2} $ - Tikhonov Regularized Least Squares

The problem is given by: $$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\|x \right\|}_{2} $$ Where $y$ and $x$ are vectors. $\|\cdot\|_2$ is Euclidean norm. In the ...
3
votes
1answer
2k views

What's the proximal operator of the nuclear norm optimization problem?

\begin{equation} \arg\min_{X} \frac{1}{2}\|X-Y\|_{F}^2 + \tau\|X\|_{*} \end{equation} where $\tau\geq 0,Y\in \mathbb{C}^{n\times n}$ and $\|\cdot\|_{*}$ is the nuclear norm. What's the solution ...
1
vote
1answer
282 views

soft thresholding derivation with two terms

I am trying to minimize the following function $$argmin_x||x-y||^2_2 + ||x-z||_2^2 + \lambda || \frac{x- w}{c}||_1$$ I have been doing it for while but i am not sure how to do it. I have already been ...
0
votes
1answer
369 views

Proximity operator for logistic function

I am reading the ADMM paper by S. Boyd et al: http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf I'm interested in implementing a L1-regularized feature-wise distributed multinomial ...
1
vote
1answer
153 views

Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $ Can someone please explain to me how to do this since there are no specific constraints?
0
votes
0answers
139 views

Algorithm (SciPy?) for Solving Optimization Problem with Absolute Values

I am at a point in n-dimensional space $X^0$ and it costs me to move to $X_i$ with varying cost depending on direction $\Sigma_i c_i |X_i-X^0_i|$. But, it's good for me to move closer to a target ...
2
votes
1answer
74 views

regression optimisation problem with $l_1$ and $l_2$ norms for $x \in \Bbb R^n$

I'm trying to solve an optimization problem: $$\text{argmin}_{x \in \Bbb R^n}~ f(x),~ f(x) = ||x - a||_2 ^2 + \lambda ||x||_1,~ \lambda>0.$$ Any thoughts on how to solve it? Thanks in advance!