Sobre o curso

Aqui você vai encontrar uma descrição geral do curso e um resumo dos tópicos que pretendo abordar, bem como alguns dos pré-requisitos para um bom acompanhamento.

Descrição e objetivos

Programação semidefinida é uma poderosa generalização de programação linear que se tem tornado cada vez mais relevante no universo dos métodos de otimização, tanto pelo seu poder como ferramenta de modelagem dos mais diversos tipos de problema, quanto pela existência de métodos eficientes (na teoria e na prática) para resolver problemas de programação semidefinida.

O objetivo deste curso é oferecer uma idéia geral do que é programação semidefinida e de suas aplicações. Ao final do curso espera-se que você:

• Saiba o que são problemas de programação semidefinida;
• Tenha uma boa idéia da teoria de programação semidefinida, e uma idéia geral dos algoritmos utilizados para resolver problemas de programação semidefinida;
• Conheça algumas das principais aplicações de programação semidefinida;
• Possa modelar diversos tipos de problemas como problemas de programação semidefinida;
• Possa resolver no computador problemas de programação semidefinida.

Abaixo está uma lista de tópicos que pretendo cobrir:

• Programação cônica e teoria de dualidade;
• Complexidade de programação semidefinida: o método dos elipsóides;
• Noções de algoritmos de pontos interiores para programação semidefinida;
• Polinômios positivos e somas de quadrados, otimização polinomial;
• Aplicações à otimização combinatória: relaxações de problemas 0-1 de programação inteira, algoritmos de aproximação (MAXCUT e a desigualdade de Grothendieck), conjuntos independentes, colorações de grafos e o número teta de Lovász;
• Hierarquias de problemas de programação semidefinida;
• Aplicação à códigos binários: o limitante de Delsarte e o uso de simetria em programação semidefinida;
• Aplicações à geometria: códigos esféricos, conjuntos que evitam distâncias, empacotamentos de corpos.

Pré-requisitos

O curso não possui pré-requisitos formais, mas é necessária uma certa maturidade matemática. Ter bom conhecimento de álgebra linear (incluindo autovalores, autovetores, etc.) é certamente importante. Ter experiência em programação também é útil, assim como ter alguma experiência com programação linear.

Conceitos fundamentais de análise e topologia, como conjuntos fechados e abertos, compacidade, funções contínuas, etc., também são importantes. Mais ou menos ao final do curso, algumas aplicações em geometria necessitam de certa familiaridade com conceitos mais avançados de análise, como medidas, integral de Lebesgue, operadores, etc. Tentarei o máximo possível fornecer o que é necessário durante o curso.

A bibliografia recomendada contém alguns livros que podem ser usados para suprir alguns dos pré-requisitos descritos acima.