Otimização 1

Horários das aulas

• Quartas-feiras de 11:00 as 13:00 (Sala 09 Eixo 1)
• Sextas-feiras de 07:00 as 09: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

• Avaliação 1
  • Lista de exercícios
  • Conteúdo: conceitos básicos, condições de otimalidade para otimização irrestrita
  • TAREFAS A SEREM ENTREGUES:
    • exercícios 2.5, 2.10, 2.12 do livro de Ana Friedlander
    • exercícios 2, 3, 4, 5, 6, 8, 16, 19 da Lista 1
  • Valor: 10,0 pontos
  • Data limite: 10/05/24
• Avaliação 2
  • Valor: 10,0 pontos
  • Data: –
• Avaliação 3
  • Valor: 10,0 pontos
  • Data: –
• Avaliação 4
  • Valor: 10,0 pontos
  • Data: –
• PROVA FINAL
  • Prova escrita
  • Conteúdo: toda a matéria
  • Valor: 10,0 pontos
  • Data: –

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)

• ANOTAÇÕES - Conceitos básicos
• VÍDEO: Uma visão geral da otimização - fala do prof. Jose Mario Martinez (Unicamp)

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)

• ANOTAÇÕES - Otimização sem restrições

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)

• ANOTAÇÕES - Convexidade

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

Para auxiliá-lo na instalação do Julia pré-compilado + pré-requisitos + pacotes utilizados nas disciplinas de otimização, baixe ESTE SCRIPT e siga as instruções contidas nele (testado no Ubuntu 22.04)

Métodos para otimização sem restrições

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
  • Leitura interessante: Artigo sobre o desenvolvimento da ideia Newtoniana ao longo dos anos (download acessando pela Universidade)
• 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)

• ANOTAÇÕES - Métodos quase-Newton tipo secante

Método do gradiente espectral

Referência principal: TCC de Elivandro Oliveira Grippa (seção 3.4)

• ANOTAÇÕES - Método do gradiente espectral

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)

• ANOTAÇÕES - Método dos gradientes conjugados

Otimização com restrições

Referência principal: Friedlander, A. Elementos de Programação Não-Linear (seções 13.1 e 13.2)

• ANOTAÇÕES - Otimização com restrições; condições de Karush-Kuhn-Tucker (KKT)

Métodos para otimização com restrições

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

• ANOTAÇÕES - Minimização com restrições lineares de igualdade (método do gradiente projetado para restrições lineares)
• ANOTAÇÕES - Minimização com restrições lineares de desigualdade; método das restrições ativas
• ANOTAÇÕES - Penalização externa
• ANOTAÇÕES - Penalização interna
• ANOTAÇÕES - Programação Quadrática Sequencial (SQP, do inglês) - algoritmo básico
• ANOTAÇÕES - Pontos interiores para problemas com restrições lineares
• ANOTAÇÕES - SQP para restrições não lineares de igualdade e desigualdade

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

Breve introdução à otimização aplicada ao aprendizado de máquina supervisionado (a fazer)

Outros

• ANOTAÇÕES - Método do gradiente com passo constante e introdução à complexidade de algoritmos
• ANOTAÇÕES - Método do gradiente projetado para restrições convexas quaisquer

Vídeos interessantes sobre Otimização

• IMECC Unicamp no facebook
• Grupo de Otimização IMECC Unicamp