Katkat

Prove That Lasso Can Be Written as a Quadratic Program

Point72Quantitative Researcher · Technical Screen

Last 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?