10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – spurra Oct 12 '14 at 22:14
  • $\begingroup$ 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. $\endgroup$ – Glen_b Oct 12 '14 at 22:21
  • $\begingroup$ 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?? $\endgroup$ – Glen_b Oct 12 '14 at 22:23
  • $\begingroup$ 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$. $\endgroup$ – spurra Oct 12 '14 at 22:32
  • 1
    $\begingroup$ @AD.Net The constraints are mostly covered in the other answer. $\endgroup$ – Glen_b Feb 19 '15 at 23:28
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Myath Jul 23 '18 at 21:14
  • $\begingroup$ 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. $\endgroup$ – Marko Oct 20 '18 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.