Métodos Numéricos II 2023
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:50 a 21:25 CIT-501, y Jueves de 19:50 a 21:25 CIT-414.
Office Hours
- Viernes de 18:00 a 19:00.
Material del curso
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 04.07.2023 | Introducción al curso. Normas matriciales. Aula 01 | Trefethen-Bau, Lecture 3. |
| 02 | 06.07.2023 | Ejemplo de norma 2. Conceptos: kernel, nulidad, rango. Aula 02 | Trefethen-Bau, Lecture 3. norms.ipynb |
| 03 | 11.07.2023 | Descomposición espectral. Aula 03 |
Trefethen-Bau, Lecture 4. spectral.ipynb |
| 04 | 13.07.2023 | Descomposición en valores singulares (SVD). Aula 04 |
Trefethen-Bau, Lecture 5. svd.ipynb |
| 05 | 18.07.2023 | Aplicaciones de la SVD: PCA. Aula 05a Aula 05b |
|
| 06 | 20.07.2023 | Aplicaciones de SVD: Aproximaciones de bajo rango, compresión de imágenes. | compression.ipynb SVD Compression Demo |
| L1 | 18.07.2023 | Lista 01 Fecha de entrega: martes 01 de agosto. |
|
| 07 | 25.07.2023 | Estabilidad y condicionamiento. Número de condición. Aula 06a Aula 06b | Trefethen-Bau, Lectures 13-15. |
| 08 | 27.07.2023 | Eliminación gaussiana. Factoración $LU$ y $PA = LU$. Aplicaciones. Aula 07 | Trefethen-Bau, Lecture 6. |
| 09 | 01.08.2023 | Técnicas de Pivoteo. Aula 08 |
Trefethen-Bau, Lecture 6. Burden-Faires, Cap. 6. |
| 10 | 01.08.2023 | Tipos especiales de matrices. Factoración LL^T y LDL^T. Aula 09 |
Trefethen-Bau, Lecture 23. Burden-Faires, Cap. 6. |
| 11 | 03.08.2023 | Matrices positivas definidas. Matrix positiva más cercana. Aplicación de la descomposición de Cholesky. | cholesky.ipynb generate_gaussian.ipynb |
| 12 | 08.08.2023 | Métodos iterativos para sistemas lineales. Aula 10 | Quarteroni et al., Cap. 4. |
| L2 | 08.08.2023 | Lista 02 Fecha de entrega: viernes 25 de agosto. |
|
| 13 | 17.08.2023 | Proyectores. Factoración QR. Aula 11 |
Trefethen-Bau, Lectures 6-8 y 10. |
| 14 | 22.08.2023 | Cálculo de autovalores. El método de las Potencias. Aula 12 |
Trefethen-Bau, Lecture 27. |
| 15 | 24.08.2023 | Cálculo de autovalores. El método QR. Aula 13 |
Trefethen-Bau, Lectures 26, 28. |
| 16 | 24.08.2023 | Matrices ralas. Aula 14 |
|
| L3 | 29.08.2023 | Lista 03 Fecha de entrega: lunes 12 de septiembre. |
|
| 17 | 31.08.2023 | Derivadas vectoriales y matriciales. Aula 16 |
Fukunaga. App A. |
| 18 | 05.09.2023 | Fundamentos de optimización I. Aula 17 |
Nocedal-Wright, Cap. 1. |
| 19 | 07.09.2023 | Fundamentos de optimización II. Aula 18 |
Nocedal-Wright, Cap. 1. |
| 20 | 19.09.2023 | Funciones convexas. Aula 19 |
Boyd-Vandenberghe. |
| 21 | 21.09.2023 | Algoritmos para optimización 1-dimensional. Aula 20 |
Nocedal-Wright, Cap. 2. |
| 22 | 26.09.2023 | Descenso gradiente. Aula 21 |
Nocedal-Wright, Cap. 2. |
| 23 | 28.09.2023 | Ejemplos de descenso gradiente. Aspectos prácticos. | Nocedal-Wright, Cap 2. |
| 24 | 03.10.2023 | Descenso gradiente de Newton y hessiano aproximado. Aula 22 | Nocedal-Wright, Cap 2. |
| 25 | 03.10.2023 | Búsqueda en línea. Condiciones de Wolfe y de Goldstein. Backtracking. Aula 23 | Nocedal-Wright, Cap. 2. |
| L4 | 04.10.2023 | Lista 04 Fecha de entrega: jueves 19 de octubre. |
|
| 26 | 05.10.2023 | Teorema de Zoutendijk. Convergencia del descenso gradiente. Aula 24 | Nocedal-Wright, Cap 3. |
| 27 | 12.10.2023 | Descenso coordenado y Descenso coordenado por Bloques. Aula 25 | Nocedal-Wright, Sección 4.5. |
| 28 | 17.10.2023 | Descenso gradiente proyectado. Regresión lineal bases de funciones. Aula 25 | Nocedal-Wright, Sección 9.3. |
| 29 | 19.10.2023 | Gradiente conjugado lineal (versión básica y estándar). Aula 26 | Nocedal-Wright, Cap 5. |
| 30 | 19.10.2023 | Gradiente conjugado no-lineal: Fletcher-Reeves, Polak-Ribière, Hestenes-Stiefel. Aula 27 | Nocedal-Wright, Cap. 5. |
| 31 | 24.10.2023 | Métodos Quasi-Newton: SR1, DFP, BFGS. Aula 28 |
Nocedal-Wright, Cap 6. |
| 32 | 26.10.2023 | Optimización sin derivadas: Nelder-Mead. Heurísticas y estrategias de optimización. Aula 29 | |
| 33 | 31.10.2023 | Representación en optimización combinatoria. Ejemplos. | |
| L5 | 02.11.2023 | Lista 05 cities.csv Fecha de entrega: jueves 23 de noviembre. |
|
| 34 | 02.11.2023 | Búsqueda local: BFS, DFS, Beam search, Backtracking, Taboo search. Aula 30 | |
| 35 | 07.11.2023 | Algoritmos genéticos (GA). Aula 31 |
|
| 36 | 09.11.2023 | Aplicaciones de GA: Permutaciones, TSP, generación de imágenes. | Larrañaga et al. GA for TSP |
| 37 | 14.11.2023 | Enfriamiento simulado. Aula 32 |
Proyectos
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 29.08.2023 | Proyecto 1 - Spectral Clustering. | Proyecto 1 Fecha de Entrega: jueves 05 de octubre. plane_half.png |
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 19.10.2023 | Proyecto 2 - Optimización. | Proyecto 2 |
| 2 | 03.11.2023 | Fecha límite para elegir tema. | |
| 3 | 11.11.2023 | Entrega de la presentación (borrador). | |
| 4 | 16 al 23.11.2023 | Presentación de proyectos. | |
| 5 | 25.11.2023 | Entrega de informe, código y presentación final. |
Proyecto 2 – Temas seleccionados
| Equipo | Fecha | Expositores | Tópico |
|---|---|---|---|
| 1 | 16.11.2023 | José Gordillo, Juan Luis Solórzano | Métodos de punto interior Presentación |
| 7 | 16.11.2023 | Rudik Rompich, Alejandro Pallais | El problema Knapsack Presentación |
| 9 | 16.11.2023 | Juan Galicia, Stefan Quintana | Algoritmos genéticos para Sudokus Presentación |
| 2 | 21.11.2023 | Elisa Samayoa, Julio Ávila | Shortest path problem Presentación |
| 3 | 21.11.2023 | María José Gil, Joshua Chicoj | Evolución diferencial (ED) Presentación |
| 4 | 21.11.2023 | Juan Fernando Ramírez, Jonathan Espinoza | Algoritmos de estimación de distribución (EDA) Presentación |
| 6 | 23.11.2023 | Javier Aguilar, Wilfredo Gallegos | Gradiente estocástico (SGD) Presentación |
| 3 | 23.11.2023 | Jeyner Arango, Oscar Méndez | Optimización en redes neuronales Presentación |
| 8 | 23.11.2023 | Sofía Escobar, Guillermo Furlán | Particle swarm optimization (PSO) Presentación |
Referencias
Textos:
Referencias adicionales:
-
R. Burden, A. Burden, D. J. Faires (2017). Análisis numérico.
-
A. Quarteroni, R. Sacco, F. Saleri (2000). Numerical Mathematics.
-
J. Stoer, R. Bulirsch (2002). Introduction to Numerical Analysis.
-
A. Izmailov, M. Solodov (2014). Newton-type for Optimization and Variational Problems.
-
C. Meyer (2001). Matrix Analysis and Applied Linear Algebra.