Programação quadrática e laço

Estou tentando executar uma regressão de laço, que tem a seguinte forma:

Minimizar em $w$ $(Y - Xw)'(Y - Xw) + \lambda \;|w|_1$

Dado a , fui aconselhado a encontrar o ideal com a ajuda da programação quadrática, que assume a seguinte forma: $\lambda$ $w$

Minimize em , sujeito a $x$ $\frac{1}{2} x'Qx + c'x$ $Ax \le b.$

Agora percebo que o termo deve ser transformado no termo de restrição , que é bastante direto. No entanto, de alguma forma, simplesmente não vejo como eu poderia transferir o primeiro termo da primeira equação para o primeiro termo da segunda. Como não consegui encontrar muita coisa na rede, resolvi perguntar aqui. $\lambda$ $Ax \le b$

regression lasso quadratic-form spurra
fonte

Respostas:

Tendo em mente que estamos trabalhando com como a variável ' ' no formulário padrão, expanda e colete termos em e e , e constantes. $w$ $x$ $(Y - Xw)'(Y - Xw)$ $w'\, [\,_{^{^\text{something}}}]\,w$ $w'$ $w$

Explique por que você pode ignorar as constantes.

Explique por que você pode combinar a e termos. $w'$ $w$

Como BananaCode tem até agora descobri com algum líder ao longo do caminho, você pode escrever e ou mais simplesmente, você poderia simplesmente escrever e (já que e têm o mesmo argumento para qualquer ). $Q=2X'X$ $c=-2X'Y$ $Q=X'X$ $c=-X'Y$ $f(x)$ $kf(x)$ $k>0$

Glen_b -Reinstate Monica
fonte

As constantes podem ser ignoradas, porque se x_ é o mínimo para f (x), então x_ + c é o mínimo de f (x) + c, portanto, podemos ignorar a constante c. Vou editar minha pergunta para mostrar onde fiquei preso.

Spurra # 12/14

BananaCode sua explicação tem várias falhas. Se por "é o mínimo para " você quer dizer "é o argumento no qual é minimizado", você diz algo como " é o de ". Mas a sua conclusão está errada. Se você adicionar a , não adicionará ao argmin.

f (x)

$f(x)$

f (x)

$f(x)$

x^{*}

$x^*$

argmin

$\text{argmin}$

f

$f$

c

$c$

f

$f$

c

$c$

Glen_b -Reinstala Monica

Veja onde eu escrevi na minha resposta? Qual é a coisa que você tem agora entre a e o na parte inferior da sua pergunta ??

w^{'} [something] w

$w'\, [\,\text{something}]\,w$

w^{'}

$w'$

w

$w$

Glen_b -Reinstala Monica

Sim, eu quis dizer é o de . Você poderia dar um exemplo em que minha conclusão está errada? O é a matriz que estou tentando formar. Se eu expandir , recebo . A primeira parte representaria a forma da matriz , no entanto, não consigo me livrar do segundo termo .

x *

$x*$

a r g m i n

$argmin$

f

$f$

[s o m e t h i n g]

$[something]$

Q

$Q$

w^{'} (X^{'} X w - X^{'} Y)

$w'(X'Xw - X'Y)$

w^{'} X^{'} X w - w^{'} X^{'} Y

$w'X'Xw - w'X'Y$

Q

$Q$

- w^{'} X^{'} Y

$-w'X'Y$

Spurra # 12/14

@ AD.Net As restrições são abordadas principalmente na outra resposta.

Glen_b -Reinstala Monica

Eu queria adicionar como resolver transformando as restrições uma forma utilizável para programação quadrática, pois não é tão direta quanto eu pensava. Não é possível encontrar uma matriz real tal que . $\sum |w_i| \le s$ $A$ $Aw \le s \leftrightarrow \sum |w_i| \le s$

A abordagem que usei foi dividir os elementos do vetor em e , de modo que . Se , você tem e , caso contrário, você teme . Ou, em termos mais matemáticos, eAmbos e são números não negativos. A idéia por trás da divisão dos números é que agora você tem $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|$ $w_i^+ = 0$ $w_i^+ = \frac{|w_i| + w_i}{2}$ $w_i^- = \frac{|w_i| - w_i}{2}.$ $w_i^-$ $w_i^+$ $|w_i| = w_i^+ + w_i^-$ , eliminando efetivamente os valores absolutos.

A função para otimizar se transforma em: , assunto para $\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$ $w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

Onde e são dados como indicado acima por Glen_b $Q$ $c$

Isso precisa ser transformado em uma forma utilizável, ou seja, precisamos de um vetor. Isso é feito da seguinte maneira:

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

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

Onde é o matriz unidade -dimensional, um -dimensional vector contendo apenas o valor de e um -dimensional vector zero. A primeira metade garante , o segundo Agora está em uma forma utilizável usar a programação quadrática para procurar e , dados . Feito isso, seu parâmetro ideal em relação a é . $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^-$

Fonte e leituras adicionais: Solucionando problemas de programação quadrática com restrições lineares contendo valores absolutos

spurra
fonte

Suponha que encontramos um vetor ideal . O que garante que e são na verdade as partes positivas e negativas de algum vetor , ou seja, suas posições de entrada coincidem?

2 D

$2D$

(w^{+}, w^{-})

$(w^+, w^-)$

w^{+}

$w^+$

w^{-}

$w^-$

w

$w$

0

$0$

Myath 23/07/19

Matriz e vetor na expressão final podem ser mais simples e, na verdade, mais corretos. Em vez de [Id Id] [w + w−] '≤ Sd, você pode colocar simplesmente [1 1 .... 1] [w + w-]' ≤ s. Isso é literalmente equivalente a ∑ | wi | = ∑ (wi + + wi−) ≤ s.

Marko