Formulación del problema de optimización restringida convexa (SVR)

Question

Estoy tratando de averiguar dónde me estoy equivocando con la formulación de un cierto problema, ya que todas las otras instancias fueron formuladas de manera ligeramente diferente.

El problema (problema SVR, si estás familiarizado con él) es el siguiente: dada $\{x^{(i)},y_i\}_{i=1}^{m}$, nos gustaría encontrar un hiperplano, definido por $\langle w,x\rangle +b=0$ que minimiza la norma $l_2$ de $w$ más la suma (sobre $i$) de la pérdida definida por: $$loss(w,b;x^{(i)})=[\left|\langle w,x^{(i)}\rangle +b -y_i\right|-\epsilon ]_+ $$

Yo formularía el problema de la siguiente manera: $$\min_{w,b,\xi_i} \frac{1}{2}\|w\|^2 + \sum_{i=1}^{m}\xi_i$$ $$s.t.\cases{\langle w,x^{(i)}\rangle +b-y_i-\epsilon\leq\xi_i\cr y_i-\langle w,x^{(i)}\rangle -b-\epsilon\leq\xi_i\cr \xi_i\geq 0} i=1,...,m $$ Pero cada formulación que he visto utiliza variables separadas $\xi_i,\xi_i^* \geq 0$ para las primeras 2 restricciones: $$\min_{w,b,\xi_i} \frac{1}{2}\|w\|^2 + \sum_{i=1}^{m}(\xi_i + \xi_i^*)$$ $$s.t. \cases{\langle w,x^{(i)}\rangle +b-y_i-\epsilon\leq\xi_i\cr y_i-\langle w,x^{(i)}\rangle -b-\epsilon\leq\xi_i^*\cr \xi_i,\xi_i^*\geq 0} i=1,...,m $$ ¿Qué está mal con mi forma de proceder? Estoy pensando que podría tener algo que ver con las condiciones KKT (ya que queremos formularlo usando los multiplicadores y obtener un problema con un mínimo global). Tengo cierta comprensión básica de las condiciones KKT, pero no entiendo completamente todas las cualificaciones de restricciones (lo cual asumo que podría ser el problema)

Answer 1

El dual de tu nuevo problema primal es casi igual que el dual estándar, con una diferencia. Para ver esto, estoy siguiendo el trabajo en este enlace (pero modificándolo para tu nuevo primal): http://alex.smola.org/papers/2003/SmoSch03b.pdf

Bajo tu nuevo problema, el Lagrangiano es (con multiplicadores $\lambda_i, \mu_i, \theta_i$):

\begin{align} &L = \frac{1}{2}||w||^2 + \sum_i \xi_i \\ &+ \sum_i \lambda_i [w^T x^i + b - y_i - \epsilon - \xi_i] \\ &+ \sum_i \mu_i [y_i - w^T x^i - b - \epsilon - \xi_i] \\ &-\sum_i \theta_i \xi_i \end{align}

donde $w^T$ es la traspuesta del vector $w$. Ahora usas conceptos de dualidad para calcular $\sup_{\lambda \geq 0 , \mu \geq 0, \theta \geq 0} \left[\inf_{w, \xi, b} L\right]$. Dado que debemos tener un ínfimo sobre $w$ podemos hacer $\partial/\partial w_j$ para obtener (similar a la ecuación (8) en el papel):

$$ w = \sum_i (\mu_i - \lambda_i)x^i $$

Dado que debemos tomar un ínfimo sobre $b$, la respuesta es $-\infty$ a menos que (similar a la ecuación (7) en el papel):

$$ \sum_i (\lambda_i - \mu_i) = 0 $$

y por lo tanto debemos elegir los multiplicadores para satisfacer lo anterior y evitar un ínfimo de $-\infty$. Del mismo modo, dado que tomamos un ínfimo sobre $\xi_i$ debemos tener (similar a la ecuación (9)):

$$ 1 = \lambda_i + \mu_i + \theta_i $$

Sustituyendo estos valores de vuelta en el Lagrangiano $L$, simplificando, y tomando la maximización externa da como resultado:

\begin{align} &\mbox{Maximizar:} -\frac{1}{2}\sum_i\sum_j (\mu_i-\lambda_i)(\mu_j-\lambda_j)x_i^Tx_j - \epsilon\sum_i(\lambda_i + \mu_i) + \sum_i y^i (\mu_i-\lambda_i) \\ &\mbox{Sujeto a:} \sum_i (\lambda_i-\mu_i) = 0 \: \: , \: \: \lambda_i \geq 0 \: \: \forall i \: \: , \: \: \mu_i \geq 0 \: \: \forall i \: \: , \: \: \lambda_i + \mu_i \leq 1 \: \: \forall i \end{align}

donde la restricción $\lambda_i + \mu_i \leq 1 $ proviene de $\lambda_i + \mu_i = 1 - \theta_i$ y $\theta_i\geq 0$. La única diferencia entre este nuevo problema dual y el estándar dado en la ecuación (10) del papel es que allí, obtendríamos restricciones separadas $\lambda_i \in [0,1]$ y $\mu_i \in [0,1]$ en lugar de la restricción combinada $\lambda_i + \mu_i \leq 1$. Creo que las restricciones separadas son un poco más fáciles, por lo que tu formulación tiene un primal más simple (como también mencionó Michael Grant), pero un dual ligeramente más complicado.