Programowanie kwadratowe i Lasso

Próbuję wykonać regresję lasso, która ma następującą postać:

Minimalizuj w( Y - X w ) ′ ( Y - X w ) + $w$$(Y - Xw)'(Y - Xw) + \lambda \;|w|_1$

Biorąc pod uwagę , doradzono mi, aby znaleźć optymalne za pomocą programowania kwadratowego, które przyjmuje następującą postać:$\lambda$$w$

Minimalizuj w , z zastrzeżeniem$x$Ax≤b$\frac{1}{2} x'Qx + c'x$$Ax \le b.$

Teraz zdaję sobie sprawę, że termin należy przekształcić w termin , co jest dość proste. Jednak jakoś nie rozumiem, jak mógłbym przenieść pierwszy człon pierwszego równania do pierwszego członu drugiego. Nie mogłem znaleźć dużo na ten temat w sieci, więc postanowiłem zapytać tutaj.A x ≤ $\lambda$$Ax \le b$

Pamiętając, że pracujemy z jako zmienną „ ” w standardowej formie, rozwiń i zbieraj terminy w i i , a stałymi.x ( Y - X w ) ′ ( Y - X w ) w $w$$x$$(Y - Xw)'(Y - Xw)$w ′$w'\, [\,_{^{^\text{something}}}]\,w$$w'$$w$

Wyjaśnij, dlaczego możesz zignorować stałe.

Wyjaśnić, dlaczego można połączyć oraz kategoriach.$w'$$w$

Jak BananaCode został już zorientowali się, ze niektórzy wiodący wzdłuż ścieżki, można napisać i lub prościej, można po prostu napisać i (ponieważ i mają ten sam argmin dla dowolnego ).c = - 2 X ′ Y Q = X ′ X c = - X ′ Y f ( x ) k f ( x ) k > $Q=2X'X$$c=-2X'Y$ $Q=X'X$$c=-X'Y$$f(x)$$kf(x)$$k>0$

Chciałem dodać, jak rozwiązać transformację ograniczeń w użyteczną formę do programowania kwadratowego, ponieważ nie jest to tak proste, jak myślałem. Nie można znaleźć prawdziwej macierzy A takiej, że A w ≤ s ↔ ∑ | w i | ≤ s .$\sum |w_i| \le s$$A$$Aw \le s \leftrightarrow \sum |w_i| \le s$

Metoda I zastosowano do dzielenia elementów wektora W w W + I i W - I tak, w I = W + I - W - I . Jeśli w i ≥ 0 , masz w + i = w i oraz w - i = 0 , w przeciwnym razie masz w - i = | w i | i $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|$. Lub bardziej matematycznie,w + i =| wi| +w$w_i^+ = 0$ orazw - i =| wi| -w$w_i^+ = \frac{|w_i| + w_i}{2}$Zarównow - i, jak iw + i są liczbami nieujemnymi. Pomysł dzielenia liczb jest taki, że masz| wi| =w + i +w - i , skutecznie pozbywając się wartości bezwzględnych.$w_i^- = \frac{|w_i| - w_i}{2}.$$w_i^-$$w_i^+$$|w_i| = w_i^+ + w_i^-$

Funkcja optymalizacji zmienia się w: , z zastrzeżeniem 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$

Gdzie i c podano jak podano powyżej przez Glen_b$Q$$c$

To musi zostać przekształcone w użyteczną formę, tzn. Potrzebujemy jednego wektora. Odbywa się to w następujący sposób:

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

z zastrzeżeniem

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

Gdzie jest macierzą D- wymiarowej jednostki, s D jest wektorem D- wymiarowym składającym się tylko z wartości s, a 0 D jest w wymiarze wektora zerowego 2 ∗ D. Pierwsza połowa zapewnia | w i | = w + i + w - i ≤ s , drugie w + i , w - i ≥ 0 Teraz w użytecznej formie można użyć programowania kwadratowego do wyszukiwania$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$ i w - , biorąc pod uwagę s . Po wykonaniu tego optymalnym parametrem w odniesieniu do s jest w = w + - w - .$w^+$$w^-$$s$$s$$w = w^+ - w^-$

Źródło i dalsze czytanie: Rozwiązywanie problemu programowania kwadratowego z ograniczeniami liniowymi zawierającymi wartości bezwzględne