En programación semidefinida no disponemos de un conjunto convexo de dimensión completa para utilizar el método elipsoidal

Question

En el capítulo 2 de la obra de Gärtner & Matousek Algoritmos de aproximación y programación semidefinida Al resolver un programa semidefinido, los autores desean utilizar el método del elipsoide. Para utilizar el método elipsoidal debemos tener un conjunto convexo de dimensión completa. Utilizando la norma de Frobenious, el conjunto de soluciones de un programa semidefinido es, por supuesto, un conjunto convexo. Pero, debido a las igualdades lineales, no es de dimensión completa.

Así, los autores consideran el espacio de soluciones afín del sistema de igualdades lineales en el programa semidefinido. Y afirman que podemos restringir el espacio factible a este espacio, por lo que es de dimensión completa.

Mi problema es que, este espacio solución afín cómo puede ser de dimensión completa. Realmente no es de dimensión completa, ya que es la intersección de conjuntos afines y cada conjunto afín debe ser de dimensión completa si la intersección es de dimensión completa.

Answer 1

Parece referirse a esta cita de la página 21 del libro:

Este conjunto C es convexo pero no completo lineales del programa semidefinido. Pero como la solución afín L del conjunto de igualdades lineales puede calcularse en en tiempo polinómico mediante la eliminación gaussiana, podemos restringir C a este espacio y, entonces, tendremos una solución de dimensión completa. este espacio y entonces tenemos un conjunto convexo de dimensión completa. Técnicamente, esto puede hacerse mediante una transformación de coordenadas explícita o tratarse implícitamente. de coordenadas explícita, o tratarse implícitamente (haremos esto último).

Cuando se hace una pregunta sobre una parte concreta de un libro o artículo, lo mejor es citar el material y proporcionar una cita completa (incluido el número de página). Si no es esto a lo que se refiere, por favor, indíquenos una cita del libro en lugar de dar su interpretación (posiblemente incorrecta) de lo que han escrito los autores.

De hecho, esto se dice muy claramente en el libro. Se puede abordar el problema expresando el conjunto de soluciones en $Ax=b$ en términos de un punto del conjunto y de una combinación lineal de vectores base para el espacio nulo de $A$ . A continuación, puede optimizar los coeficientes de esa combinación lineal. Esto requiere una factorización LU de $A$ pero eso puede (al menos en teoría) hacerse fácilmente en tiempo polinómico.

Tenga en cuenta que esto es sólo un enfoque teórico. En la práctica computacional, el algoritmo del elipsoide no se utiliza para resolver SDP. Lo más habitual es utilizar métodos de punto interior primal-dual, que tratan directamente las restricciones lineales de igualdad. Alternativamente, se pueden utilizar métodos de optimización convexa de primer orden, pero éstos tampoco tienen ningún problema particular con las restricciones lineales.