¿Por qué los métodos de puntos interiores son difíciles de calentar?

10

A menudo encuentro el adagio general de que los métodos de puntos interiores son difíciles de iniciar. ¿Hay una explicación intuitiva detrás de este consejo? ¿Hay situaciones en las que uno puede esperar beneficios del arranque en caliente en un método de punto interior? ¿Alguien puede recomendar algunas referencias útiles sobre el tema?

optimization constrained-optimization Christopher Johnson
fuente

Respuestas:

11

Los métodos de puntos interiores funcionan siguiendo el camino central hacia una solución óptima. Cuando cambia la función objetivo, la solución óptima de la versión anterior del problema está lejos de la ruta central para el nuevo problema, por lo que se necesitan varias iteraciones para volver a la ruta central y, además, tiene que volver a estar bastante bien centrado. solución. Luego, debe avanzar por el camino hacia una nueva solución óptima. También podría comenzar el método de punto interior desde un punto arbitrario.

En comparación, el método simplex (primario o dual) se mueve de vértice a vértice del conjunto factible. En el caso típico, un cambio razonablemente pequeño en el objetivo dará como resultado una nueva solución óptima que está a solo unos pocos pivotes simples.

... agregado a la explicación intuitiva anterior para dar más detalles ...

En la práctica computacional, la experiencia simplemente no ha mostrado ningún beneficio sustancial al iniciar en caliente los métodos de punto interior primario-dual. No es una característica de códigos ampliamente utilizados como CPLEX y Gurobi (las compañías que producen estos paquetes seguramente agregarían dicha característica si valiera la pena), y hay relativamente pocos documentos que discutan estrategias para métodos de punto de inicio cálido. .

Dos referencias que recomendaré son:

EA Yildirim y S. Wright. Estrategias de arranque en caliente en métodos de punto interior para programación lineal. SIAM Journal on Optimization 12: 782-810, 2002. Este documento ofrece algunos límites teóricos agradables sobre algunas estrategias de inicio cálido. Ver http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf

Un artículo posterior escrito por Yildirim da algunos resultados computacionales, pero los autores admiten que simplemente el arranque en frío suele ser más rápido en sus pruebas que el arranque en caliente:

E. John y EA Yildirim. Implementación de estrategias de arranque en caliente en métodos de punto interior para programación lineal en dimensión fija. Optimización computacional y aplicaciones. 41: 151-183, 2008. Ver http://link.springer.com/article/10.1007/s10589-007-9096-y

Brian Borchers
fuente
Tengo que decir que siento que tu explicación es un poco escasa. Para un problema que está un poco mal condicionado, encontrar un punto factible ya es un problema en sí mismo y la mayoría de los métodos usan métodos de "Fase I" para encontrar este primer punto factible. Todavía no me queda claro por qué no puede usar un punto factible para saltear al menos esa fase, si no es para garantizar realmente el éxito del método.
olamundo
En realidad, la mayoría de las implementaciones de métodos de puntos interiores primarios-dobles utilizan un punto de partida inviable (con respecto a las restricciones de igualdad) y trabajan simultáneamente en la factibilidad y la optimización. No hay una fase separada I.
Brian Borchers