Pemrograman Quadratic dan Lasso

Saya mencoba melakukan regresi laso, yang memiliki bentuk sebagai berikut:

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

Diberikan , saya disarankan untuk mencari optimal dengan bantuan pemrograman kuadratik, yang mengambil bentuk berikut:$\lambda$$w$

Minimalkan dalam , tunduk pada$x$Ax≤b$\frac{1}{2} x'Qx + c'x$$Ax \le b.$

Sekarang saya menyadari bahwa istilah harus diubah menjadi istilah kendala , yang agak mudah. Namun, saya entah bagaimana tidak melihat bagaimana saya bisa mentransfer term pertama dari persamaan pertama ke term pertama dari yang kedua. Saya tidak dapat menemukan banyak tentang itu di internet, jadi saya memutuskan untuk bertanya di sini.A x ≤ $\lambda$$Ax \le b$

Ingatlah bahwa kami bekerja dengan sebagai variabel ' x ' dalam bentuk standar, perluas ( Y - X w ) ′ ( Y - X w ) dan kumpulkan istilah dalam w $w$$x$$(Y - Xw)'(Y - Xw)$ dan di w ′ dan w , dan konstanta.$w'\, [\,_{^{^\text{something}}}]\,w$$w'$$w$

Jelaskan mengapa Anda dapat mengabaikan konstanta.

Jelaskan mengapa Anda dapat menggabungkan istilah dan w .$w'$$w$

Seperti yang sudah diketahui oleh BananaCode dengan beberapa yang memimpin di sepanjang jalan, Anda bisa menulis dan c = - 2 X ′ Y atau lebih sederhana, Anda bisa menulis Q = X ′ X dan c = - X ′ Y (karena f ( x ) dan k f ( x ) memiliki argumen yang sama untuk k > 0 ).$Q=2X'X$$c=-2X'Y$ $Q=X'X$$c=-X'Y$$f(x)$$kf(x)$$k>0$

Saya ingin menambahkan bagaimana memecahkan mengubah kendala menjadi bentuk yang dapat digunakan untuk pemrograman kuadratik, karena tidak semudah yang saya pikir. Ini tidak mungkin untuk menemukan matriks nyata A sehingga A w ≤ s ↔ Σ | w i | ≤ s .$\sum |w_i| \le s$$A$$Aw \le s \leftrightarrow \sum |w_i| \le s$

Pendekatan yang saya gunakan adalah untuk membagi elemen dari vektor w menjadi w + i dan w - i , sehingga w i = w + i - w - i . Jika w i ≥ 0 , Anda memiliki w + i = w i dan w - i = 0 , selain itu Anda memiliki w - i = | w i | dan $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|$. Atau dalam istilah yang lebih matematis,w + i =| wi| +W$w_i^+ = 0$ danw - i =| wi| -w$w_i^+ = \frac{|w_i| + w_i}{2}$Baikw - i danw + i adalah angka non-negatif. Gagasan di balik pemisahan angka adalah bahwa Anda sekarang memiliki| wi| =w + i +w - i , secara efektif menghilangkan nilai absolut.$w_i^- = \frac{|w_i| - w_i}{2}.$$w_i^-$$w_i^+$$|w_i| = w_i^+ + w_i^-$

Fungsi untuk mengoptimalkan berubah menjadi: , tunduk pada 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$

Di mana dan c diberikan seperti yang dinyatakan di atas oleh Glen_b$Q$$c$

Ini perlu diubah menjadi bentuk yang dapat digunakan, yaitu kita perlu satu vektor. Ini dilakukan dengan cara berikut:

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

tunduk pada

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

Di mana adalah matriks unit D- dimensi, s D a D -vektor dimensi yang hanya terdiri dari nilai s dan 0 D a 2 ∗ D- dimensi nol vektor. Babak pertama memastikan | w i | = w + i + w - i ≤ s , w + i kedua , w - i ≥ 0 Sekarang sudah dalam bentuk yang dapat digunakan untuk menggunakan pemrograman kuadratik untuk mencari$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$ dan w - , diberikan s . Setelah selesai, parameter optimal Anda sehubungan dengan s adalah w = w + - w - .$w^+$$w^-$$s$$s$$w = w^+ - w^-$

Sumber dan bacaan lebih lanjut: Memecahkan masalah pemrograman kuadratik dengan kendala linear yang mengandung nilai absolut