Técnicas de búsqueda de arcos para métodos de puntos interiores

Título original:

Arc-Search Techniques for Interior-Point Methods

Contenido del libro:

Este libro aborda un área importante de la optimización numérica, denominada método del punto interior. Este tema ha sido popular desde la década de 1980, cuando la gente se dio cuenta gradualmente de que todos los algoritmos simplex no eran convergentes en tiempo polinómico y se pudo demostrar que muchos algoritmos de punto interior convergen en tiempo polinómico.

Sin embargo, durante mucho tiempo hubo una gran diferencia entre los límites polinómicos teóricos de los algoritmos de punto interior y la eficiencia de estos algoritmos. Las estrategias que eran importantes para la eficiencia computacional se convirtieron en barreras en la prueba de buenos límites polinómicos. Cuanto más se utilizaban las estrategias en los algoritmos, peores eran los límites polinómicos.

Para agravar aún más el problema, el algoritmo predictor-corrector (MPC) de Mehrotra (el algoritmo de punto interior más popular y eficiente hasta hace poco) utiliza todas las estrategias buenas y no consigue demostrar la convergencia.

Por lo tanto, MPC no tiene polinomialidad, un problema crítico con el método simplex. Este libro analiza los últimos avances que resuelven el dilema.

Consta de tres partes principales. La primera, que incluye los capítulos 1, 2, 3 y 4, presenta algunos de los algoritmos más importantes durante el desarrollo del método del punto interior en torno a la década de 1990, la mayoría de ellos ampliamente conocidos. El objetivo principal de esta parte es explicar el dilema descrito anteriormente analizando los límites polinómicos de estos algoritmos y resumiendo la experiencia computacional asociada a ellos.

La segunda parte, que incluye los capítulos 5, 6, 7 y 8, describe cómo resolver el dilema paso a paso utilizando técnicas de búsqueda de arcos. Al final de esta parte, se presenta un algoritmo muy eficiente con el límite polinómico más bajo. La última parte, que incluye los capítulos 9, 10, 11 y 12, extiende las técnicas de búsqueda de arcos a algunos problemas más generales, como la programación cuadrática convexa, el problema de complementariedad lineal y la programación semidefinida.