Programación Cuadrática y Lazo

Estoy tratando de realizar una regresión de lazo, que tiene la siguiente forma:

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

Dado un , me aconsejaron encontrar la w óptima con la ayuda de la programación cuadrática, que toma la siguiente forma:$\lambda$$w$

Minimizar en $x$, sujeto aAx≤b$\frac{1}{2} x'Qx + c'x$$Ax \le b.$

Ahora me doy cuenta de que el término debe transformarse en el término de restricción A x ≤ b , que es bastante sencillo. Sin embargo, de alguna manera no veo cómo podría transferir el primer término de la primera ecuación al primer término de la segunda. No pude encontrar mucho al respecto en la red, así que decidí preguntar aquí.$\lambda$$Ax \le b$

Teniendo en cuenta que estamos trabajando con como la variable ' x ' en la forma estándar, expanda ( Y - X w ) ′ ( Y - X w ) y recopile términos en w $w$$x$$(Y - Xw)'(Y - Xw)$ y en w ' y w , y constantes.$w'\, [\,_{^{^\text{something}}}]\,w$$w'$$w$

Explica por qué puedes ignorar las constantes.

Explicar por qué se puede combinar el y W términos.$w'$$w$

Como BananaCode ya ha descubierto algunos guiones a lo largo del camino, puede escribir y c = - 2 X ′ Y o más simplemente, puede escribir Q = X ′ X y c = - X ′ Y (ya que f ( x ) y k f ( x ) tienen el mismo argumento para cualquier k > 0 ).$Q=2X'X$$c=-2X'Y$ $Q=X'X$$c=-X'Y$$f(x)$$kf(x)$$k>0$

Quería agregar cómo resolver transformando las restricciones en una forma utilizable para la programación cuadrática, ya que no es tan sencillo como pensaba. No es posible encontrar una matriz real A tal que A w ≤ s ↔ ∑ | w i | ≤ s .$\sum |w_i| \le s$$A$$Aw \le s \leftrightarrow \sum |w_i| \le s$

El enfoque que utilicé fue dividir los elementos del vector w en w + i y w - i , de modo que w i = w + i - w - i . Si w i ≥ 0 , tienes w + i = w i y w - i = 0 , de lo contrario tienes w - i = | w i | y $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|$. O en términos más matemáticos,w + i =| wi| +w$w_i^+ = 0$ yw - i =| wi| -w$w_i^+ = \frac{|w_i| + w_i}{2}$Tantow - i comow + i son números no negativos. La idea detrás de dividir los números es que ahora tienes| wi| =w + i +w - i , eliminando efectivamente los valores absolutos.$w_i^- = \frac{|w_i| - w_i}{2}.$$w_i^-$$w_i^+$$|w_i| = w_i^+ + w_i^-$

$\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$$w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

$Q$$c$

Esto debe transformarse en una forma utilizable, es decir, necesitamos un vector. Esto se hace de la siguiente manera:

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

sujeto a

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

$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$$w^+$$w^-$$s$$s$$w = w^+ - w^-$

Fuente y lecturas adicionales: resolución de problemas de programación cuadrática con restricciones lineales que contienen valores absolutos