Otimização 2
Horários das aulas
- Terças-feiras de 12:00 as 14:00 (Sala 10 Eixo 3)
- Sextas-feiras de 10:00 as 12:00 (Sala 10 Eixo 1)
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.
Avaliações
- Avaliação 1
- Lista de exercícios
- Conteúdo: condições KKT, penalidade externa e interna, Lagrangiano aumentado e pontos interiores
- Tarefas:
- Exercícios 13.2, 13.6, 13.7
- Exercícios 3, 6, 8 da Lista 0
- Exercícios 1, 2, 5, 6, 7, 8 da Lista 1
- Exercícios 2, 3, 5, 6, 7, 9 da Lista 2
- Valor: 10,0 pontos
- Data: 13/12/24 (sexta-feira)
- Entregar resolução escrita à mão. Exercícios computacionais requerem uma discussão escrita à mão e o envio do código para o email secchinleo@gmail.com
- O trabalho é individual
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
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.
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
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 Referência para Programação Linear: J. Gondzio. Interior point methods 25 years later. European Journal of Operational Research, 218(3):587-601, 2012
- 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]
- Notas de aula
- Implementação própria e comparação com o método de pontos interiores do pacote CPLEX sobre problemas lineares da biblioteca NETLIB
- Exercicios: veja LISTA 2
Conteúdo extra
- Uma implementação de pontos interiores para PL em Julia: pacote
Tulip.jl - 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
- Detalhes sobre métodos de pontos interiores especializados para PL: veja o Tóptico 1 da disciplina Tópicos em Pesquisa Operacional
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
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
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