Barreras auto concordantes y su aplicación en el método de punto Interior: primal dual

Abstract

En el presente trabajo de investigación haremos una presentación de la teoría de funciones auto concordantes y su aplicación en el análisis de la convergencia del método de punto interior: primal dual. Los métodos de punto interior se caracterizan porque hacen uso del método de Newton para minimizar un problema de programación lineal irrestricto, el cual tiene complejidad polinomial. El análisis clásico de convergencia del método de Newton depende de la convexidad fuerte de la función objetivo que incluye constantes desconocidas en la mayor parte de problemas y de la constante de Lipchtz para la Hessiana de la función objetivo. En el trabajo se ha usado la teoría de funciones auto concordantes para el análisis de la convergencia del método de Newton y consecuentemente del método de punto interior primal dual. En el marco teórico se presenta la teoría básica y fundamental de las funciones o barreras auto concordantes comenzando con funciones de una sola variable y generalizando la definición para una función de varias variables. Se ha demostrado la convergencia y la complejidad polinomial del método de Newton que no depende de la función objetivo ni de constantes desconocidas como es el caso del análisis de convergencia tradicional. Se presenta el método de punto interior primal dual y se establece su convergencia y complejidad polinomial en base a la convergencia y complejidad polinomial del Método de Newton y el Método Barrera.