MAC0343  Otimização Semidefinida e Aplicações

Por | Em

Até 2016 se chamou MAC0343 Programação Semidefinida e Aplicações.

OBJETIVOS:  Programação semidefinida é uma poderosa extensão de programação linear. Neste curso vemos a teoria de programação semidefinida bem como inúmeras aplicações em otimização combinatória, teoria de códigos e otimização polinomial. Técnicas de programação semidefinida têm encontrado inúmeras aplicações em matemática, logística, engenharia, etc. Tais técnicas constituem uma parte essencial das ferramentas de otimização disponíveis.

PROGRAMA RESUMIDO:  Dualidade, complexidade computacional e métodos de pontos interiores; Como resolver problemas de programação semidefinida no computador; Aplicações à otimização combinatória: relaxações de problemas 0-1, algoritmos de aproximação (MaxCut, Max-2Sat, etc.), conjuntos independentes e o número teta de Lovász; Hierarquias de programação semidefinida para politopos 0-1; Aplicações a códigos binários: o limitante de Delsarte e o uso de simetria em problemas de programação semidefinida; Somas de quadrados e polinômios positivos; otimização polinomial.

PROGRAMA:  Dualidade, complexidade computacional e métodos de pontos interiores; Como resolver problemas de programação semidefinida no computador; Aplicações à otimização combinatória: relaxações de problemas 0-1, algoritmos de aproximação (MaxCut, Max-2Sat, etc.), conjuntos independentes e o número teta de Lovász; Hierarquias de programação semidefinida para politopos 0-1; Aplicações a códigos binários: o limitante de Delsarte e o uso de simetria em problemas de programação semidefinida; Somas de quadrados e polinômios positivos; otimização polinomial.

PRÉ-REQUISITOS:  MAC0315.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA: 

  • A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Appllications, SIAM, 2012.
  • L. Tunçel, Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, American Mathematical Society, Providence, 2010.
  • B. Gärtner, J. Matousek, Approximation Algorithms and Semidefinite Programming, Springer-Verlag, Berlin, 2012.
  • S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
  • A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
  • A. Barvinok, A Course in Convexity, American Mathematical Society, Providence, 2002.

OBSERVAÇÃO:  Disciplina optativa eletiva nos currículos do BCC.

 

[Veja dados da disciplina no JúpiterWeb]