Otimização 1

Horários das aulas

• Segundas-feiras de 16:00 as 18:00 (Sala 07 Eixo 3, LABMAT)
• Terças-feiras de 12:00 as 14:00 (Sala 09 Eixo 3, LABMAT)

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.

Avaliações

Avaliação 1

• Conteúdo: conceitos básicos, condições de otimalidade para otimização irrestrita, métodos de descida gerais (gradiente, Newton, quase-Newton, método do gradiente espectral)
• Valor: 10,0 pontos
• Data limite: 25/05/26

A avaliação consiste no seguinte:

• para estudantes de matemática: entrega de lista de exercícios OU estudo de artigo selecionado.
• para estudantes de ciência da computação: entrega de lista de exercícios OU trabalho computacional OU estudo de artigo selecionado.

No caso de trabalho computacional e artigo, o(a) estudante será arguido pelo professor individualmente. No caso de artigo, o(a) estudante deverá reproduzir os testes do artigo na medida do possível. Testes adicionais são sempre bem vindos. No caso de artigo, caso a qualidade do trabalho realizado seja excepcional, o(a) estudante poderá ser dispensado de novas avaliações. Não é preciso estudar/reproduzir os teoremas de convergência.

• Lista de exercícios
  • exercícios 2.5, 2.10, 2.12, 2.17, 4.2, 4.8, 6.4, 6.9 do livro de Ana Friedlander
  • exercícios 3, 4, 6, 16, 19 da Lista 1
  • exercícios 3, 5, 9(b-e) da Lista 3
• Trabalhos computacionais
  1. Método do gradiente espectral: descrição; código base
  2. Método dos gradientes conjugados: descrição; código base
• Artigos selecionados (caso não consiga baixar, envie email para secchinleo@gmail.com solicitando o PDF)

  1. Liang, Xu, Bao, Quan, Ji. Barzilai–Borwein-based adaptive learning rate for deep learning. Pattern Recognition Letters 128:197-203, 2019
     Este artigo apresenta um método tipo gradiente espectral (também chamado de Barzilai-Borwein na literatura) para treinamento de redes neurais no contexto do aprendizado de máquina supervisionado. Caso use o Julia, datasets para aprendizado de máquina podem ser obtidos via os pacotes MLDatasets.jl ou OpenML.jl.

  2. Luengo, Raydan. Gradient method with dynamical retards for large-scale optimization problems. Eletronic Transactions on Numerical Analysis 16:186-193, 2003
     Em análise. Descrição em breve.

  3. Dai, Yuan, Yuan. Modified Two-Point Stepsize Gradient Methods for Unconstrained Optimization. Computational Optimization and Applications 22:103-109, 2002
     Em análise. Descrição em breve.

  4. Martínez, Pilotta, Raydan. Spectral Gradient Methods for Linearly Constrained Optimization. Journal of Optimization Theory and Applications 125:629–651, 2005
     Em análise. Descrição em breve.

  5. Luengo, Raydan, Glunt, Hayden. Preconditioned spectral gradient method. Numerical Algorithms 30:241–258, 2002
     Neste artigo é proposto uma modificação do método do gradiente espectral em que a direção do gradiente é “corrigida” por uma aproximação da Hessiana da função objetivo. É obrigatório reproduzir apenas os testes da seção 4.1, cujos problemas estão disponíveis no Julia via pacote NLSProblems.jl. A correspondência entre os problemas da Tabela 1 do artigo e os códigos do pacote pode ser consultada neste link.

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)

• 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.

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
  • 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 lineares

Referência principal: Friedlander, A. Elementos de Programação Não-Linear

• 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

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

• 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

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.

• 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
• Ilustra a necessidade da condição do ângulo no método geral de descida
• Gráfico que ilustra as diferentes ordens de convergência

Tópicos extras

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

Breve introdução à otimização aplicada ao aprendizado de máquina supervisionado

• Veja o Tópico 5 deste link

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