Otimização 2
Horários das aulas
- —
- —
Ementa e programa
Objetivos da disciplina
- Estudar conceitos de programação não linear com restrições
- Estudar os fundamentos dos métodos de resolução clássicos para programação não linear, sobretudo com restrições
- Analisar aspectos teóricos e numéricos dos métodos
- Implementar algoritmos em computador e testá-los em problemas da literatura
- Promover a utilização de pacotes computacionais, discutindo seu comportamento numérico à luz da teoria (discussão de artigos científicos e manuais)
Textos de referência
- Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização
- Martínez, J. M. Otimização prática usando o Lagrangiano aumentado
- Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (uma versão alternativa similar neste link)
- Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008.
- Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006.
- 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)
Textos complementares
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.
Listas de exercícios
- LISTA 0 - Revisão, condições KKT
- LISTA 1 - Métodos de penalização externa e Lagrangiano aumentado
- Código para o exercício 5(c): plbin.jl
- Instâncias para o exercício 7: portfolio.zip
- LISTA 2 - Método de penalização interna / pontos interiores
- LISTA 3 - Região de confiança
- LISTA 4 - Programação quadrática sequencial e dualidade
- LISTA 5 - Quadrados mínimos
Trabalhos computacionais
- Método de pontos interiores aplicado à programação linear: descrição
Material
A linguagem de programação Julia
Julia é uma linguagem de programação de alto nível surgida 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 todos os exemplos do link acima, especialmente 6, 7, 8, 9 e 12.
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)
Introdução; as condições de Karush-Kuhn-Tucker (KKT)
Penalização externa
Referência: Martínez, J. M. Otimização prática usando o Lagrangiano aumentado
- Penalização externa pura [ANOTACOES] [QUADRO]
- Convergência do esquema de penalização externa e prova das condições KKT [ANOTACOES]
- Exercicios: veja LISTA 1
Método do Lagrangiano aumentado
Referência: Martínez, J. M. Otimização prática usando o Lagrangiano aumentado
- O método de Lagrangiano aumentado “Algencan” [ANOTACOES]
- Convergência teórica de Algencan [ANOTACOES]
- Pacote computacional livre Algencan
- Sítio oficial
- Referências bibliográficas do Algencan:
- 1. artigo inicial (versão alternativa com acesso livre)
- 2. livro
- 3. texto em português com acesso livre
- Pacote Julia
NLPModelsAlgencan.jl. Veja pré-requisitos para instalação em neste link
- Exercicios: veja LISTA 1
Penalização interna / barreiras / pontos interiores
Referência: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização
- Penalização interna / Pontos interiores [ANOTACOES]
- Pacote computacional livre Ipopt [ANOTACOES]
- Sítio oficial
- Documentação oficial
- Referência bibliográfica do Ipopt (versão alternativa com acesso livre)
- Lista de opções configuráveis no pacote
- Pacote Julia
NLPModelsIpopt.jl. Veja informações neste link
- Pontos interiores para programação linear [ANOTACOES] [Contas direção Newtoniana - veja pgs 1 a 5 deste link]
- Uma implementação de pontos interiores para PL em Julia: pacote
Tulip.jl - Código com testes comparando: (1) simplex do CPLEX; (2) pontos interiores do CPLEX e (3) pontos interiores do Tulip
- Uma implementação de pontos interiores para PL em Julia: pacote
- Exercicios: veja LISTA 2
Conteúdo extra
- Outros pacotes (proprietários) que empregam a técnica de penalização interna
- Veja o algoritmo de barreira do CPLEX (barrier algorithm) para problemas lineares, quadráticos, e quadráticos com restrições quadráticas
- Leia a descrição do software KNITRO
- Leia a descrição do software GUROBI
- Material adicional sobre pontos interiores para programação linear
- Detalhes sobre métodos de pontos interiores especializados para PL: veja o Tóptico 1 da disciplina Tópicos em Pesquisa Operacional
- Pontos interiores aplicado à Programação Linear
Estratégia de regiões de confiança
Referência 1: Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014 (versão alternativa)
Referência 2: Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006
- Estratégia de regiões de confiança e convergência global [ANOTACOES]
- O passo de Cauchy e o método dog-leg [ANOTACOES]
- Exercicios: veja LISTA 3
Programação quadrática sequencial
Referência: Martínez, J. M.; Santos, S. A. Métodos computacionais de otimização
- Programação Quadrática Sequencial (SQP) básica para restrições de igualdade [ANOTACOES]
- Boa definição do SQP básico e algumas questões práticas do método [ANOTACOES]
- Subproblemas de SQP - questões práticas e problemas com restrições de desigualdade [ANOTACOES]
- Pacote computacional WORHP (proprietário com licença para uso acadêmico)
- Site do desenvolvedor
- Principal referência bibliográfica do pacote
- Outra referência com acesso livre
- Roteiro para instalar o WORHP e usá-lo no Julia (testado em nov/2023)
- Exercicios: veja LISTA 4
- (Conteúdo extra) Pacote proprietário com versão de demonstração junto ao AMPL: SNOPT
O Problema de quadrados mínimos linear e não-linear
Referência: Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006
- Quadrados mínimos linear [ANOTAÇÕES]
- Quadrados mínimos não linear - método de Gauss-Newton [ANOTAÇÕES]
- Quadrados mínimos não linear - método de Levenberg-Marquardt [ANOTAÇÕES]
- Exercicios: veja LISTA 5
Dualidade em programação não linear
Referência 1: Izmailov, A.; Solodov, M. Otimização vol 1. SBM.
Referência 2: Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008
- Dualidade em Programação Não Linear, parte 1 [QUADRO]
- Dualidade em Programação Não Linear, parte 2 [QUADRO]
- Método de planos de corte / Resolução de sistemas de inequações convexas [QUADRO]