Pregunta sobre la complejidad del método simplex

Question

Así que sé que en general el método simplex para la programación lineal y cuadrática convexa puede requerir un tiempo exponencial. Pero suponiendo un programa cuadrático semidefinitivo positivo que es resoluble por el método simplex, entonces el problema está definitivamente en P, ¿no?

La razón por la que lo pregunto: estoy trabajando en la teoría de la complejidad. Y creo que he encontrado una reducción de un problema a un problema cuadrático semidefinido positivo PERO la solución sólo es válida si el óptimo devuelto está en un vértice de la región factible. Así que eso deja fuera la solución con un método de puntos interiores ya que el mínimo se puede obtener trivialmente en el centro de la región factible y tal vez en otros puntos también. Como el método simplex opera en los vértices, entonces sé que una vez que se encuentra el óptimo, entonces está en un punto que realmente me interesa.

Suponiendo que la reducción es adecuada y siempre da lugar a una respuesta correcta: ¿es la reducción al método simplex una condición suficiente para demostrar la pertenencia a P? ¿O alguien tiene una buena referencia de métodos eficientes de punto exterior para esta clase de problemas? ¿Hay algún otro método para programas cuadráticos que esté pasando por alto? ¿O estoy básicamente atascado en probar que el número de iteraciones es polinómico para este programa específico? ¿Esta pregunta es más adecuada para otro sitio de intercambio de pilas?

Answer 1

Creo que puedes estar entendiendo mal cómo se utiliza el método simplex para resolver programas cuadráticos. No opera sobre los vértices de la región factible del programa cuadrático original; opera sobre los vértices de la región factible de las condiciones KKT para el programa cuadrático original. Esto se debe a que 1) las condiciones KKT son suficientes y necesarias para los problemas convexos, y 2) para un programa cuadrático las condiciones KKT son lineales (bueno, excepto la holgura complementaria, pero eso se puede manejar fácilmente). Por lo tanto, la resolución del programa cuadrático convexo original se reduce a la resolución de sus condiciones KKT lineales, y el método simplex se utiliza para manejar este último. (Véase, por ejemplo, aquí .)

Todo esto significa que el método simplex dará como resultado un vértice de la región factible de las condiciones KKT y no necesariamente un vértice de la región factible del programa cuadrático original.

Sin embargo, si el programa cuadrático tiene la solución óptima en un vértice, significa que si se utiliza cualquiera de los algoritmos de programación lineal, el algoritmo dará como resultado ese vértice como solución óptima. (Bueno, suponiendo que no haya múltiples soluciones óptimas.) Así que si usas uno de los algoritmos de tiempo polinómico, ese algoritmo dará como resultado el vértice que quieres en tiempo polinómico. Por ejemplo, el método del elipsoide funcionará bien, como en esta respuesta reciente en Math Overflow.

Añadido : Si el problema de programación cuadrática tiene múltiples soluciones óptimas, y se utiliza, por ejemplo, un algoritmo de punto interior en tiempo polinómico para encontrar una de ellas, no necesariamente encontrará una de las soluciones óptimas de vértice. Sin embargo, hay un algoritmo de tiempo polinómico debido a Berkelaar, Jansen, Roos y Terlaky por encontrar una base óptima (que le dará un vértice óptimo) a partir de una solución interior óptima de un programa cuadrático. Así que todo eso junto te llevará a un vértice óptimo en tiempo polinómico.