¿Qué se puede resolver con la programación semidefinida que no se puede resolver con la programación lineal?

9

Estoy familiarizado con los programas lineales en que pueden resolver problemas con funciones objetivas lineales y restricciones lineales. Pero, ¿qué puede resolver la programación semidefinida que la programación lineal no puede? Ya sé que los programas semidefinidos son una generalización de programas lineales.

Además, ¿cómo se reconoce un problema que se puede resolver con la programación semidefinida? ¿Cuál es un problema típico para el que se utiliza la programación semidefinida que no se pudo resolver mediante la programación lineal?

Muchas gracias por cualquier respuesta.

linear-programming convex-optimization semidefinite-programming user11094
fuente
2
¿Quizás puedas hacer tu pregunta más precisa? Después de todo, la programación lineal es -completa. PAGS
Kristoffer Arnsfelt Hansen
55
@KristofferArnsfeltHansen Nunca dejo de preguntarme por qué la gente sigue planteando este hecho en discusiones similares. La completitud de P es irrelevante a menos que estemos hablando de separar P de L o NC; si estamos hablando de polytime, todo en P es "P-complete". Para sugerir una respuesta a OP: una vez que arregle una codificación lineal de un problema (es decir, escriba como optimizar una función lineal sobre un politopo), tiene mucho sentido preguntar si un LP / SDP polisize puede resolver el problema.
Sasho Nikolov

Respuestas:

18

Un problema típico es MaxCut: genera un corte en un gráfico que (aproximadamente) maximiza el número de bordes cortados. Goemans y Williamson mostraron que un SDP aproxima el valor de MaxCut a un factor de al menos 0.878. Recientemente, Chan, Lee, Raghavendra y Steurer mostraron que para una codificación lineal natural del problema MaxCut, todos los LP de tamaño polinómico alcanzan una aproximación no mejor que 0.5.

Es difícil decir de manera concisa qué tipo de problemas generalmente se benefician de un SDP. Un enfoque sistemático para construir relajaciones SDP es a través de jerarquías, la más poderosa de las cuales es la jerarquía de Lasserre: vea la encuesta de Rothvoß para una buena introducción. En este momento, hay demasiados ejemplos de éxitos de SDP en optimización para enumerar. Además, Raghavendra demostró que un SDP particular brinda la mejor aproximación a todos los problemas de MaxCSP, si la conjetura de Unique Games es cierta.

Consulte los libros de Gaertner y Matousek , capítulos 6 y 13 del libro de Willimson y Shmoys , la encuesta de Lovasz .

Sasho Nikolov
fuente
12

Para muchos problemas de optimización combinatoria (por ejemplo, Max-Cut), la programación semidefinida produce relajaciones mucho más fuertes que la relajación LP de las formulaciones IP. Esto permite el diseño de algoritmos de aproximación y de algoritmos exactos que son más eficientes que sus contrapartes lineales debido a la mejor calidad de los límites. Se pueden encontrar ejemplos en la tesis de Habilitación de Christoph Helmberg , esta encuesta y esta página del curso .

Otra secuencia reciente de resultados espectaculares que hace uso de la programación semidefinida es la aplicación de álgebras de bandera de Razborov para probar resultados en problemas de tipo Turan (ver esta encuesta y el proyecto de bandera ).

Thomas Kalinowski
fuente