View on GitHub

opt2022

Curso de Optimización 2022

Métodos Numéricos II 2022

Este curso es continuación de los temas estudiados en Métodos Numéricos 1. En esta materia, se estudian o revisan temas no introductorios de algoritmos para cálculo científico y aplicado y su implementación computacional. Se estudian tres grandes temas: (1) Álgebra lineal computacional, (2) Optimización numérica continua, y (3) Optimización discreta. La primera parte el curso se enfoca en temas sobre cálculo de autovalores y autovectores, y la solución eficiente de sistemas lineales. En el segundo bloque, el bloque principal del curso, introduce los temas de optimización numérica, principalmente los métodos de gradiente y punto interior, así como métodos de la familia de gradiente conjugado y métodos quasi-Newton. El tema culmina haciendo un estudio de la teoría de optimización restricta, particularmente programación lineal y programación cuadrática. Finalmente, en el tercer bloque, hacemos una introducción a algunos métodos de optimización combinatoria y discreta.

Importante!! El curso cuenta con una parte práctica extensiva, en la que el estudiante implementará en código computacional cada uno de los algoritmos estudiados. Parte fundamental del curso es utilizar las herramientas aprendidas en varios proyectos aplicados donde se trabajará con datos reales y comunicar los resultados mediante reportes técnicos y seminarios.

Prerrequisitos

Se recomienda que los estudiantes antes del curso estén habituados con los temas:

Programa del curso

Programa del curso

Horario

  • Martes y jueves de 18:10 a 19:45.

Office Hours

  • Viernes de 19:00 a 20:00.

Material del curso

No. Fecha Tópicos Recursos
01 05.07.2022 Introducción al curso. Normas matriciales.
Aula 01		 Libro de Trefethen, Lecture 3.
02 07.07.2022 Ejemplos de normas matriciales. Descomposición espectral.
Aula 02		 Libro de Trefethen, Lecture 4.
03 12.07.2022 Descomposición SVD. Propiedades.
Aula 03		 Libro de Trefethen, Lecture 5.
04 14.07.2022 Ejemplo de SVD. Descomposición de Schur. Estabilidad.
Aula 04		 Libro de Trefethen, Lecture 12.
05 19.07.2022 Número de condición. Aritmética de punto flotante.
Aula 05		 Libro de Trefethen, Lectures 13-15.
06 21.07.2022 Eliminación gaussiana. Factoracón LU y PA = LU.
Aula 06		 Libro de Trefethen, Lecture 6.
07 26.07.2022 Gauss-Jordan. Estrategias de pivoteo.
Aula 07		 Libro de Trefethen, Lecture 6.
Burden y Faires, Cap. 6.
08 26.07.2022 Descomposición LL^T y LDL^T.
Aula 08		 Libro de Trefethen, Lecture 23.
L1 28.07.2022   Lista 1
Fecha de entrega: martes 16 de agosto.
09 02.08.2022 Métodos iterativos para sistemas lineales.
Aula 09		 Libro de Quarteroni et al., Cap. 4.
10 04.08.2022 Proyectores. Factoración QR.
Aula 10		 Libro de Trefethen, Lectures 6-8 y 10.
11 16.08.2022 Cálculo de autovalores. Método de las Potencias. Aula 11 Libro de Trefethen, Lecture ??.
12 18.08.2022 El método QR.
Aula 12		  
13 23.08.2022 Matrices dispersas.
Aula 13		  
14 25.08.2022 Derivadas vectoriales y Cálculo matricial.
Aula 14		  
L2 01.09.2022   Lista 2
Fecha de entrega: martes 20 de septiembre.
16 01.09.2022 Fundamentos de optimización.
Aula 15		  
17 06.09.2022 Condiciones de Optimalidad.
Aula 16		  
18 08.09.2022 Optimización Convexa.
Aula 17		 Boyd y Vandenberghe. Caps 1 y 2.
19 20.09.2022 Descenso gradiente.
Aula 18		 Nocedal y Wright.
20 22.09.2022 Algoritmos de optimización 1-dimensional.
Aula 19		 Nocedal y Wright.
21 27.09.2022 Búsqueda en línea. Condiciones de Wolfe y de Goldstein. Backtracking.
Nocedal y Wright.
22 29.09.2022 Convergencia.
Nocedal y Wright.
L3 29.09.2022   Lista 3
Fecha de entrega: jueves 13 de octubre.
23 06.10.2022 Estimación de la tasa de convergencia.
Nocedal y Wright.
24 11.10.2022 Descenso Coordenado. Gradiente Proyectado.
Nocedal y Wright.
25 13.10.2022 Aplicaciones: Bases radiales gaussianas.
 
27 25.10.2022 Métodos Cuasi-Newton: SR1, DFP, BFGS.
 
28 27.10.2022 Optimización sin derivadas. Método de Nelder-Mead.
 
29 03.11.2022 Optimización discreta. Representaciones.  
30 08.11.2022 Búsqueda local. BFS, DFS, Backgracking.  
31 10.11.2022 Hill-Climbing. Estrategias para problemas discretos.  
32 15.11.2022 Enfriamiento simulado.  
33 17.11.2022 Algoritmos genéticos.  
34 18.11.2022 Operadores de selección, cruce y mutación. Ejemplos.  
35 22.11.2022 Presentación de seminarios.  
36 24.11.2022 Presentación de seminarios.  

Proyectos

A continuación se listan algunos temas sugeridos para presentación de sus proyectos de curso. Temas-proyecto.pdf

Fechas importantes:

No. Fecha .
1 21.10.2022 Elección de tema de proyecto.
2 15.11.2022 Entrega de presentación y reporte (borrador).
3 21-25.11.2022 Presentación de Seminarios.
4 27.11.2022 Entrega de versión final (Presentación, Reporte, Código).

Temas presentados:

No. Fecha Conferencistas Tópico
1 22.11.2021 José Lucha El problema TPS
2 22.11.2021 Juan Lorthiois, Leonel Contreras Un ejemplo de Programación Lineal
3 24.11.2021 Carlos Martínez, Elder Guzmán Un problema de Asignación de Recursos
4 24.11.2021 Oscar Godoy, Rafael Dubois El problema Knapsack

Referencias