El método Simplex para SDP?

Question

Sé que el método de punto interior funciona tanto para la Programación Lineal (LP) y semidefinite de programación (SDP). Mi pregunta es, ¿puede el otro método popular para la resolución de LP, es decir, el método simplex, se extendió a SDP? Si no, ¿cuál es la barrera?

Answer 1

Creo que a partir de ahora simplex métodos no se han extendido a la SDP. El problema es que la región factible de un SDP tiene una curva de límite. Así que para cualquier punto en la frontera me puede cocinar una función lineal que se minimiza allí. Así que hay conjunto infinito de posibles candidatos para la minimización de punto.

Para el LP el límite se compone de segmentos rectos, por lo que los mínimos se producen sólo en los vértices de la región factible. Como hay sólo un número finito de vértices, usted puede buscar a través de este conjunto finito para encontrar tu minimizar punto, que es lo que el algoritmo del simplex.

Answer 2

[la primera parte de esta respuesta es similar a la Dinakar Muthiah]

A la hora de optimizar una función lineal en un conjunto convexo, siempre se puede suponer que la solución óptima se encuentra en un punto extremo de la región factible (si hay varias soluciones óptimas, al menos uno es un punto extremo).

En el caso de la programación lineal, estos puntos extremos son los vértices de un poliedro, con la propiedad de que

• hay un número finito de vértices
• cada vértice admite una simple descripción algebraica (este es el concepto de base, que es esencialmente una lista de los activos de las desigualdades)

Sin embargo, para semidefinite de programación, la región factible, aunque convexo, normalmente se admite un número infinito de puntos extremos, por lo que no es evidente el equivalente al concepto de base.

Tenga en cuenta que simplex tipo de métodos (también llamado activo-conjunto de métodos) se puede generalizar a la programación cuadrática (minimización de una función cuadrática convexa más de un poliedro). Por otro lado, yo no soy consciente de que cualquier generalización para cuadráticamente limitada de programación cuadrática (QCQP, es decir, de programación cuadrática con cuadrática convexa restricciones) o de segundo orden cono de programación (una ligera extensión de QCQP), dos problema de las clases cuyas instancias pueden ser planteados como semidefinite de problemas de programación.

Answer 3

bueno, aquí hay algunas trabajar hacia un simplex-como en el enfoque a la SDP.

http://www4.ncsu.edu/~kksivara/publicaciones/rpi-coloquio.pdf

el autor dice que usted puede email él para la pre-impresión, pero las diapositivas de la charla están ahí.

Si he entendido correctamente, es simple-como en el sentido de que es trabajar con matrices que no son de rango completo. Así que en lugar de variables que entran y salen de la base, como en LP, usted podría intercambiar las columnas dentro y fuera. No simplex-como en el sentido geométrico de pasar de punto extremo a punto extremo en un poliedro.

X puede ser factorizados como X=P^TDP donde P no es de rango completo por lo que el problema se reduce a encontrar el derecho de P. La charla va en cómo actualizar las columnas de P de forma iterativa hasta que el criterio de optimalidad (tener un psd de la holgura de la matriz) se cumple. Las columnas con el negativo de la reducción de los costos en cualquier iteración son los vectores propios asociados con la negativa de los autovalores de la indefinida holgura de las matrices.

Si yo lo he entendido todo correctamente.

Answer 4

Ver: semidefinite método simplex. A. I. Kosolap, A. S. Peretyatko "Numérica de la eficiencia de los métodos de semidefinite optimización" "Diario de Automatización y Ciencias de la Información" de 2014.