Introdução à Otimização (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

Requisitos

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

Linguagens: a priori, qualquer linguagem dentre C(++), Java, Python pode ser usada. Outras linguagens mais exotéricas (ou especializadas), me consultar.

Estrutura do curso

A priori, uma aula teórica e uma aula prática por semana, mas pode ser ajustado.

Aulas: Segundas e quartas, das 13h às 15h.

Ementa

  • Otimização diferenciável: Condições de optimalidade, Métodos de solução, Análise de convergência local e global
  • Programação linear: Definição, Análise convexa, Método do simplexo, Método de pontos interiores, Dualidade
  • Aplicações: Otimização robusta, Otimização estocástica, Controle ótimo

Bibliografia

  • Nonlinear Optimization, por Andrzej Ruszczyński. Princeton University Press.
  • Introduction to Linear Optimization, por Dimitris Bertsimas and John N. Tsitsiklis.
  • Convex Optimization, por Stephen Boyd & Lieven Vandenberghe. Cambridge University Press.

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


Instalando o CVXOPT no ubuntu+anaconda

Só se você quiser usar o solver do CVXOPT com o CVXPY, mas não deve ser mais necessário.
sudo apt-get install libglpk-dev
cd /home/my_user_here/anaconda3/bin
./pip uninstall cvxopt
sudo CVXOPT_BUILD_GLPK=1 ./pip install cvxopt


  • 2016/2
    • 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
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