Profesor:    Pablo Parrilo (Massachusetts Institute of Technology)                                      

Puntaje:     1  punto (lic. y prof.)

Correlatividades:  Algebra lineal

Carga horaria:  6 horas semanales durante 1 mes (marzo-abril)

Carreras:   Licenciatura en Matemática (Or. Pura y Aplicada), Profesorado en Matemática, Doctorado en Matemática

Breve descripción del curso:

En los últimos años, ha habido un gran progreso en el desarrollo de métodos computacionales para resolver ciertos problemas de optimización que pueden describirse utilizando sistemas de ecuaciones e inecuaciones polinomiales. Dichos métodos combinan resultados teóricos de geometría algebraica real y compleja con programación semidefinida y dan lugar a las herramientas más efectivas conocidas hasta el momento para tratar con estos problemas. El objetivo de este curso es introducir los aspectos teóricos y prácticos de los métodos en cuestión y algunas de sus aplicaciones. 

Este mini-curso se concentrará en aspectos teóricos y computacionales para problemas de optimización con estructura algebraica (en particular, aquéllos que involucran ecuaciones e inecuaciones polinomiales), con énfasis en las conexiones con técnicas basadas en programación semidefinida (SDP).

El curso desarrollará diversos acercamientos algebraicos y numéricos a sistemas polinomiales, con el objeto de presentar métodos que incorporen ambos simultáneamente. Se estudiarán tanto el caso complejo como el real, desarrollándose técnicas de aplicabilidad general, y haciendo hincapié en ideas basadas en convexidad, resultados de complejidad e implementaciones eficientes. Se usarán ejemplos de diversas áreas de la matemática aplicada y la ingeniería, incluyendo sistemas y control, demostración geométrica de teoremas y teoría de la información clásica y cuántica.

Entre los temas a cubrir se encuentran: relajación semidefinida, representaciones como sumas de cuadrados, polinomios hiperbólicos, representabilidad semidefinida de conjuntos convexos, Nullstellensatz complejo y real, geometría algebraica convexa, polinomios ralos y problemas de minimización de rango, etc.

Programa:

• Programación semidefinida.
• Polinomios univariados. Resultantes y discriminantes.
• Polinomios hiperbólicos. Representabilidad semidefinida.
• Polítopos de Newton. Cota BKK.
• Polinomios que son sumas de cuadrados. Aplicaciones.
• Variedades e ideales. Nullstellensatz. Ideales cero-dimensionales.
• Eliminación de cuantificadores sobre R. Positivstellensatz.
• Métodos de reducción usando simetrías.
• Aplicaciones.

Apuntes del curso:

http://homepages.cwi.nl/~monique/eidma-seminar-parrilo/Parrilo-LectureNotes-EIDMA.pdf

Bibliografía:

1. D. A. Cox, J. B. Little, and D. O’Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer,1997.
2. E. de Klerk. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, volume 65 of Applied Optimization. Kluwer Academic Publishers, 2002.
3. B. Mishra. Algorithmic Algebra. Springer-Verlag, 1993.
4. B. Sturmfels. Solving Systems of Polynomial Equations. AMS, Providence, R.I., 2002.
5. H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors. Handbook of Semidefinite Programming. Kluwer, 2000.
6. C. K. Yap. Fundamental problems of algorithmic algebra. Oxford University Press, New York, 2000.

Reunión preliminar:

Aulas y horarios: