No hay comentarios.

CURSO:FUNDAMENTOS DE ALGORITMOS, COMBINATORIA Y OPTIMIZACION
TRADUCCION:FOUNDATIONS OF ALGORITHMS, COMBINATORICS AND OPTIMIZATION
SIGLA:IMT3400
CREDITOS:10
MODULOS:3
CARACTER:OPTATIVO
TIPO:CATEDRA
CALIFICACION:ESTANDAR
PALABRAS CLAVE:GEOMETRIA CONVEXA,OPTIMIZACION CONVEXA, OPTIMIZACION COMBINATORIAL,OPTIMIZACION ENTERA,ALGORITMOS DE OPTIMIZACION
NIVEL FORMATIVO:MAGISTER


I.DESCRIPCIÓN DEL CURSO

En este curso los estudiantes aprenderan tecnicas de convexidad y sus aplicaciones en optimizacion, combinatoria y algoritmos, para ello abordaran de manera acabada y rigurosa la geometria convexa. Del mismo modo se espera que los estudiantes analicen problemas de optimizacion lineal y conica, a traves de la teoria de la dualidad. Ademas, resolveran de manera eficiente problemas lineales y conicos por medio de la teoria de barreras auto-concordantes. Por ultimo, abordaran el modelamiento eficiente de problemas conicos a traves de formulaciones extendidas.


II.RESULTADOS DE APRENDIZAJE

1.Aplicar las herramientas fundamentales de geometria convexa y discreta en problemas de ingenieria y ciencias de la computacion.

2.Analizar las conexiones clasicas de convexidad con las areas de optimizacion y combinatoria, para su uso en problemas de investigacion en ingenieria y ciencias de la computacion.

3.Identificar nuevos usos de las herramientas de convexidad en otras areas del conocimiento, a traves de aplicaciones provenientes de la ingenieria y ciencias de la computacion.

4.Comparar la aplicabilidad y limitaciones de los metodos de optimizacion mas relevantes para problemas en combinatoria y optimizacion.

5.Crear nuevos algoritmos de optimizacion basados en la teoria de dualidad para problemas en combinatoria y optimizacion.

6.Caracterizar las estructuras geometricas para resolver problemas de combinatoria y optimizacion.

7.Aplicar el pensamiento critico a problemas de investigacion relevantes y de vanguardia, en las areas de Algoritmos, Combinatoria y Optimizacion.


III.CONTENIDOS

1.Elementos de Geometria Convexa en Dimension Infinita
1.1.Espacios Vectoriales normados y sus duales
1.2.Puntos extremos e hiperplanos soportantes de un conjunto convexo
1.3.Recordatorio teoremas de separacion
1.4.Teorema de Krein-Milman
1.5.Compacidad debil del conjunto de probabilidades
1.6.Conos convexos, conjunto polar y dual

2.Geometria Convexa en Dimension Finita
2.1.Teorema de Caratheodory
2.2.Teoremas de Radon y Helly.
2.3.Puntos extremos y caras en poliedros. Aplicaciones al politopo de Birkhoff y politopo de transporte.
2.4.El permutaedro y el Teorema de Schur-Horn
2.5.El cono de momentos, el cono de polinomios no-negativos, y el cono de matrices semidefinidas positivas
2.6.El cono de recesion
2.7.Teorema del Punto Fijo de Brouwer

3.Optimizacion
3.1.Programacion lineal en dimension infinita y finita
3.2.Dualidad en Programacion Lineal
3.3.Matching optimo en grafos bipartitos y transporte optimo.
3.4.Gap de dualidad
3.5.Programacion semidefinida y sumas de cuadrados

4.Cuerpos Convexos y Elipsoides
4.1.Elipsoides
4.2.Aproximacion de normas por elipsoides: el Teorema de John
4.3.Normas y cuerpos convexos.
4.4.El metodo del Elipsoide

5.Barreras auto-concordantes y metodos de punto interior
5.1.Breve repaso del metodo de Newton
5.2.Invarianza afin y funciones autoconcordantes
5.3.Autoconcordancia y conjugada de Fenchel
5.4.Convergencia cuadratica del metodo de Newton para funciones autoconcordantes
5.5.Metodo de path-following
5.6.Barreras auto-concordantes
5.7.Metodo de punto interior primal
5.8.Metodo de punto interior primal-dual para programacion lineal y semidefinida

6.Formulaciones extendidas
6.1.Proyecciones y formulaciones extendidas
6.2.Ejemplos: Permutaedro, el politopo de arboles generadores y poligonos regulares
6.3.Construccion de formulaciones extendidas: Union de poliedros, Programacion Dinamica, jerarquia de Sherali-Adams


IV.ESTRATEGIAS METODOLOGICAS

-Clases expositivas.

-Ayudantias.

-Aprendizaje basado en proyectos.


V.ESTRATEGIAS EVALUATIVAS

-Interrogaciones: 50%

-Proyecto: 20%

-Examen final: 30%


VI.BIBLIOGRAFIA

Minima

A. Barvinok. A Course in Convexity.American Mathematical Society, 2002

Y. Nesterov. Lectures on Convex Optimization. Springer, 2018


Complementaria

J. Matousek. Lectures on Discrete Geometry.Springer,2002

K. Ball. An Elementary Introduction to Modern Convex Geometry. In Flavors of Geometry.MSRI Publications,1997

G. Ziegler. Lectures on Polytopes.Graduate Texts in Mathematics, Springer,1995.

D. Luenberger.Optimization by Vector Space Methods.Wiley & Sons,1969.


PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
INSTITUTO DE INGENIERIA MATEMATICA Y COMPUTACIONAL / MAYO 2022