# Quadratic Programming and Lasso

I'm trying to perform a lasso regression, which has following form:

Minimize $w$ in $(Y - Xw)'(Y - Xw) + \lambda \;|w|_1$

Given a $\lambda$, I was advised to find the optimal $w$ with the help of quadratic programming, which takes the following form:

Minimize $x$ in $\frac{1}{2} x'Qx + c'x$, subject to $Ax \le b.$

Now I realize that the $\lambda$ term should be transformed into the constraint term $Ax \le b$, which is rather straightforward. However, I somehow just don't see how I could transfer the first term of the first equation into the first term of the second. I couldn't find much about it on the net, so I decided to ask here.

## 2 Answers

Keeping in mind that we're working with $w$ as the '$x$' variable in the standard form, expand $(Y - Xw)'(Y - Xw)$ and collect terms in $w'\, [\,_{^{^\text{something}}}]\,w$ and in $w'$ and $w$, and constants.

Explain why you can ignore the constants.

Explain why you can combine the $w'$ and $w$ terms.

As BananaCode has by now figured out with some leading along the path, you can either write $Q=2X'X$ and $c=-2X'Y$ or more simply, you could just write $Q=X'X$ and $c=-X'Y$ (since $f(x)$ and $kf(x)$ have the same argmin for any $k>0$).

• The constants can be ignored, because if x_ is the minimum to f(x), then x_ + c is the minimum of f(x) + c, hence we can ignore the constant c. I'll edit my question to show where I got stuck. – spurra Oct 12 '14 at 22:14
• BananaCode your explanation has several flaws. If by "is the minimum to $f(x)$" you mean "is the argument at which $f(x)$ is minimized", you say something like "$x^*$ is the $\text{argmin}$ of $f$". But your conclusion there is wrong. If you add $c$ to $f$, you don't add $c$ to the argmin. – Glen_b Oct 12 '14 at 22:21
• See where I wrote $w'\, [\,\text{something}]\,w$ in my answer? What's the something you now have between the $w'$ and the $w$ at the bottom of your question?? – Glen_b Oct 12 '14 at 22:23
• Yes, I meant $x*$ is the $argmin$ of $f$. Could you give an example where my conclusion is wrong? The $[something]$ is the $Q$ matrix I'm trying to form. If I expand $w'(X'Xw - X'Y)$ I get $w'X'Xw - w'X'Y$. The first part would represent the form of the $Q$ matrix, however I can't get rid of the second term $-w'X'Y$. – spurra Oct 12 '14 at 22:32
• @AD.Net The constraints are mostly covered in the other answer. – Glen_b Feb 19 '15 at 23:28

I wanted to add how to solve transforming the constraints $\sum |w_i| \le s$ into a usable form for quadratic programming, as it is not quite as straightforward as I thought. It's not possible to find a real matrix $A$ such that $Aw \le s \leftrightarrow \sum |w_i| \le s$.

The approach I used was to split the elements $w_i$ of vector $w$ into $w_i^+$ and $w_i^-$, so that $w_i = w_i^+ - w_i^-$. If $w_i \ge 0$, you have $w_i^+ = w_i$ and $w_i^- = 0$, else you have $w_i^- = |w_i|$ and $w_i^+ = 0$. Or in more mathematical terms, $w_i^+ = \frac{|w_i| + w_i}{2}$ and $w_i^- = \frac{|w_i| - w_i}{2}.$ Both $w_i^-$ and $w_i^+$ are non-negative numbers. The idea behind splitting the numbers up is that you now have $|w_i| = w_i^+ + w_i^-$, effectively getting rid of the absolute values.

The function to optimize turns into: $\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$, subject to $w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

Where $Q$ and $c$ are given as stated above by Glen_b

This needs to be transformed into a usable form, i.e we need one vector. This is done in the following way:

$\frac{1}{2} \bigg[ \begin{array}{c} w^+ \\ w^- \end{array} \bigg]^T \bigg[ \begin{array}{cc} Q & -Q \\ -Q & Q \end{array} \bigg] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] + \big[ \begin{array}{cc} c^T & -c^T \end{array} \big] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg]$

subject to

$\bigg[ \begin{array}{cc} I_D & I_D \\ -I_{2D} \end{array} \bigg]\bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] \le \bigg[ \begin{array}{c} s_D \\ 0_{2D} \end{array}\bigg]$

Where $I_D$ is the $D$-dimensional unit matrix, $s_D$ a $D$-dimensional vector consisting only of the value $s$ and $0_D$ a $2*D$-dimensional zero vector. The first half ensures $|w_i| = w_i^+ + w_i^- \le s$, the second $w_i^+,w_i^- \ge 0$ Now it's in a usable form to use quadratic programming to search for $w^+$ and $w^-$, given $s$. Once that is done, your optimal parameter with respect to $s$ is $w = w^+ - w^-$.

Source and further reading: Solving quadratic programming problem with linear constraints containing absolute values

• Suppose that we've found an optimal $2D$-dimensional vector $(w^+, w^-)$. What ensures that $w^+$ and $w^-$ are actually the positive parts and negative parts of some vector $w$, i.e. their $0$ entry positions match up? – Myath Jul 23 '18 at 21:14
• Matrix and vector in final expression can be more simple, and actually more correct. Instead of [Id Id] [w+ w−]' ≤ Sd you could put simply [1 1 .... 1][w+ w-]' ≤ s. This is literally equivalent to ∑|wi| = ∑(wi+ + wi−) ≤ s. – Marko Oct 20 '18 at 18:53