Otimização Contínua

Conhecimentos de Base Recomendados

Análise Matemática II, Álgebra Linear, Álgebra Linear Numérica

Métodos de Ensino

As aulas teórico-práticas são de consolidação de conceitos e de resolução de problemas, com a participação ativa dos alunos. Poderão ser efectuados alguns pequenos trabalhos computacionais.

Resultados de Aprendizagem

Este curso oferece uma introdução aos fundamentos da otimização contínua, partindo da programação linear e cobrindo de seguida a teoria básica e os métodos mais usuais da otimização não linear com e sem restrições. Ao longo de todo o curso será dado particular ênfase às aplicações concretas à ciência dos dados, que servirão para ilustrar os métodos introduzidos.
Este curso pretende desenvolver uma sólida base matemática sobre a qual possa ser mais tarde desenvolvida com segurança a componente mais aplicacional, nomeadamente no campo da aprendizagem automática.
No final deste curso o aluno deve conhecer e compreender os algoritmos mais importantes de otimização contínua, ser capaz de modelar e resolver problemas de otimização e ter a capacidade de implementar autonomamente versões elementares dos mesmos.
As competências a desenvolver serão a modelação, o espírito crítico, a capacidade analítica e a capacidade de resolução de problemas.

Estágio(s)

Não

Programa

1. Programação linear
1.1- Formulações
1.2- Geometria convexa
1.3- Algoritmo simplex
1.4- Dualidade
2. Otimização não-linear sem restrições
2.1- Existência e unicidade de ótimos
2.2- Métodos de procura unidirectional
2.2-1. Métodos de primeira ordem
2.2-2. Métodos de segunda ordem [Newton, BFGS…]
2.3- Métodos de região de confiança
3. Otimização não-linear com restrições
3.1- Qualificação de restrições e condições necessárias e suficientes para otimalidade
3.2- Penalização quadrática
3.3- Gradiente projetado
3.4- Lagrangeano aumentado
3.5- Programação sequencial quadrática
4. Aplicações a ciência dos dados (a executar ao longo do curso). Por exemplo “compressed sensing”, mínimos quadrados não lineares, LASSO, etc.

Métodos de Avaliação

Avaliação
Resolução de problemas: 15.0%
Exame: 85.0%

Bibliografia

 D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, segunda edição, Wiley & Sons, 1990.

 J. Nocedal e S. J. Wright, Numerical Optimization, segunda edição, Springer, Berlim, 2006.

 M.S. Bazaraa, H.D. Sherali, C.M. Shetty. Nonlinear programming: theory and algorithms. John Wiley & Sons, 2013.

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

 I. Griva, S. G. Nash e A. Sofer, Linear and Nonlinear Optimization, segunda edição, SIAM, Filadélfia, 2009.

 S. Sra, S. Nowozin, S.J. Wright. Optimization for machine learning. Cambridge, Mass. MIT Press, 2012.

- G. Strang. Computational Science and Engineering. Wellesley-Cambridge Press, 2007.