Introducción a Optimización Convexa

Martes y Jueves 7:00-8:50am

Salón: AU-2017

Textos:

  • [BV] Convex Optimization. S. Boyd y L. Vandenberghe.
  • [G] Foundations of Optimization. O. Güler.
  • [N] Introductory Lectures on Convex Optimization. Y. Nesterov.
  • [NW] Numerical Optimization. J. Nocedal y S. Wright.

Notas:

  • Tareas (40%): Se asignarán varios ejercicios semanalmente y los estudiantes los deben presentar en la clase.
  • Parciales (40%): Se harán dos parciales. El segundo tendrá una parte computacional.
  • Proyecto (20%).

Anuncios:

  • El primer parcial es el jueves 5 de marzo.
  • El segundo parcial consiste en entregar un adelanto del proyecto el martes 12 de mayo.
Fecha Tema Referencias Ejercicios
21/01 Preliminares de cálculo. Resultados básicos de optimización. [G] Sec. 1.2,1.3,1.5,2.1,2.7 [G] Cap. 1: 5,7-9
23/01 Resultados básicos de optimización. Conjuntos convexos. [G] Sec. 2.1,2.7,4.2
28/01 Conjuntos convexos. [G] Sec. 4.2 [G] Cap. 2: 4,9. Cap. 4: 3.
30/01 Funciones convexas. Funciones convexas suaves. [G] Sec. 4.3,4.4
04/02 Optimización de funciones convexas. Regularidad de funciones convexas. [G] Sec. 4.5, [N] Sec. 3.1.3 [G] Cap. 4: 7,11,14.
06/02 Regularidad de funciones convexas. Subgradientes (I). [N] Sec. 3.1.3,3.1.5
11/02 Subgradientes (I). Teoremas de separación (I). [G] Sec. 6.1,6.2, [N] Sec. 3.1.4 Justifique los ejemplos 2-5 de [N] Sec. 3.1.6.
13/02 Teoremas de separación (I). Subgradientes (II). [G] Sec. 6.1,6.2, [N] Sec. 3.1.4,3.1.6
18/02 Subgradientes (II). Teoremas de separación (II). [G] Sec. 6.2, [N] Sec. 3.1.6 [G] Cap. 6: 1,2. Ejercicios de clase.
20/02 Funciones barrera. Cono polar. Conos poliedrales y finitamente generados. [G] Sec. 6.3,7.1
25/02 Teorema de representación de poliedros. [G] Sec. 7.1,7.2
27/02 Desigualdades lineales y Lema de Farkas. [G] Sec. 7.3,7.4
03/03 Repaso
05/03 Programación lineal [G] Sec. 8.1 [G] Cap. 7: 2,9,10,20
10/03 Holgura complementaria estricta. Programación geométrica. [G] Sec. 8.5, [BV] Sec. 4.5 [G] Cap. 8: 3,6
12/03 Optimización convexa en estadística. Corrección del parcial. [BV] Cap. 7, Sec. 8.6
24/03 Problemas convexos generales. Problemas duales, ejemplos. [G] Sec. 11.5,11.6
26/03 Puntos de silla, dualidad débil y condiciones KKT. [G] Sec. 11.2, 11.3 [G] Cap. 11: 2,4,8,10
31/03 Teorema de dualidad fuerte [G] Sec. 11.4 [G] Cap. 11: 15,19,20
02/04 Presentación de proyectos
14/04 Método del descenso del gradiente. Condiciones de Armijo, Wolfe y Goldstein. [N] Sec. 1.2.2,1.2.3, [NW] Sec. 3.1,3.2
16/04 Métodos del descenso del gradiente, Newton y quasi-Newton. [N] Sec. 1.2.3,1.2.4,1.3.1 [NW] Sec. 6.1 Tarea 1.
21/04 Método de región de confianza. Método del descenso del gradiente y acelerado para funciones convexas. [N] Sec. 2.1.5,2.2.1 [NW] Sec. 4.1,4.2
23/04 Método del descenso del gradiente para funciones fuertemente convexas. Funciones auto-concordantes. [N] Sec. 2.1.3,2.1.5,4.1.3-4.1.5
28/04 Métodos del gradiente estocástico, subgradiente y gradiente proximal. [N] Sec. 3.2.2,3.2.3
30/04 No hay clase.
05/05 Problemas con restricciones de igualdad. Método de barrera. [BV] Cap. 10 y Sec. 11.2,11.3, [N] Sec. 4.2.2-4.2.4
07/05 Función de barrera para programación semidefinida. Método primal-dual. [BV] Sec. 11.7, [N] Sec. 4.3.3