Novedades

La materia comienza el lunes 18 de agosto a las 19 h (aula 1204 pabellón 0 + infinito).

Horarios y organización

Se dictará en el 2.º Cuatrimestre 2025.

• Lunes de 19 a 21h, clase teórica. Aula 1204, pabellón 0 + infinito
• Miercoles de 19 a 21h, clase práctica en laboratorio de computación. Laboratorio 1111, pabellón 0 + infinito
• Ambos días habrá horario extra de consultas de 21 a 22.

Docentes

• Santiago Laplagne (profesor Instituto de Cálculo)
• Pedro Ortiz (auxiliar Instituto de Cálculo)

Correlatividades

Se requiere haber cursado alguna de las siguientes materias: Álgebra lineal / Matemática 2 (F) / Álgebra Lineal Computacional / Métodos Numéricos.

Breve descripción del curso

La programación semidefinida (SDP) puede considerarse como una extensión de programación lineal a polinomios, donde las restricciones lineales se generalizan a restricciones sobre la positividad de matrices. Es la clase más grande problemas de optimización que podemos resolver eficientemente, con aplicaciones en optimización combinatoria y convexa, teoría de grafos y geometría algebraica.

En este curso comenzaremos estudiando los conceptos básicos de SDP e iremos avanzando hacia desarrollos más actuales, poniendo énfasis especial en la teoría de Parrilo-Lasserre de relajaciones de sumas de cuadrados y aplicaciones. Veremos abundantes ejemplos y cómo resolverlos implementando algoritmos y utilizando bibliotecas de software en Python. En la última parte del curso, nos enfocaremos en un estudio teórico de los conos de polinomios positivos y sumas de cuadrados, siguiendo resultados sorprendentes recientes de G. Blekherman.

Puntaje y régimen de promoción

• La aprobación de la materia es por entrega de ejercicios durante la cursada y un trabajo final (preparación y exposición de algún tema teórico o práctico).
• Esta materia otorga 4 puntos para la Licenciatura en Matemática y 96 horas para Licenciatura en Ciencias de Datos.
• Esta aprobada como materia de posgrado por la Facultad y otorga un puntaje máximo de 4 puntos para doctorado (consultar el puntaje con la subcomisión de doctorado correspondiente).

Programa

1) Preliminares.

Programación lineal. El método simplex. Dualidad en programación lineal. Métodos de punto interior. Aplicaciones. Conjuntos convexos. Descripción implícita de conjuntos convexos. Proyecciones. Hiperplano separador. Hiperplano soporte. Conos convexos. El ortante no-negativo. Matrices definidas y semidefinidas positivas. Teorema espectral. El cono de matrices semidefinidas. Formas cuadráticas y formas bilineales. Diagonalización de formas cuadráticas. Ley de inercia. Python. Introducción a programación en Python. Jupyter Notebook. Anaconda.

2) Programación semidefinida. Conceptos básicos y ejemplos.

Desigualdades matriciales lineales (LMI). Poliedros y espectraedros. Proyección de espectraedros. Problema primal. Conjuntos factibles. Problema dual. Condiciones de optimalidad. Salto de dualidad. Espectraedros como conjuntos factibles de programas semidefinidos. Programación cónica. Dualidad fuerte. Software: Mosek.

3) Aplicaciones de optimización semidefinida.

Mayor y menor autovalor. Teoría de control en sistemas dinámicos. Conjuntos estables en grafos. Optimización combinatoria: maxcut. Optimización convexa: volumen mínimo de elipsoide circunscriptp. Datos faltantes en matrices de mínimo rango.

4) Optimización polinomial y sumas de cuadrados.

Conjuntos semi-algebraicos. Conos de polinomios no-negativos y sumas de cuadrados. El teorema de Hilbert. Descomposición como suma de cuadrados de polinomios positivos en una variable. Matriz de Gram y criterio de descomposición como suma de cuadrados para polinomios en varias variables. Descomposición racional. Programas de sumas de cuadrados.

5) Momentos

El problema de momentos en una dimensión. Problema de momentos completo y truncado. El problema de momentos en varias dimensiones. Algoritmos. Relajación semidefinida. Aplicaciones. Optimización global sobre polinomios. Optimización con restricciones.

Bibliografía

• A. Ben-Tal y A. Nemirovski, “Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (MPS-SIAM Series on Optimization)”. SIAM, 2001.
• G. Blekherman, “Nonnegative polynomials and sums of squares”. Journal of the American Mathematical Society, 2012.
• G. Blekherman, P. Parrilo y R. Thomas (eds.), “Semidefinite Optimization and Convex Algebraic Geometry”. SIAM, 2013.
• S. Boyd y L. Vandenberghe, “Semidefinite programming”. SIAM Review 38, 49-95, 1996.
• S. Boyd. y L. Vandenberghe, “Convex Optimization”. Cambridge University Press, 2004.
• B. Gärtner and J. Matousek, “Approximation Algorithms and Semidefinite Programming”.  Springer, 2012.
• R. D. C. Monteiro, “First- and second-order methods for semidefinite programming”. Mathematical Programming B97, 209-244, 2003.
• A. Nemirovskii y Y. Nesterov, “Interior-Point Polynomial Algorithms in Convex Programming (SIAM Studies in Applied Mathematics, Vol. 13)”. SIAM, 1994.
• P. Parrilo, “Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization”. Tesis de doctorado, 2000.
• J. Renegar, “A Mathematical View of Interior-Point Methods in Convex Optimization (MPS-SIAM Series on Optimization)”. SIAM, 2001.
• R. Saigal, L. Vandenberghe y H. Wolkowicz (eds.), “Handbook on Semidefinite Programming: Theory, Algorithms, and Applications”. Kluwer Academic, 2000.
• M. J. Todd, “Semidefinite optimization”. Acta Numerica 10, 515-560, 2001.
• S. J. Wright, “Primal-Dual Interior-Point Methods”. SIAM, 1997.