Otimização 1
Horários das aulas
- Quartas-feiras de 11:00 as 13:00 (Sala 09 Eixo 1)
- Sextas-feiras de 09:00 as 11:00 (Sala 12 Eixo 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. (uma versão reformulada deste livro feita em 2019 também está disponível gratuitamente – em inglês)
- Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014. (uma versão alternativa similar neste link)
- Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização
- Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008.
(disponível na biblioteca). - Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006
Textos complementares
- Izmailov, A.; Solodov, M. Otimização vol 1. SBM
- Martínez, J. M. Otimização prática usando o Lagrangiano aumentado
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.
Avaliações
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
- Quase-Newton (BFGS) globalizado: 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. A seguir você encontra instruções de instalação, bem como exemplos simples que ajudarão você a dar os primeiros passos nas ferramentas de otimização disponíveis no Julia.
- Tutorial para instalação e uso da linguagem de programação Julia
- Julia para Otimização - primeiros passos
- Estude os exemplos 1 a 5, 8, 9, 12 e 14 do link acima
- Execute os testes com o método do gradiente do tópico Métodos de descida gerais
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
Códigos em Julia
- Métodos do gradiente, Newton e Newton globalizado, com funções para testes
- “Pré-implementação” do método de gradientes conjugados para quadráticas, com função para testes
Tópicos extras
Comparação do desempenho de diferentes algoritmos
Referência principal: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (seção 6.3 do livro publicado pela Cengage)
- 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