¿Cuáles son las ventajas / desventajas de los métodos de punto interior sobre el método simplex para la optimización lineal?

Según tengo entendido, dado que una solución a un programa lineal siempre ocurre en un vértice de su conjunto poliédrico factible (si existe una solución y el valor óptimo de la función objetivo está limitado desde abajo, suponiendo un problema de minimización), ¿cómo puede una búsqueda a través del interior de la región factible ser mejor? ¿Converge más rápido? ¿En qué circunstancias sería ventajoso utilizar el método simplex sobre los métodos de punto interior? ¿Es uno más fácil de implementar en un código que el otro?

convex-optimization linear-programming Paul
fuente

Una de sus declaraciones es incorrecta. La solución a un problema de optimización convexa NO siempre ocurre en el límite. Tomemos, por ejemplo, , donde la solución óptima ocurre en

, que está en el interior de la región factible. Además, fuera del contexto de la programación lineal, el método simple generalmente se refiere al método simplex de Nelder-Mead, que incluso puede no converger a una solución óptima en una dimensión mayor que 1. Este método no se recomienda para la programación convexa. Edite su pregunta para mayor claridad y corrección.

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 0$

Geoff Oxberry

¿Sería más apropiado decir "optimización lineal" en lugar de "optimización convexa"?

Paul

Sí, entonces su declaración es correcta. Gracias por editar tu pregunta.

Geoff Oxberry

El problema con el método simplex es que no se puede generalizar a problemas no lineales, es decir, la mayoría de los problemas del mundo real.

Respuestas:

Basado en la experiencia personal, diría que los métodos simplex son marginalmente más fáciles de entender cómo implementar que los métodos de punto interior, basados en la experiencia personal de implementar tanto el simplex primario como un método básico de punto interior en MATLAB como parte de tomar una clase de programación lineal . Los principales obstáculos en primal simplex son asegurarse de implementar correctamente la Fase I y la Fase II, y también implementar correctamente una regla de ciclismo. Los principales obstáculos en la implementación de un método de punto interior para la programación lineal tienden a ser más sobre la implementación correcta del método iterativo y la escala del parámetro de barrera en consecuencia.

Puede encontrar una discusión más completa de los pros y los contras de cada algoritmo en un libro de texto sobre programación lineal, como Introducción a la optimización lineal de Bertsimas y Tsitsiklis. ( Descargo de responsabilidad: aprendí la programación lineal de este libro de texto, y tomé la programación lineal en el MIT de la esposa de Bertsimas). Estos son algunos de los conceptos básicos:

Pros de simplex:

Dada variables de decisión, por lo general converge en las operaciones con pivotes. $n$ $O(n)$ $O(n)$
Aprovecha la geometría del problema: visita los vértices del conjunto factible y verifica la optimización de cada vértice visitado. (En primitivo simple, el costo reducido se puede usar para esta verificación).
Bueno para pequeños problemas.

Contras de simplex:

Dadas variables de decisión, siempre puede encontrar una instancia de problema donde el algoritmo requiere operaciones y pivotes para llegar a una solución. $n$ $O(2^{n})$
No es tan bueno para grandes problemas, porque las operaciones de pivote se vuelven caras. Algoritmos de plano de corte o algoritmos de generación de columnas retrasadas como Dantzig-Wolfe a veces pueden compensar esta deficiencia.

Ventajas de los métodos de puntos interiores:

Tener una complejidad asintótica de tiempo polinomial de , donde es el número de bits de entrada al algoritmo. $O(n^{3.5}L^2\log{L}\log\log{L})$ $L$
Mejor para problemas grandes y escasos porque el álgebra lineal requerida para el algoritmo es más rápido.

Contras de los métodos de puntos interiores:

No es tan intuitivamente satisfactorio porque tienes razón, estos métodos no visitan vértices. Vagan por la región interior, convergiendo en una solución cuando tienen éxito.
Para pequeños problemas, el simplex probablemente será más rápido. (Puede construir casos patológicos, como el cubo Klee-Minty).

Geoff Oxberry
fuente

Un buen resumen De hecho, Klee-Minty parece estar diseñado para confundir los métodos de LP simplex ...

@JM Sí, ese es exactamente el punto: es una construcción explícita para mostrar que los métodos simplex no son polinomiales (aunque hay variantes que también hacen llorar a los métodos de punto interior).

Christian Clason

Gracias por esta publicación informativa. Me pregunto cuántas variables hacen que el problema sea grande. Docenas? Cientos? Miles?

KjMag

El cubo de Klee-Minty se ejecuta en <0.1 segundos en el solucionador de código abierto GLPK 4.65 simplex. (Los valores en y hacen que muchos solucionadores se comporten mal en D = 100, pero eso es diferente.) ¿Hay algún problema para el cual el método simplex funciona lentamente, digamos disperso con <1M nonzeros?

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

denis

La respuesta es fácil. Ambos (métodos de punto simple e interior) son un campo maduro desde un punto de vista algorítmico. Ambos funcionan muy bien en la práctica. La buena reputación de IPM (métodos de punto interior) se debe a su complejidad polinómica en el peor de los casos. Ese no es el caso del simplex que tiene complejidad combinatoria. Sin embargo, los programas lineales combinatorios casi nunca ocurren en la práctica. Para problemas a gran escala, la IP parece ser un poco más rápida, pero no es necesariamente la regla. En mi opinión, IP puede ser fácil de entender e implementar, pero seguro, alguien más puede estar en desacuerdo, y eso está bien. Ahora, en LP, si la solución es única, definitivamente está en un vértice (tanto IP como Simplex también funcionan bien aquí). La solución también puede estar en una cara del poliedro o en un borde, en cuyo caso, el vértice adyacente es (o los vértices son) también una solución (de nuevo, tanto IP como simplex funcionan bien). Entonces son más o menos lo mismo.

Carlos Ramirez
fuente

Me doy cuenta de que el ejemplo que di no era un programa lineal; Si observa el historial de revisiones, una versión anterior de esta pregunta solicitaba comparar el método simplex y los métodos de punto interior para problemas de optimización convexa. Di un contraejemplo para justificar las ediciones que hice y para alentar al afiche original a corregir su pregunta, lo cual hizo.

Geoff Oxberry