¿Cómo convertir un problema de optimización con restricciones en un problema sin restricciones?

Question

Supongamos que tengo un problema de optimización

$$ \mathbf{w}^* = \max_{\mathbf{w}} \sum_{i=1}^{N} (y_i - \mathbf{w}\cdot\mathbf{x}_i)^2 $$ $$\text{subject to}$$ $$\sum_{j=1}^m w_j^2 \leq \tau$$

Quiero mostrar que esto se puede escribir como

$$ \mathbf{w}^* = \max_{\mathbf{w}} \sum_{i=1}^{N} (y_i - \mathbf{w}\cdot\mathbf{x}_i)^2 + \lambda \sum_{j=1}^m w_j^2$$

¿Cuál es la intuición básica?

He hecho problemas básicos de multiplicador lagrangiano como

$$\max_{\mathbf{x}} U(\mathbf{x})$$ $$\text{subject to}$$ $$\mathbf{x}\cdot \mathbf{w} = \tau$$

En esos casos, he escrito un Lagrangiano como

$$L(\mathbf{x},\lambda) = U(\mathbf{x}) + \lambda (m - \mathbf{x}\cdot \mathbf{w})$$

Pero hay dos problemas:

1. Un Lagrangiano no es en sí mismo algo que minimice, ¿correcto? Estoy tratando de reescribir mi problema restringido como un problema no restringido.
2. Hay una desigualdad, no una igualdad. Supongo que las condiciones de Kuhn-Tucker son relevantes para esto, pero no estoy seguro de cómo.

Answer 1

Introducción de la variable de holgura $\epsilon$ se puede escribir el problema de optimización equivalente sin restricciones con el Lagrangiano

$$ L(\mathbf{w},\lambda,\epsilon) = \sum_{i=1}^{N} (y_i - \mathbf{w}\cdot\mathbf{x}_i)^2 + \lambda \left(\sum_{j=1}^m w_j^2-\tau + \epsilon^2\right) $$

NOTAS

1) Resolviendo la lagrangiana tendremos sus puntos estacionarios que deben ser calificados.

2) Analizar los valores de $\epsilon^*, \lambda^*$ podemos concluir las condiciones K-T.