Quadratische Programmierung und Lasso

Ich versuche eine Lasso-Regression durchzuführen, die folgende Form hat:

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

Bei einem wurde mir geraten, das optimale mit Hilfe der quadratischen Programmierung zu finden, die die folgende Form annimmt:$\lambda$$w$

Minimiere in , vorbehaltlich$x$$\frac{1}{2} x'Qx + c'x$$Ax \le b.$

Jetzt ist mir klar, dass der Term in den Constraint-Term , was ziemlich einfach ist. Ich sehe jedoch irgendwie nicht, wie ich den ersten Term der ersten Gleichung in den ersten Term der zweiten übertragen könnte. Ich konnte im Internet nicht viel darüber finden, also habe ich beschlossen, hier zu fragen.$\lambda$$Ax \le b$

Wenn man bedenkt , dass wir arbeiten mit als ' ' Variable in der Standardform, erweitern und collect Begriffe in und in und und Konstanten.$w$$x$$(Y - Xw)'(Y - Xw)$$w'\, [\,_{^{^\text{something}}}]\,w$$w'$$w$

Erklären Sie, warum Sie die Konstanten ignorieren können.

Erklären Sie, warum Sie die Begriffe und kombinieren können .$w'$$w$

Wie BananaCode inzwischen herausgefunden hat, können einige entweder und oder einfacher und (da und für jedes das gleiche Argmin haben ).c = - 2 X '$Q=2X'X$$c=-2X'Y$ $Q=X'X$$c=-X'Y$$f(x)$$kf(x)$$k>0$

Ich wollte hinzufügen, wie man die Transformation der Einschränkungen löst in eine verwendbare Form für die quadratische Programmierung, da es nicht ganz so einfach ist, wie ich dachte. Es ist nicht möglich, eine reelle Matrix A zu finden, so dass A w ≤ s ↔ ∑ | ist w i | ≤ s .$\sum |w_i| \le s$$A$$Aw \le s \leftrightarrow \sum |w_i| \le s$

Der Ansatz, den ich benutzte, bestand darin, die Elemente des Vektors w in w + i und w - i aufzuteilen , so dass w i = w + i - w - i . Wenn w i ≥ 0 ist , haben Sie w + i = w i und w - i = 0 , sonst haben Sie w - i = | w i | und $w_i$$w$$w_i^+$$w_i^-$$w_i = w_i^+ - w_i^-$$w_i \ge 0$$w_i^+ = w_i$$w_i^- = 0$$w_i^- = |w_i|$. Oder mathematischer ausgedrückt,w + i =| wi| +w$w_i^+ = 0$ undw - i =| wi| -w$w_i^+ = \frac{|w_i| + w_i}{2}$Sowohlw - i als auchw + i sind nicht negative Zahlen. Die Idee hinter der Aufteilung der Zahlen ist, dass Sie jetzt| haben wi| =w + i +w - i , wodurch die absoluten Werte effektiv beseitigt werden.$w_i^- = \frac{|w_i| - w_i}{2}.$$w_i^-$$w_i^+$$|w_i| = w_i^+ + w_i^-$

Die zu optimierende Funktion wird zu: , vorbehaltlich w + i +w - i ≤s$\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$$w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

Wobei und c wie oben von Glen_b angegeben sind$Q$$c$

Dies muss in eine verwendbare Form umgewandelt werden, dh wir benötigen einen Vektor. Dies geschieht folgendermaßen:

$\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]$

vorbehaltlich

$\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]$

Wobei die D- dimensionale Einheitsmatrix ist, s D ein D- dimensionaler Vektor, der nur aus dem Wert s und 0 D a 2 ∗ D -dimensionaler Nullvektor besteht. Die erste Hälfte sorgt für | w i | = w + i + w - i ≤ s , das zweite w + i , w - i ≥ 0 Jetzt ist es in einer verwendbaren Form, nach quadratischer Programmierung zu suchen$I_D$$D$$s_D$$D$$s$$0_D$$2*D$$|w_i| = w_i^+ + w_i^- \le s$$w_i^+,w_i^- \ge 0$ und w - , gegeben s . Sobald dies geschehen ist, Ihre optimalen Parameter in Bezug auf s sind w = w + - w - .$w^+$$w^-$$s$$s$$w = w^+ - w^-$

Quelle und weiterführende Literatur: Lösung eines quadratischen Programmierproblems mit linearen Einschränkungen, die absolute Werte enthalten