Método de punto interior

Los métodos de punto interior (también denominados métodos de barrera o IPM ) son una cierta clase de algoritmos que resuelven problemas de optimización convexa lineal y no lineal .

Ejemplo de búsqueda de una solución. Las líneas azules muestran restricciones, los puntos rojos muestran soluciones iteradas.

Un método de punto interior fue descubierto por el matemático soviético II Dikin en 1967 y reinventado en los EE. UU. A mediados de la década de 1980. En 1984, Narendra Karmarkar desarrolló un método para la programación lineal llamado algoritmo de Karmarkar , que se ejecuta en un tiempo polinomial comprobable y también es muy eficiente en la práctica. Permitió soluciones de problemas de programación lineal que estaban más allá de las capacidades del método simplex. Al contrario que el método simplex, alcanza la mejor solución atravesando el interior de la región factible . El método se puede generalizar a la programación convexa basada en una función de barrera autoconcordante utilizada para codificar el conjunto convexo .

Cualquier problema de optimización convexa se puede transformar en minimizar (o maximizar) una función lineal sobre un conjunto convexo mediante la conversión a la forma de epígrafe . ^[1] La idea de codificar el conjunto factible usando una barrera y diseñar métodos de barrera fue estudiada por Anthony V. Yurii Nesterov , y Arkadi Nemirovski ideó una clase especial de tales barreras que pueden usarse para codificar cualquier conjunto convexo. Garantizan que el número de iteraciones del algoritmo está acotado por un polinomio en la dimensión y precisión de la solución. ^[2]

El avance de Karmarkar revitalizó el estudio de los métodos de punto interior y los problemas de barrera, demostrando que era posible crear un algoritmo para la programación lineal caracterizado por la complejidad polinomial y, además, competitivo con el método simplex. El método elipsoide de Khachiyan ya era un algoritmo de tiempo polinomial; sin embargo, fue demasiado lento para ser de interés práctico.

La clase de métodos de punto interior de seguimiento de ruta primal-dual se considera la más exitosa. El algoritmo predictor-corrector de Mehrotra proporciona la base para la mayoría de las implementaciones de esta clase de métodos. ^[3]

Método de punto interior dual primario para optimización no lineal

La idea del método primal-dual es fácil de demostrar para la optimización no lineal restringida . Para simplificar, considere la versión de todas las desigualdades de un problema de optimización no lineal:

minimizar ${\displaystyle f(x)}$ sujeto a ${\displaystyle c_{i}(x)\geq 0~{\text{for}}~i=1,\ldots ,m,~x\in \mathbb {R} ^{n},}$ dónde ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ,c_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} \quad (1).}$

Este problema de optimización restringido por desigualdad se resuelve luego convirtiéndolo en una función objetivo no restringida cuyo mínimo esperamos encontrar de manera eficiente. Específicamente, la función de barrera logarítmica asociada con (1) es

${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$

Aquí ${\displaystyle \mu }$es un pequeño escalar positivo, a veces llamado "parámetro de barrera". Como${\displaystyle \mu }$ converge a cero el mínimo de ${\displaystyle B(x,\mu )}$ debería converger a una solución de (1).

El gradiente de la función de barrera es

${\displaystyle g_{b}(x,\mu ):=\nabla B(x,\mu )=g(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x),\quad (3)}$

dónde ${\displaystyle g(x):=\nabla f(x)}$ es el gradiente de la función original ${\displaystyle f(x)}$, y ${\displaystyle \nabla c_{i}}$ es el gradiente de ${\displaystyle c_{i}}$.

Además de la variable original ("primaria") ${\displaystyle x}$introducimos una variable dual inspirada en el multiplicador de Lagrange${\displaystyle \lambda \in \mathbb {R} ^{m}}$

${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\forall i=1,\ldots ,m.\quad (4)}$

(4) a veces se denomina condición de "complementariedad perturbada", por su semejanza con la "holgura complementaria" en las condiciones KKT .

Tratamos de encontrar esos ${\displaystyle (x_{\mu },\lambda _{\mu })}$ para el cual el gradiente de la función de barrera es cero.

Aplicando (4) a (3), obtenemos una ecuación para el gradiente:

${\displaystyle g-A^{T}\lambda =0,\quad (5)}$

donde la matriz ${\displaystyle A}$es el jacobiano de las restricciones${\displaystyle c(x)}$.

La intuición detrás de (5) es que el gradiente de ${\displaystyle f(x)}$debe estar en el subespacio atravesado por los gradientes de las restricciones. La "complementariedad perturbada" con pequeños${\displaystyle \mu }$ (4) puede entenderse como la condición de que la solución debe estar cerca del límite ${\displaystyle c_{i}(x)=0}$, o que la proyección del gradiente ${\displaystyle g}$ en el componente de restricción ${\displaystyle c_{i}(x)}$ lo normal debería ser casi cero.

Aplicando el método de Newton a (4) y (5), obtenemos una ecuación para${\displaystyle (x,\lambda )}$ actualizar ${\displaystyle (p_{x},p_{\lambda })}$:

${\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}},}$

dónde ${\displaystyle W}$es la matriz de Hesse de${\displaystyle B(x,\mu )}$, ${\displaystyle \Lambda }$es una matriz diagonal de${\displaystyle \lambda }$, y ${\displaystyle C}$ es una matriz diagonal con ${\displaystyle C_{ii}=c_{i}(x)}$.

Debido a (1), (4) la condición

${\displaystyle \lambda \geq 0}$

debe hacerse cumplir en cada paso. Esto se puede hacer eligiendo el apropiado${\displaystyle \alpha }$:

${\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}$

"> Reproducir medios

Trayectoria de las iteraciones de x utilizando el método del punto interior.