Prove That Lasso Can Be Written as a Quadratic Program
Point72Quantitative Researcher · Technical ScreenLast updated
Derive the Lasso quadratic-program formulation and prove equivalence, convexity, minimizer correspondence, and rank-related uniqueness.
Prove That Lasso Can Be Written as a Quadratic Program
For a real matrix $X\in\mathbb{R}^{n\times p}$, response $y\in\mathbb{R}^n$, and $\lambda>0$, consider the Lasso problem
$$\min_{\beta\in\mathbb{R}^p};\frac12\lVert y-X\beta\rVert_2^2+\lambda\lVert\beta\rVert_1.$$
Can it be expressed as a quadratic program? Give an explicit formulation and rigorously prove equivalence of optimal values and the correspondence of minimizers. Explain whether convexity or uniqueness requires $X$ to have full column rank.
Hints
Hint 1
Represent absolute values: Look for linear inequalities that force an auxiliary variable to upper-bound both signs of a coefficient.
Follow-up questions
- What changes in the equivalence argument if the penalty is zero?
- How would you leave an intercept unpenalized?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.