Prove That Lasso Can Be Written as a Quadratic Program

# 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. ### What a Strong Answer Covers - A quadratic objective and linear constraints using auxiliary variables or coefficient splitting. - Both directions of the equivalence argument, including why the absolute-value bound is tight at an optimum. - A positive-semidefinite quadratic matrix and a correct distinction between convexity and uniqueness. ```hint 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?