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 .
Un método de punto interior fue descubierto por el matemático soviético II Dikin en 1967 y reinventado en los Estados Unidos 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] Anthony V. Yurii Nesterov estudió la idea de codificar el conjunto factible usando una barrera y diseñar métodos de barrera , 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, mostrando 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]
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:
