Sólo un chico nuevo en la optimización. Es cierto que todos los problemas de optimización convexa puede ser resuelto en el polinomio tiempo de uso interior-punto de algoritmos?
Respuestas
¿Demasiados anuncios?
No, esto no es cierto (a menos que P=NP). Hay ejemplos de problemas de optimización convexa que son NP-hard. Varios NP-duro de problemas de optimización combinatoria puede ser codificado como problemas de optimización convexa sobre los conos de co-positivo (o completamente positivo) de las matrices. Ver, por ejemplo,"Aproximación del número de estabilidad de un gráfico a través de copositive de programación", SIAM J. Opt. 12(2002) 875-892 (que escribí conjuntamente con Etienne de Klerk).
Por otra parte, incluso para semidefinite problemas de programación (SDP) en su configuración general (sin extra supuestos como estricta complementariedad) no polinomio de tiempo de los algoritmos son conocidos, y hay ejemplos de Pes para que cada solución exponencial de las necesidades de espacio. Ver Leonid Khachiyan, Lorant Porkolab. "La computación Integral Puntos en Convexo Semi-algebraica de Conjuntos". Los pabellones de conveniencia en 1997: 162-171 y Leonid Khachiyan, Lorant Porkolab "Entero Optimización Convexa Semialgebraic Conjuntos". Discretos & Geometría Computacional 23(2): 207-224 (2000).
M. Ramana en "Una Exacta la dualidad de la Teoría de Semidefinite Programación y de su Complejidad Implicaciones" Programación Matemática, 77(1995) muestra que la SDP se encuentra en la intersección de la NP y co-NP, o fuera de la unión de NP y coNP, y nada mejor que este que se conoce.
En "Semidefinite de la programación y de la aritmética evaluación del circuito" Discretas Matemáticas Aplicadas, 156(2008) Sergey P. Tarasov y Mikhail N. Vyalyi muestran que la SDP puede ser utilizado para comparar los números representados por circuitos aritméticos. (Este último es considerado como uno de los problemas difíciles).
wojo
Puntos
1707
Como se ha mencionado por otro cartel, el trabajo de Nesterov y Nemirovski resume en el Interior de Punto Polinomio Algoritmos en Programación Convexa mostró que muchos de los problemas de optimización convexa (incluyendo la programación lineal (LP), de segundo orden cono de programación (SOCP) y semidefinite de programación (SDP) problemas) puede ser resuelto en el polinomio tiempo por métodos de punto interior. Estos métodos son muy importantes tanto en la teoría como en la práctica.
Un enfoque anterior que es igualmente importante en sus consecuencias teóricas fue la obra en la década de 1980 en el elipsoide algoritmo. Khachian mostró que el elipsoide algoritmo puede resolver problemas de programación lineal en el tiempo polinomio. Más tarde, Groetschel, Lovasz, y Schrijver mostró que el elipsoide algoritmo puede ser aplicado también a ciertos problemas de optimización combinatoria y demostró que el polinomio de equivalencia de la separación y de optimización. Este trabajo aparece en su libro, Geométricas y Algoritmos de Optimización Combinatoria. Aunque el elipsoide método fue muy importante desde un punto de vista teórico no es útil en la práctica.
La frase "optimización convexa" es a menudo utilizado por los autores para referirse a la clase de problemas de optimización convexa que puede ser formulada de la forma cónica LP, SOCP, o SDP problemas. No es estrictamente cierto que todos los problemas de optimización involucra la minimización de un convexo de la función objetivo a través de una convexo conjunto factible puede ser formulada de la LP, SOCP, o SDP problemas. Usted se puede imaginar matemática instancias de problemas de optimización convexa para el que no existe razonablemente estructurada problema de la representación que usted podría utilizar en decir "tengo un polinomio tiempo algoritmo para este problema."
Así que, realmente, no es correcto decir que "todos los problemas de optimización convexa puede ser resuelto en el polinomio de tiempo." Sin embargo, como Nesterov y Nemirovski show, muchos problemas de optimización convexa puede ser formulada de la LP, SOCP, o SDP y esta técnica es muy importante, tanto en la teoría y la práctica.
anjanb
Puntos
5579
Usted debe comprobar fuera de Boyd-Vanderberghe de optimización convexa, disponible de forma gratuita en Boyd de la página web de la universidad de Stanford. Este tiene una discusión de la "fácil" clases de problemas de optimización convexa (google "auto concordantes", para poco más rápido de satisfacción). Incluso para problemas lineales de punto interior métodos son lentos si la condición es muy malo (lo que a veces ocurre en la práctica; lo que ocurre más frecuentemente es que la condición no puede ser DEMOSTRADO ser pequeño, para que el programa se ejecuta más rápido en la práctica, pero no puede ser demostrado ser el polinomio de tiempo).
Peter
Puntos
1681
En muchos casos, Sí (pero ver Dima y Brian respuestas), por el trabajo de Yu. Nesterov, A. Nemirovski, como se resume en su libro Interior de Punto Polinomio Algoritmos en Programación Convexa, SIAM Estudios en Matemáticas Aplicadas, 1994. (SIAM enlace). Aquí son más recientes (2004) apuntes para un curso dado por Arkadi Nemirovski, titulado "Punto Interior Polinomio Métodos en Tiempo de Programación Convexa": Enlace PDF.
Optimización convexa especialistas esperamos que proporcionan una respuesta más matizada.
Hongli Lai
Puntos
642
