Notas para contenedor de docker:
Comando de docker para ejecución de la nota de forma local:
nota: cambiar <ruta a mi directorio> por la ruta de directorio que se desea mapear a /datos dentro del contenedor de docker.
docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0password para jupyterlab: qwerty
Detener el contenedor de docker:
docker stop jupyterlab_numericalDocumentación de la imagen de docker palmoreck/jupyterlab_numerical:1.1.0 en liga.
En esta nota se consideran resolver problemas de optimización con restricciones lineales de igualdad de la forma:
$$\min f_o(x)$$con variable de optimización $x \in \mathbb{R}^{n}$ y $A \in \mathbb{R}^{p \times n}, b \in \mathbb{R}^p$ conocidos.
Se asume lo siguiente:
$f_o:\mathbb{R}^n \rightarrow \mathbb{R}$ convexa y $\mathcal{C}^2(\text{dom}f_o)$.
$rank(A) = p < n$: tenemos menos restricciones que variables y los renglones de $A$ son linealmente independientes.
Existe un punto óptimo $x^*$ por lo que el problema tiene solución y el valor óptimo se denota por $p^* = f_o(x^*) = \inf f_o(x)$.
Los puntos iniciales $x^{(0)}$ de los métodos iterativos están en $\text{dom}f_o$ y los conjuntos $f_o(x^{(0)})$-subnivel son conjuntos cerrados.
Ver 1.4.Polinomios_de_Taylor_y_diferenciacion_numerica y 4.1.Optimizacion_numerica_y_machine_learning para definiciones utilizadas en esta nota.
El problema del inicio lo nombramos primal (se recomienda leer el ápendice de esta nota donde se dan definiciones utilizadas en esta sección.)
En el caso de optimización sin restricciones la condición que nos ayudó a determinar si un punto $x^*$ es óptimo fue $\nabla f(x^*) = 0$ (ver definiciones al final de 4.1.Optimizacion_numerica_y_machine_learning y la nota 4.2.Algoritmos_para_UCO) . Tal condición es necesaria y suficiente por la suposición que $f_o$ es convexa diferenciable. Esta condición es en general un conjunto de $n$ ecuaciones no lineales en $n$ variables que resuelve el problema sin restricciones.
Para los problemas de optimización convexos con restricciones lineales o afines de igualdad las condiciones de Karush-Kuhn-Tucker de optimalidad constituyen un conjunto de condiciones necesarias y suficientes que ayudan a resolver al problema primal. Tales condiciones KKT de optimalidad para este problema son:
$$Ax^* = b$$Comentarios:
La ecuación de factibilidad primal ($1$a ecuación anterior) es una ecuación lineal.
La ecuación de factibilidad dual ($2$a ecuación anterior) en general es una ecuación no lineal.
Por las condiciones KKT de optimalidad: $x^* \in \text{dom}f_o$ es óptimo si y sólo si $Ax^*=b$ y $\exists \nu^* \in \mathbb{R}^p$ tal que $\nabla f_o(x^*) + A^T\nu^*=0$. Entonces resolver el sistema de ecuaciones anteriores para las variables $x^*$ y $\nu ^*$ equivale a resolver el problema de optimización primal.
Los métodos para resolver el problema primal consisten en:
En esta nota utilizamos el enfoque número $3$: extender el método de Newton. Para una revisión de los otros dos enfoques ver liga2
El método de Newton sin restricciones revisado en 4.2.Metodo_de_Newton_Python se extiende para el caso de restricciones de igualdad considerando:
El punto inicial $x^{(0)}$ debe ser factible: $x^{(0)} \in \text{dom}f_o$ y $Ax^{(0)}=b$ (aunque esta restricción puede eliminarse con el método de Newton para puntos no factibles, ver 4.4.Metodo_de_Newton_para_puntos_iniciales_no_factibles_Python para una implementación).
El paso de Newton $\Delta x_{\text{nt}}$ debe modificarse de modo que satisfaga la ecuación de factibilidad primal.
El método de Newton con punto inicial factible puede obtenerse de varias formas. Ejemplos son:
Aproximación de segundo orden vía el teorema de Taylor.
Linearización de las condiciones KKT de optimalidad vía el teorema de Taylor.
Para una introducción al teorema de Taylor ver 1.4.Polinomios_de_Taylor_y_diferenciacion_numerica.
Supóngase que $x$ es punto factible del problema primal. Por las suposiciones del inicio se cumple por el teorema de Taylor:
$$\hat{f}_o(x+v) = f_o(x) + \nabla f_o(x)^Tv + \frac{1}{2}v^T \nabla ^2 f_o(x) v$$es una aproximación de segundo orden a $f_o(x)$ con centro en $x$ y variable $v$.
El método de Newton para puntos factibles consiste en considerar resolver el problema:
para la variable de optimización $v \in \mathbb{R}^n$. Tal problema es un problema de optimización convexa con función objetivo cuadrática.
Diferentes condiciones determinan si el problema anterior tiene solución y si es única. Tales condiciones tienen una relación directa con las condiciones KKT de optimalidad que son:
$A(x + v^*) = b$ y por tanto $Av^*=0$ (factibilidad primal) y $\nabla ^2f_o(x) v^* + \nabla f_o(x) + A^T w^* = 0$ para $w^*$ variable óptima dual asociada al problema.
Reescribiendo las condiciones anteriores en un sistema nombrado sistema KKT para el problema primal con matriz KKT se tiene:
$$\begin{array}{l} \left[ \begin{array}{cc} \nabla^2f_o(x) & A^T\\ A & 0 \end{array} \right] \cdot \left[\begin{array}{c} v\\ w \end{array} \right] = \left[\begin{array}{c} -\nabla f_o(x)\\ 0 \end{array} \right] \end{array} $$Comentarios:
Considérese la aproximación lineal por el teorema de Taylor a las condiciones KKT de optimalidad del problema optimización primal:
Sustitúyase la variable $x^*$ por $x + \Delta x_{\text{nt}}$ y $\nu ^*$ por $w$. Asimismo reemplácese el gradiente de $f_o$ de la ecuación de factibilidad dual ($2$a ecuación anterior) por su aproximación lineal por Taylor con centro en $x$. Se tiene:
Como $Ax = b$ implica $A \Delta x_{\text{nt}} =0$ se tiene el sistema de ecuaciones:
O escrito en notación matricial:
Que es el sistema nombrado sistema KKT para el problema primal con matriz KKT. El paso de Newton $\Delta x_{\text{nt}}$ es la solución única al sistema anterior para el caso de la matriz KKT no singular.
Se define el decremento de Newton para problemas con restricciones de igualdad como la cantidad:
Como en el caso sin restricciones, ver 4.2.Metodo_de_Newton_Python, el decremento de Newton tiene propiedades que nos ayudan al criterio de paro, resultados de convergencia del método y al método de búsqueda de línea por backtracking como son:
$\frac{1}{2} \lambda ^2 (x)$ estima $f(x)-p^*$.
$\lambda(x) = || \Delta x_{\text{nt}} ||_{\nabla ^2 f_o(x)}$ es la norma del paso de Newton en la norma cuadrática definida por la Hessiana.
En el método de búsqueda de línea por backtracking $-\lambda (x) ^2$ es la derivada direccional de $f$ en $x$ en la direccióin de $\Delta x_{\text{nt}}$:
Supóngase que $Ax=b$ con $x \in \mathbb{R}^n$. Una dirección $v \in \mathbb{R}^n$ se nombra dirección factible si $Av=0$.
Obs: obsérvese que si $v$ es dirección factible también lo es $x + tv$ con $t \in \mathbb{R}$.
Adicionalmente $v$ es dirección de descenso para $f_o$ en $x$ si para valores $t$ pequeños positivos se tiene: $f(x +tv) < f(x)$.
El paso de Newton $\Delta x_{\text{nt}}$ siempre es dirección de descenso factible si $x$ no es óptima pues $A \Delta x_{\text{nt}} =0$ y $\nabla f_o(x)^T\Delta x_{\text{nt}} = - \frac{\lambda(x)^2}{2} <0$.
Tanto el paso de Newton como el decremento de Newton son invariantes ante transformaciones afines. Por ejemplo para el paso de Newton: si $T \in \mathbb{R}^{n \times n}$ es no singular y $\hat{f}_o: \mathbb{R}^n \rightarrow \mathbb{R}$ está definida como $\hat{f}_o(\hat{x}) = f_o(T^{-1}x)$ entonces se puede probar que $\Delta \hat{x}_{\text{nt}} = T^{-1} \Delta x_{\text{nt}}$ con $\Delta x_{\text{nt}}$ el paso de Newton para $f_o$ en $x$ y $\hat{w} = w$. Esto indica que los pasos de Newton están relacionados por la misma transformación lineal $T$, de hecho: $x + \Delta x_{\text{nt}} = T(\hat{x} + \Delta \hat{x}_{\text{nt}})$.
Obs: en este caso se considera el problema primal transformado:
$$\min \hat{f}(\hat{x})$$Algoritmo de Newton con punto inicial factible para problemas de optimización con restricciones de igualdad lineales
Dados un punto inicial $x$ en $\text{dom}f_o$ con $Ax=b$ y una tolerancia $\epsilon >0$.
Repetir el siguiente bloque para $k=0,1,2,...$
- Calcular la dirección de descenso de Newton $\Delta x_{\text{nt}}$ y el decremento de Newton al cuadrado: $\lambda^2 (x)$.
- Criterio de paro: finalizar el método si $\frac{\lambda^2(x)}{2} \leq \epsilon$.
- Búsqueda de línea. Elegir un tamaño de paso $t > 0$ (usar el cálculo de $\lambda^2 (x)$ del paso anterior).
- Hacer la actualización: $x = x + t\Delta x_{\text{nt}}$.
hasta convergencia (satisfacer criterio de paro).
Comentarios:
Este método es de descenso factible pues todas las iteraciones son factibles y $f(x^{(k+1)}) < f(x^{(k)})$ (excepto si $x^{(k)}$ es óptimo).
La convergencia del método requiere que la matriz KKT sea no singular, que la inversa de la matriz KKT sea acotada por arriba, $\nabla ^2 f_o$ sea una función que satisfaga la condición de Lipschitz, ver Lipschitz_continuity y las suposiciones del inicio de la nota.
En construcción... ver 4.4.Metodo_de_Newton_para_puntos_iniciales_no_factibles_Python para una implementación
A partir de esta sección consideramos problemas de optimización de la forma:
donde: $f_o$, $f_i \forall i=1,\dots,m$ y $h_i \forall i=1,\dots,p$ son funciones diferenciables. Este problema lo nombramos problema primal de optimización.
Obs: obsérvese que no estamos asumiendo que tenemos un problema convexo.
Definimos la función Lagrangiana asociada al problema de optimización (primal) como: $\mathcal{L}: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$ con:
$$\mathcal{L}(x, \lambda , \nu) = f_o(x) + \displaystyle \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)$$y $\text{dom} \mathcal{L} = \mathcal{D} \times \mathbb{R}^m \times \mathbb{R}^p$ donde: $\mathcal{D}$ es el dominio del problema de optimización. Ver el apéndice de la nota 4.1.Optimizacion_numerica_y_machine_learning para definición del dominio de un problema de optimización.
Comentarios:
$\lambda _i$ se le nombra multiplicador de Lagrange asociado con la $i$-ésima restricción de desigualdad $f_i(x) \leq 0$.
$\nu_i$ se le nombra multiplicador de Lagrange asociado con la $i$-ésima restricción de igualdad $h_i(x)=0$.
Los vectores $\lambda = (\lambda_i)_{i=1}^m$ y $\nu = (\nu_i)_{i=1}^p \in \mathbb{R}^p$ se les nombran variables duales o vectores de multiplicadores de Lagrange asociados con el problema de optimización. El vector $x \in \mathcal{D}$ se le nombra variable primal.
Consideramos en lo que continúa la restricción $\lambda_i \geq 0 \forall i=1,\dots, m$.
Podemos interpretar a la función Lagrangiana como una subestimación relajada del problema primal de optimización. Tal problema puede reescribirse en uno sin restricciones de la forma:
donde:
Obs: para ver la equivalencia entre este problema sin restricciones y el primal piénsese en que a la función $f_o$ se le está añadiendo una regularización en donde se penaliza fuertemente a los vectores $x$ que no cumplen con $f_i(x) \leq 0$ o $h_i(x) = 0$. Ver 4.3.Minimos_cuadrados_R para regularización en un problema de mínimos cuadrados y la relación de la regularización con problemas bi-criterion de optimización.
Como $\lambda_i \geq 0$ se tiene:
$$\lambda_i f_i(x) \leq I_{-}(f_i(x)) \quad \forall i=1,\dots,m$$La Lagrangiana $\mathcal{L}(x, \nu) = f_o(x) + \displaystyle \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^m \nu_i h_i(x)$ entonces cumple $\mathcal{L}(x, \nu) \leq f_o(x) + \displaystyle \sum_{i=1}^m I_{-}(f_i(x)) + \sum_{i=1}^p I_o(h_i(x))$ $\forall (x, \nu ) \in \text{dom}\mathcal{L}$. Esto es, $\mathcal{L}(x,\nu)$ subestima a $f_o(x) + \displaystyle \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^m \nu_i h_i(x)$ .
La función dual de Lagrange se define como $g: \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$ con:
$$g(\lambda, \nu) = \displaystyle \inf_{x \in \mathcal{D}} \mathcal{L}(x,\lambda, \nu)$$Comentarios:
Recuérdese que $\inf$ es el máximo de las cotas inferiores, ver 1.3.Condicion_de_un_problema_y_estabilidad_de_un_algoritmo para definición de supremo e ínfimo. En esta definción se está tomando el ínfimo de la Lagrangiana para cada punto $x \in \mathcal{D}$ (ínfimo puntual).
Por la definición de la función dual de Lagrange y el punto anterior, se tiene: $g(\lambda, \nu) \leq \mathcal{L}(\tilde{x},\lambda, \nu)$ para $\tilde{x}$ factible.
La función dual de Lagrange para cada par $(\lambda, \nu)$ con $\lambda \geq 0$ da una subestimación de $p^*$, el valor óptimo del problema primal. Esto es: $g(\lambda, \nu) \leq p^*$ para $\lambda \geq 0, \nu \in \mathbb{R}^p$ y $p^*$ valor óptimo del problema de optimización primal.
Si la Lagrangiana no es acotada por debajo entonces la función dual de Lagrange se asigna $-\infty$.
Se prueba que la función dual de Lagrange siempre es una función cóncava.
Asociado a todo problema de optimización existe su problema dual el cual se define como:
$$\displaystyle \max g(\lambda,\nu)$$Comentarios:
Si $(\lambda, \nu)$ satisface $\lambda \geq 0$ y $g(\lambda, \nu)$ no es $-\infty$ la pareja $(\lambda, \nu)$ se nombra dual factible.
El valor óptimo del problema dual se denota con $d^*$. El valor óptimo se alcanza si existen $(\lambda^*, \nu^*)$ tales que $d^* = g(\lambda^*, \nu^*)$.
La pareja $(\lambda^*, \nu^*)$ se nombra óptimo dual o pareja óptima de multiplicadores de Lagrange si satisface:
Para distinguir a los óptimos duales de los puntos óptimos $x^*$ del problema primal, a éste últimos se les nombra óptimos primales.
El problema dual tiene como interpretación la mejor cota inferior de la función Lagrangiana como función de $x$ que se obtiene con la función dual de Lagrange.
El problema dual de Lagrange siempre es un problema de optimización convexo aún si el problema primal no es convexo.
A la diferencia $p^* - d^*$ se le nombra optimal duality gap. Si es positiva se tiene un problema de optimización en el que se cumple dualidad débil. Si es igual a cero se tiene un problema de optimización en el que se cumple dualidad fuerte.
En un problema de optimización en el que los valores óptimos primal y dual se alcanzan y en el que se cumple dualidad fuerte se tiene la propiedad que el punto óptimo primal minimiza $\mathcal{L}(x,\lambda^*, \nu^*)$ pues:
$$f_o(x^*) = p^* = d^* = g(\lambda^*, \nu^*) = \inf_{x \in \mathcal{D}} \mathcal{L}(x, \lambda^*, \nu^*)$$Comentario: lo anterior prueba que $\lambda^*_i f_i(x^*)=0 \quad \forall i=1, \dots, m$. Tal ecuación se conoce con el nombre de holgura complementaria. La holgura complementaria indica que si el $i$-ésimo multiplicador de Lagrange es positivo entonces la $i$-ésima función de restricción de desigualdad $f_i$ es activa:
Sean $x^*, (\lambda^*, \nu^*)$ un par primal-dual de puntos óptimos en los que la optimal duality gap es cero o bien: $d^* = p^*$. Entonces $x^*$ minimiza $\mathcal{L}(x, \lambda^*, \nu^*)$ y por factibilidad y holgura complementaria se cumple:
$$\nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) = \nabla f_o(x^*) + \displaystyle \sum_{i=1}^m \lambda^*_i f_i(x^*) + \sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0$$Las $5$ condiciones anteriores se nombran condiciones KKT de optimalidad para el problema de optimización del inicio.
Comentarios:
Las condiciones KKT de optimalidad se satisfacen para cualquier problema de optimización con función objetivo y funciones de restricción diferenciables evaluadas en un par primal-dual de puntos óptimos en el que se cumple la dualidad fuerte.
La notación $\nabla_x$ se refiere a la derivada de $\mathcal{L}$ respecto a la variable $x$.
Son condiciones necesarias.
La ecuación $h_i(x^*)=0 \forall i=1,\dots,p$ y $f_i(x^*) \leq 0 \forall i=1,\dots,m$ se nombran ecuaciones de factibilidad primal y $\nabla_x \mathcal{L}(x^*,\lambda^*, \nu^*)=0$ se nombra ecuación de factibilidad dual.
Si el problema primal es convexo, esto es, $f_o, f_1, \dots, f_m$ son funciones convexas y $h_i$ es afín $\forall i,\dots, p$ entonces las condiciones KKT son suficientes para puntos primal-dual óptimos:
Sean $\tilde{x}, \tilde{\lambda}, \tilde{\nu}$ puntos que satisfacen las condiciones KKT de optimalidad:
$$\nabla_x \mathcal{L}(\tilde{x}, \tilde{\lambda}, \tilde{\nu}) = \nabla f_o(\tilde{x}) + \displaystyle \sum_{i=1}^m \tilde{\lambda}_i f_i(\tilde{x}) + \sum_{i=1}^p \tilde{\nu}_i \nabla h_i(\tilde{x}) = 0$$entonces el par $(\tilde{x},\tilde{\nu})$ son puntos primal-dual óptimos y en el problema de optimización se cumple la dualidad fuerte.
Comentario: en algunos casos especiales es posible resolver las condiciones KKT de optimalidad de manera analítica y en general muchos algoritmos de optimización resultan o pueden interpretarse como métodos que las resuelven.
Referencias: