Un algoritmo de programación lineal homogéneo y autidual de O(√nL) iteraciones

Presentamos un algoritmo de programación lineal (LP) homogéneo y autidual de O(√nL) iteraciones. El algoritmo posee las siguientes características: • Resuelve el problema de programación lineal sin ninguna suposición de regularidad con respecto a la existencia de soluciones óptimas, factibles o interiormente factibles. • Puede comenzar en cualquier par primal-dual positivo, factible o no factible, cerca del rayo central del ortante positivo (cono), y no utiliza ningún parámetro de penalización grande M ni cota inferior. • Cada iteración resuelve un sistema de ecuaciones lineales cuya dimensión es casi la misma que la resuelta en los algoritmos de punto interior (primal-dual) estándar. • Si el problema de programación lineal tiene solución, el algoritmo genera una secuencia que se aproxima a la factibilidad y óptima simultáneamente; si el problema es no factible o ilimitado, el algoritmo detectará correctamente la no factibilidad para al menos uno de los problemas primal y dual.