Optimización

Dra Ana Friedlander

UNICAMP (Universidade Estadual de Campinas), Brasil.

 friedlan@ime.unicamp.br

http://www.ime.unicamp.br/friedland.html

 

 

Materia optativa para la Licenciatura en Ciencias de la Computación.

Puede ser cursada también por alumnos de otras carreras (consultar con la profesora por los prerequisitos).

 

Modalidad del dictado: 4 horas de clase teórico/prácticas.

 

Horario: se llevará a cabo una reunión para fijar el horario el martes 16 de marzo a las 19hrs

en el aula de seminario del segundo piso del Pabellón I.

 

Correlativas: Métodos Numéricos.

Puntaje: 3 puntos

Forma de evaluación : Un parcial y un trabajo práctico.

Fechas y trabajos


Libro: Metodos Computacionais de Otimizacao, Martinez, Santos



Programa BOX-Quacan en C++


 

PROGRAMA

 

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.

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 la ciencias(por ejemplo:   economía, ingeniería mecánica, geofísica, teoría de juegos )  que pueden ser modelados como problemas de optimización no lineal, y se propondrán algunas de ellas como trabajo práctico. Se usará el paquete EASY  desarrollado por el Grupo de Optimización de la Universidad de  Campinas para analizar  el desempeño de los principales algoritmos.

 

Programa detallado

 

1.       Introducción al problema de optimización no lineal.

1.1   Formulación del problema.

1.2   Ejemplo: Un problema de equilibrio en economía.

1.3   Optimización global y local.

1.4   Algoritmos.

 

2.      Condiciones de optimalidad para optimización sin restricciones

2.1   Condiciones necesarias  y suficientes  para un minimizador local.

2.2   Convexidad.

2.3   Condiciones de optimalidad para funciones convexas diferenciables.

 

3.      Algoritmo con búsquedas unidimensionales.

3.1    Direcciones de descenso.

3.2    Modelo de algoritmo de búsqueda unidimensional.

3.3    Algoritmo con convergencia global.

3.4    Velocidad de convergencia.

 

4.      Métodos clásicos de descenso.

4.1   Método  del gradiente.

4.1.1        Funciones cuadráticas.

4.1.2        Funciones generales.

4.2   Método de Newton.

4.3   Métodos Quasi-Newton.

 

5.      Optimización con restricciones lineales de igualdad.

5.1   Región de factibilidad.

5.2   Condiciones necesarias y suficientes para un minimizador local.

5.3   Programación cuadrática.

5.4   Algoritmos para restricciones lineales de igualdad.

 

6.      Optimización con restricciones lineales de desigualdad.

6.1   Región de factibilidad.

6.2    Condiciones necesarias y suficientes para un minimizador local.

6.3    Optimización con restricciones de cotas.

6.4    Programación cuadrática.

6.5   Algoritmos para restricciones lineales de desigualdad.

 

7.       Métodos de restricciones activas.

7.1    Modelo de algoritmo.

7.2    Análisis de convergencia global y local.

7.3    Uso del paquete EASY de UNICAMP.

 

8.       Optimización con restricciones de igualdad no lineales.

8.1   Región de factibilidad.

8.2    Condiciones necesarias y suficientes para un minimizador local.

8.3    Multiplicadores de Lagrange.

8.4    Algoritmos.

8.4.1        Métodos de penalización.

8.4.2        Métodos de gradiente proyectado.

8.4.3        Métodos de Lagrangeano Aumentado.

8.4.4        Métodos de restauración inexacta.

8.4.5        Uso del paquete  EASY de UNICAMP.

 

9.        Optimización con restricciones de desigualdad no lineales.

9.1   Región de factibilidad.

9.2   Condiciones necesarias y suficientes para un minimizador local.

9.3    Adaptación de los métodos del capítulo 8 para desigualdades.

9.4    Métodos de región de confianza.

9.5    Programación cuadrática secuencial.

 

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 andnonlinear equations. Englewood Cliffs, Prentice hall, 1983.

·        Fletcher, R. Practical methods of optimization. 2da 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.