Introdução à Otimização (2018/1 e 2016/2)

Para os cursos de graduação em Matemática Aplicada, e os cursos de mestrado em Matemática Aplicada e Matemática.

Motivação

Este curso pretende ser, ao mesmo tempo, uma ocasião para apresentar resultados matemáticos relativamente recentes, e continuar a familiarização dos alunos com os processos de Modelagem Matemática, sensibilizando ao mesmo tempo o entendimento conceitual e a necessidade de métodos efetivos para solução computacional de problemas.

Requisitos

Cálculo II e Álgebra Linear, familiaridade com Programação (digamos Científica I bem feita, ou dois cursos de programação), um pouco de Probabilidade.

Linguagens: a priori, qualquer linguagem suportada pela família CVX* pode ser usada. No momento, isso inclui Python (CVXPY), R (CVXR), Julia (Convex.jl) e MATLAB (CVX). Outras linguagens mais esotéricas (ou especializadas), me consultar.

Estrutura do curso

A priori, uma aula teórica e uma aula prática por semana.

Aulas: sondagem de horário

Ementa

  • Análise convexa: conjuntos convexos, funções convexas, problemas de otimização convexos, dualidade.
  • Exemplos de problemas de otimização: Programação linear e aplicações, programação quadrática e aplicações, modelos mais gerais.
  • Otimização diferenciável: Condições de optimalidade, Métodos de solução, Análise de convergência local e global
  • Aplicações: Otimização robusta, Otimização estocástica, Controle ótimo, ...

Nesta edição de 2018, a parte de subgradientes será material apenas para os alunos de mestrado.

Bibliografia

Usaremos, principalmente, o livro Convex Optimization, por Stephen Boyd & Lieven Vandenberghe. Cambridge University Press.

Referências mais avançadas / especializadas são:

  • Nonlinear Optimization, por Andrzej Ruszczyński. Princeton University Press.
  • Introduction to Linear Optimization, por Dimitris Bertsimas and John N. Tsitsiklis.

Objetivos do curso

Espero que ao final do curso você saiba:
  • Modelar situações como problemas de otimização, e saber algumas técnicas para converter entre tipos de modelos;
  • Conhecer os tipos "básicos" de otimização (convexo vs geral; linear vs quadrático vs geral; contínuo vs discreto; determinístico vs estocástico), as vantagens e limitações de cada um;
  • Saber analisar alguns métodos de solução para problemas de otimização;
  • Entender como os métodos podem ser usados "dentro de um problema maior / mais geral" onde a otimização é "só um passo".

Instalando o CVXPY:

De http://www.cvxpy.org/en/latest/install/

- Instale o Anaconda
- conda install -c cvxgrp cvxpy


  • 2018/1
  • 2016/2
    • Aulas: Segundas e quartas, das 13h às 15h.
    • Aula 0: Apresentação do curso.
    • Aula 1: Conjuntos e funções convexas.
    • Aula 2: Problemas de otimização, forma-padrão.
    • Lista 1 para dia 19 de Setembro.
      • Boyd, capítulo 2: exercícios 2, 3, 7, 9, 11, 12, 14, 16 - Mestrado: fazer também 9c, 12fg, 15, 17, 19
      • Boyd, capítulo 3: exercícios 1, 3, 4, 6, 7, 14 - Mestrado: também 10
    • Aula 3: Cones e cones duais.
    • Aula 4: Biduais, cones normais, pontos extremos. Subdiferencial.
    • Aula 5: Propriedades do subdiferencial. Condições de optimalidade.
    • Lista 2 para dia 30 de Setembro.
      • Boyd, capítulo 3: exercícios 16, 19, 26, 30, 32 - Mestrado: também 23, 24
      • Ruszczyński, capítulo 2: exercícios 2, 5, 9, 10, 14 - Mestrado: também 8, 13
    • Aula 6: Programação Linear: forma-padrão, soluções básicas. Exemplos.
    • Aula 7: Restrições: penalização, relaxação e dualidade de Lagrange.
    • Aula 8: Dualidade em Programação Linear. Exemplos numéricos e variáveis duais, com exercício.
    • Aula 9: Dualidade Forte em Programação Linear.
    • Aula 10: Dualidade Forte para problemas convexos: condições de Slater. Projeção L^1, com exercício.
    • Aula 11: Condições de otimalidade de segunda ordem.
    • Lista 3 para dia 26 de Outubro
      • Boyd, capítulo 5: exercícios 1, 4, 6, 10, 15, 18 - Mestrado: também 2, 7, 19
    • Aula 12: Métodos de otimização em dimensão 1.
    • Aula 13: Métodos de otimização em dimensão 2 e mais: gradientes.
    • Aula 14: Método de Newton.
    • Aula 15: Barreira logarítmica e Newton com restrições.
    • Prova 1: Análise convexa. Mestrado, Graduação.
    • Aula 16: Exemplos de otimização: normas e penalidades.
    • Lista 4 = Prova 1' para dia 25 de Novembro: Multiplicadores de Lagrange.
    • Aula Final: L1 Tricks e aproximação de funções
UFRJ Departamento de Matemática Aplicada - Instituto de Matemática - UFRJ
Valid XHTML 1.1 Valid CSS! Desenvolvido por: Bernardo Freitas Paulo da Costa Inspirado do padrão: TIC/UFRJ