Otimização 1
Ementa e programa
Objetivos da disciplina
- Estudar conceitos básicos em programação não linear
- Estudar os fundamentos dos métodos de resolução clássicos para programação não linear, sobretudo sem restrições
- Analisar aspectos teóricos e numéricos dos métodos
- Implementar algoritmos em computador e testá-los em problemas da literatura
Textos de referência
- Friedlander, A. Elementos de Programação Não-Linear [link 1] [link 2 (versão reformulada em inglês)]
- Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 [link 1] [link 2 (versão alternativa similar)]
Textos complementares
- Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008 [link 1] [link 2]
- Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização [link]
- Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006 [link 1] [link 2]
- Izmailov, A.; Solodov, M. Otimização vol 1. SBM
Canais de acesso
- E-mail do professor: leonardo.secchin@ufes.br
- Sala do professor: prédio do Departamento de Matemática Aplicada, sala 08
Formas de avaliação
- provas escritas, listas de exercícios, trabalhos computacionais ou apresentações orais.
Critérios para aprovação
- Faltas acima de 25% da carga horária –> reprovado(a) por falta
- Média parcial >= 7,0 —> aprovado(a) (desde que não reprovado(a) por falta)
- Média parcial < 7,0 —> Avaliação final (desde que não reprovado(a) por falta). Neste caso, média final >= 5,0 —> aprovado(a).
Listas de exercícios
- LISTA 1 – Conceitos básicos, otimização irrestrita
- LISTA 2 – Convexidade
- LISTA 3 – Métodos para otimização sem restrições
- LISTA 4 – Otimização com restrições
Trabalhos computacionais
- Método dos gradientes conjugados: descrição; código base
- Método do gradiente espectral: descrição; código base
Material
Conceitos básicos
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (capítulo 1)
Otimização sem restrições
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (capítulo 2) Referência complementar: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (capítulo 2)
Convexidade
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (capítulo 3) Referência complementar: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (capítulo 3)
A linguagem de programação Julia
Julia é uma linguagem de programação de alto nível criada em 2012 que implementa várias ferramentas para uso geral em matemática aplicada. Em particular, Julia possui várias ferramentas para otimização. É muito parecida com o Matlab, portanto os códigos são fáceis de entender. Os trabalhos computacionais desta disciplina serão feitos em Julia.
Para uma introdução ao Julia e seu uso em otimização, acesse este link.
Métodos de descida gerais
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (seção 6.1) Referência complementar: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização (seção 6.1)
- ANOTAÇÕES - Métodos de descida gerais
- ANOTAÇÕES - Convergência dos métodos de descida (baseado no Teorema 6.1.6 da referência complementar)
- Código do método do gradiente com busca linear inexata - veja seção “Códigos em Julia”
Método de Newton
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (capítulo 5, seção 6.2) Referência complementar: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização (seção 6.1)
- ANOTAÇÕES - Método de Newton
- ANOTAÇÕES - Convergência global vs local
- ANOTAÇÕES - Convergência dos métodos de Newton e Newton globalizado
- Código dos métodos de Newton e Newton globalizado - veja seção “Códigos em Julia”
Métodos quase-Newton
Referência principal: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização (seção 6.3) Referência complementar 1: Friedlander, A. Elementos de Programação Não-Linear (seção 6.1) Referência complementar 2: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (seção 5.4 do livro publicado pela Cengage)
Método do gradiente espectral
Referência principal: TCC de Elivandro Oliveira Grippa (seção 3.4)
Método dos gradientes conjugados para minimização de quadráticas
Referência principal: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (seção 5.3 do livro publicado pela Cengage)
Otimização com restrições
Referência principal: Friedlander, A. Elementos de Programação Não-Linear (seções 13.1 e 13.2)
Métodos para otimização com restrições lineares
Referência principal: Friedlander, A. Elementos de Programação Não-Linear
Métodos para otimização com restrições gerais
Referência principal 1: Friedlander, A. Elementos de Programação Não-Linear Referência principal 2: Martínez, J. M. Otimização prática usando o Lagrangiano aumentado (capítulo 2) Referência complementar: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização
Tópicos extras
Introdução à complexidade de algoritmos
Breve introdução à otimização aplicada ao aprendizado de máquina supervisionado
- Introdução
- Método do gradiente incremental
- Um pouco de probabilidade
- Método do gradiente estocástico (SG) e variantes
- Convergência do método do gradiente estocástico para funções convexas
- Treinamento de redes neurais multicamadas tipo feedfoward, backpropagation
- Experimentos numéricos
- Método do gradiente clássico, incremental e estocástico
- Um pacote para aprendizado de máquina em Julia: Flux.jl
- Código exemplo de uso do Flux no dataset MNIST
- Sobre o dataset MNIST: wikipedia
- EXERCÍCIOS
- Referências:
- Bottou, L; Curtis, F. E.; Nocedal, J. Optimization Methods for Large-Scale Machine Learning. SIAM Rev., 60(2), 223-311 (2018). artigo revista; PDF acesso livre
- (introdução gradiente incremental – seção 2.1.5) Bertsekas, D. P. Convex Optimization Algorithms. Athena Scientific, 2015.
- (gradiente incremental/estocástico e convergência – seções 8.3, 8.4) Beck, A. First-Order Methods in Optimization. MOS-SIAM Series on Optimization, SIAM, 2017.
- Livro on-line “Neural Networks and Deep Learning”
Para mais informações, veja o Tópico 5 deste link.
Método do gradiente projetado para restrições convexas quaisquer
Comparação do desempenho de diferentes algoritmos
Referência 1: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (seção 6.3 do livro publicado pela Cengage) Referência 2: Dolan, Elizabeth D.; Moré, Jorge J. Benchmarking optimization software with performance profiles. Math. Program., Ser. A 91: 201-213 (2002). artigo revista; PDF acesso aberto
- ANOTAÇÕES - Perfis de desempenho segundo Dolan e Moré e comentários sobre contagem de tempo de execução
- BenchmarkProfiles.jl - gerando perfis de desempenho com o Julia
- EXERCÍCIOS
Códigos em Julia
Obs: Em novas versões de um pacote, comandos antigos podem deixar de funcionar. Logo, caso algum código apresente erro, pode ser devido à comandos obsoletos. Avise-me para que eu atualize os códigos.