View on GitHub

opt2024

Curso de Optimización 2024

Métodos Numéricos II 2024

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, (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 consiste en 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:

Cálculo vectorial
Álgebra lineal (teoría)
Algunos elementos de análisis (convergencia de secuencias y series, análisis en Rn)
Métodos numéricos para una variable (root finding, fitting, numerical differentiation and integration)
Un curso de Programación.

Programa del curso

Horario

Martes de 19:00 a 20:35 CIT-312, y Jueves de 19:00 a 20:35 CIT-312.

Office Hours

Viernes de 18:00 a 19:00.

Material del curso

No.	Fecha	Tópicos	Recursos
01	02.07.2024	Introducción. Aspectos generales del curso.
02	04.07.2024	Normas matriciales. Aula 01	Trefethen-Bau, Lecture 3.
03	09.07.2024	Autovalores. Descomposición espectral. Aula 02	Trefethen-Bau, Lecture 4.
04	11.07.2024	Ejemplos de descomposición espectral. Descomposición en valores singulares (SVD). Aula 03	Trefethen-Bau, Lecture 5.
L1	11.07.2024		Lista 01 Entrega: Jueves 25 de julio
05	16.07.2024	Propiedades de la SVD. Aproximaciones de bajo rango. Aula 04
06	18.07.2024	Aplicaciones de la SVD: Compresión de imágenes.	SVD Compression Demo
07	23.07.2024	Condicionamiento y Estabilidad. Aula 05 Aula 06	Trefethen-Bau, Lectures 13-15.
08	25.07.2024	Factoración LU y PA = LU. Aplicaciones. Aula 07	Trefethen-Bau, Lecture 6.
09	30.07.2024	Técnicas de Pivoteo. Aula 08	Trefethen-Bau, Lecture 6.
10	01.08.2024	Corto 1.
11	06.08.2024	Factoraciones especiales de matrices: Cholesky, LDL^T. Aula 09	Trefethen-Bau, Lecture 23. Burden-Faires, Cap 6.
L2	08.08.2024		Lista 02 Entrega: Martes 27 de agosto
12	06.08.2024	Métodos iterativos para sistemas lineales. Aula 10	Quarteroni et al., Cap. 4.
13	20.08.2024	Descomposición QR. Aula 11	Trefethen-Bau, Lectures 6-8 y 10.
14	27.08.2024	El método de las potencias. Deflación. Shift trick. Aula 12	Trefethen-Bau, Lecture 27.
15	29.08.2024	El método QR. Aula 13	Trefethen-Bau, Lecture 27.
17	04.09.2024	Matrices ralas. Aula 14
18	06.09.2024	Agrupamiento espectral. Segmentación de imágenes.
19	19.09.2024	Programación Lineal. Forma estándar.
20	24.09.2024	Bases y soluciones básicas. Algoritmo Simplex. Ejemplo 1 Ejemplo 3	Taha, Cap. 1 a 3.
L3	26.09.2024	Aplicaciones de programación lineal.	Lista 03 Entrega: Jueves 03 de octubre
21	01.10.2024	Modelo de transporte. Modelo de asignación.	Taha, Cap. 5
22	03.10.2024	Fundamentos de optimización. Derivadas vectoriales y matriciales. Aula 20	Fukunaga. App A.
23	08.10.2024	Fundamentos de optimización II. Gradiente. Fórmula de Taylor. Aula 21	Nocedal-Wright, Cap 1.
24	08.10.2024	Condiciones de optimalidad. Aula 22	Nocedal-Wright, Cap. 1
25	10.10.2024	Funciones Convexas. Aula 23	Boyd-Vandenberghe.
26	10.10.2024	Optimización 1-dimensional. Aula 24	Nocedal-Wright, Cap. 2
27	15.10.2024	Descenso gradiente. Aula 25	Nocedal-Wright, Cap. 2
28	17.10.2024	Descenso gradiente de Newton. Hessianos. Aula 26	Nocedal-Wright, Cap 2.
C2	17.10.2024	Corto 2.	Corto 2 Entrega: Martes 22 de octubre.
29	22.10.2024	Búsqueda en Línea. Condiciones de Wolfe y de Goldstein. Aula 27	Nocedal-Wright, Cap. 2
30	22.10.2024	Convergencia de Búsqueda en Línea. Aula 28	Nocedal-Wright, Cap. 2
31	24.10.2024	Descenso coordenado. Gradiente proyectado simple Aula 29	Nocedal-Wright, Cap. 2
32	29.10.2024	Regresión lineal. Ecuaciones Normales.	Nocedal-Wright, Sección 9.3
33	31.10.2024	Gradiente Conjugado. Aula 31 Aula 32	Nocedal-Wright, Cap. 5
34	05.11.2024	Métodos Quasi-Newton: SR1, DFP, BFGS. Aula 33	Nocedal-Wright, Cap. 6
35	07.11.2024	Representación en optimización combinatoria. Aula 34
36	07.11.2024	Algoritmos genéticos. Operadores de cruce y mutación. Aula 35
37	07.11.2024	Enfriamiento simulado. Aula 36
38	12.11.2024	Presentación de proyectos.
C3	18.11.2024	Corto 3.	Corto 3 Entrega: Viernes 22 de noviembre.
39	19.11.2024	Presentación de proyectos.
C4	21.11.2024	Corto 4.	Corto 4 Entrega: Domingo 24 de noviembre.

Proyectos

Primer Proyecto

No.	Fecha	Tópicos	Recursos
1	06.09.2024	Proyecto 1 - Spectral Clustering.	Proyecto 1 Fecha de Entrega: jueves 10 de octubre. falcon.jpg plane.jpg tree.jpg

Segundo Proyecto

No.	Fecha	Tópicos	Recursos
1	22.10.2024	Proyecto 2 - Optimización.	Proyecto 2
2	30.10.2024	Elección de tema.
3	09.11.2024	Borrador de la presentación.
4	11-22.11.2024	Presentaciones.
5	24.11.2024	Entrega de código, presentación e informa final.

Presentación Segundo Proyecto

Fecha	Expositores	Tópico
12.11.2024	Sofi, Mario	Optimización en Máquinas de Vectores de Soporte Presentación
12.11.2024	Diana, Sebastián	El problema Knapsack Presentación
12.11.2024	Aaron, Carlos	El problema del TSP Presentación
14.11.2024	Ximena, Montse	Particle Swarm Optimization Presentación
14.11.2024	Mariel, Adrián	Regresión logística Presentación
14.11.2024	Paulo, Joab	Ant-colony optimization Presentación
19.11.2024	Gaby, Lourdes	Optimización en redes neuronales Presentación
19.11.2024	Sharis, Manuel	Lagrangiano aumentado Presentación
19.11.2024	Juan Miguel, Pedro	Región de confianza, método dog-leg Presentación
21.11.2024	Alan, Mario	Gradiente estocástico, ADAM Presentación
21.11.2024	Ian, Ricardo	Método de Nelder-Mead Presentación
21.11.2024	Nicolle, Jorge	Búsqueda Tabú Presentación