Un abordaje para el cálculo de una base del precondicionador separador en un Método de Puntos Interiores

Abstract

En éste trabajo se analiza el método predictor-corrector de Mehrotra, para resolver problemas de programación lineal. El punto clave del método es la resolucin de un sistema normal aumentado, el que proporciona la direccin de Newton. El inconveniente encontrado aqu es que este sistema es mal condicionado a medida que se hace más iteraciones y se esté más prximo del punto ptimo. Por tal motivo, basados en la propuesta de Porrio Suæagua, se procedi a precondicionar dicho sistema, mediante una técnica que utiliza las componentes básicas y no básicas del sistema por medio de la estrategia de pivoteamiento parcial, para luego resolver el sistema usando métodos iterativos, como el método de gradientes conjugados. El algoritmo de Mehrotra, junto con la estrategia obtenida a partir de la propuesta de Porrio Suñagua, fue implementado en Matlab. Varios experimentos se hicieron mostrando que este algoritmo precondicionado es más eficiente que otros métodos de puntos interiores.