En este curso se introducirán los conceptos básicos que permiten caracterizar las soluciones de los problemas de optimización continua y se presentarán algoritmos numéricos para su resolución. Al final del curso se presentarán brevemente las ideas de algoritmos no determinísticos, y se dará una idea somera de las técnicas de optimización discreta.
Los problemas se analizarán en orden creciente de dificultad, comenzando con problemas de optimización irrestrictos, agregando restricciones lineales y finalmente el caso de función objetivo y restricciones no lineales.
Se analizarán los principales métodos considerando tanto sus propiedades teóricas como las cuestiones esenciales relacionadas con su implementación computacional.
Se presentarán ejemplos de problemas de la industria y de otras áreas de las ciencias que pueden ser modelados como problemas de optimización no lineal, y se propondrán algunos de ellas como trabajo práctico. Se usará Matlab y algunas rutinas específicas para resolver problemas y analizar el desempeño de los principales algoritmos.
Introducción al problema de optimización no lineal.
1. Formulación del problema.
2. Ejemplos.
3. Optimización global y local.
4. Algoritmos.
Condiciones de optimalidad para optimización sin restricciones
1. Condiciones necesarias y suficientes para un minimizador local.
2. Convexidad.
3. Condiciones de optimalidad para funciones convexas diferenciables.
Algoritmo con búsquedas unidimensionales.
1. Direcciones de descenso.
2. Modelo de algoritmo de búsqueda unidimensional.
3. Algoritmo con convergencia global.
4. Velocidad de convergencia.
Métodos clásicos de descenso.
1. Método del gradiente.
2. Funciones cuadráticas.
3. Funciones generales.
4. Método de Newton.
5. Métodos Quasi-Newton.
Optimización con restricciones lineales de igualdad.
1. Región de factibilidad.
2. Condiciones necesarias y suficientes para un minimizador local.
3. Programación cuadrática.
4. Algoritmos para restricciones lineales de igualdad.
Optimización con restricciones lineales de desigualdad.
1. Región de factibilidad.
2. Condiciones necesarias y suficientes para un minimizador local.
3. Optimización con restricciones de cotas.
4. Programación cuadrática.
5. Algoritmos para restricciones lineales de desigualdad.
Métodos de restricciones activas.
1. Modelo de algoritmo.
2. Análisis de convergencia global y local.
Optimización con restricciones de igualdad no lineales.
1. Región de factibilidad.
2. Condiciones necesarias y suficientes para un minimizador local.
3. Multiplicadores de Lagrange.
4. Algoritmos: Métodos de penalización. Métodos de gradiente proyectado. Métodos de Lagrangiano Aumentado. Métodos de restauración inexacta.
Optimización con restricciones de desigualdad no lineales.
1. Región de factibilidad.
2. Condiciones necesarias y suficientes para un minimizador local.
3. Adaptación de los métodos del capítulo 8 para desigualdades.
4. Métodos de región de confianza.
5. Programación cuadrática secuencial.
Métodos no determinísticos
1. Métodos de recocido simulado.
2. Concepto de algoritmos genéticos.
Métodos discretos
1. Grafos y redes de transporte.
2. Flujo máximo en redes de transporte y problema del emparejamiento óptimo.
BIBLIOGRAFÍA:
Bertsekas, D, Nonlinear programming. Athena Scientific, 2da edición 1999.
Conn,.A.R. ; Gould, N.I.M.; Toint, Ph. L., Trust region methods. MPS SIAM series, 2000.
Dennis, J. E.; Schnabel, R. B. Numerical methods for unconstrained optimization and nonlinear equations. Englewood Cliffs, Prentice hall, 1983.
Fletcher, R. Practical methods of optimization. 2 da edición., NY, John Wiley and Sons, 1986.
Friedlander,. Ana Elementos de programaçao nao linear, Campinas, Editora da Unicamp, 1994.
Gill, P.E; Murray, W.; Wright, M. Practical Optimization. NY, Academic Press, 1981.
Mangasarian, O. Nonlinear programming, Classics in applied mathematics . SIAM, 1994.
Martínez, J. M. ; Santos, S.A. , Métodos computacionais de otimizaçao, XX Colóquio Brasileiro de Matemática, IMPA, 1995.
Nocedal ,J.; Wright, S., Numerical optimization, Springer Series in Operations research, Springer, 1999.
Strang, G, Linear Algebra and its Applications, 3 edición. Saunders, 1988.
CORRELATIVAS: Elementos de Cálculo Numérico –Análisis Complejo –Investigación Operativa