DCC808 - Programação Não Linear
Disciplina da linha de pesquisa em Otimização, ministrada pelo Prof. Alexandre Salles da Cunha, para os Programas de Mestrado e de Doutorado em Ciência da Computação da UFMG.
Objetivos:
Apresentar a teoria que fundamenta várias classes de algoritmos para resolução de Problemas de Otimização Não Linear, diferenciáveis, convexos ou não convexos.
Apresentar os principais algoritmos para resolver Problemas de Otimização Não Linear diferenciáveis.
Observação: Este não é um curso de Otimização Global. Assim sendo, para Problemas de Otimização Não Linear Não Convexos, os algoritmos aqui discutidos são capazes de produzir (apenas) uma solução ótima local.
Para um curso de Otimização Não Linear Global, veja o meu curso de Programação Não Linear Inteira e Global aqui.
Referências bibliográficas:
[Principal] David G. Luenberger e Yinyu Ye. Linear and Nonlinear Programming, 3a Edição, Springer, 2010.
D. Bertsekas. Nonlinear Programming, 3a Edição, Athena Scientific, 2016.
M. Bazaraa, H. H. Sherali e C. Shetty. Nonlinear Programming: Theory and Algorithms, 3a Edição, Wiley-Interscience, 2006.
S. Boyd e L. Vanderberghe. Convex optimization, Cambridge University Press, 2007.
R.C. Buck. Advanced Calculus, Waveland Pr. Inc, 3a. Edição, 2003.
J. Hiriart-Urruty e C. Lemaréchal. Fundamentals of Convex Analysis, 2a Ediçao, Springer, 2004.
Lloyd N. Trefethen, David III Blau, Numerical Linear Algebra, SIAM, 1997.
Estrutura do curso:
O curso é organizado em três blocos:
Bloco 1 - Revisão de Álgebra Linear, Álgebra Linear Computacional e Análise Convexa. Uma boa referência para o conteúdo de Álgebra Linear aqui revisado pode ser encontrado na página do curso de Álgebra Linear Computacional que leciondo para a graduação em Ciência da Computação e Matemática Computacional. O link para o curso encontra-se aqui. Em resumo, revisamos os conceitos de espaços vetoriais, matrizes simétricas, simétricas positivas definidas, fatorações matriciais (LU, Cholesky, Espectral), autovalores e autovetores. Além disso, revisamos caracterizações de funções convexas e operações que preservam convexidade.
Bloco 2 – Otimização Não Linear Irrestrita.
Condições necessárias e suficientes de otimalidade local (e global) para problemas irrestritos.
Busca Unidirecional.
Métodos do tipo Gradiente.
Métodos de Direções Conjugadas, Gradiente Conjugado.
Métodos do tipo Newton, Quasi-Newton.
Análise de ordem e taxa de convergência destes métodos para o caso quadrático convexo.
Bloco 3 – Otimização Não Linear com Restrições.
Condições necessárias e suficientes de otimalidade local (e global) para problemas com restrições de igualdade e desigualdades.
O papel das condições de qualificação (regularidade) para a caracterização de otimalidade local.
Métodos primais:
Métodos de restrições ativas.
Métodos de direções viáveis, método de Frank-Wolfe.
Método do Gradiente Projetado.
Método do Gradiente reduzido, Simplex Convexo.
Dualidade em Programação Não Linear:
Problema Dual Lagrangeano
Funções conjugadas
Dualidade de Fenchel
Métodos de Penalidades e Barreira (pontos interiores)
Propriedades de funções de penalidade
Propriedades de funções barreira
Penalidades exatas
Papel convexificador da função de penalidade clássica.
Método de Newton e Gradiente Conjugado para resolver os subproblemas em métodos de penalidades e de barreira.
Método do Lagrangeano Aumentado.
Programação Sequencial Quadrática.
Listas de exercícios e provas anteriores:
Avaliação da disciplina:
A distribuição de pontos entre as atividades avaliativas varia um pouco de semestre para semestre. Porém, via de regra, contemplam cerca de 40% dos pontos para listas de exercícios, 40% para provas individuais e 20% para um trabalho de implementação de algum método visto durante o curso.