Material e bibliografia

Bibliografia recomendada

A fonte que seguirei mais de perto são as notas de aula de Monique Laurent e Frank Vallentin; você pode baixá-las na seção de arquivos mais abaixo.

Não pretendo seguir de perto nenhum dos livros abaixo, mas são certamente recomendáveis.

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

Para os que precisam relembrar conceitos básicos de álgebra linear, recomendo o seguinte livro:

• S. Lang, Introduction to linear algebra, Springer-Verlag, New York, 1986.

Já para os que precisam relembrar alguns conceitos fundamentais de topologia e análise, recomendo o seguinte livro:

• G.F. Simmons, Introduction to Topology and Modern Analysis, McGraw-Hill, 1963.

Um livro mais avançado e muito bom sobre análise funcional, que pode ser útil mais ao final do curso, é o seguinte:

• F. Riez e B. Sz-Nagy, Funcional Analysis, Dover Books on Advanced Mathematics, Dover Publications, Inc., New York, 1990.

Software

Pretendo que o curso tenha uma forte parte experimental, para que os participantes aprendam a resolver problemas de programação semidefinida na prática.

Há muitos solvers para programação semidefinida que podem ser encontrados na Internet. Dois dos que eu recomendo são:

• CSDP: é um solver escrito em linguagem C, que pode ser utilizado como aplicativo stand-alone ou como biblioteca;
• SDPA: é uma família de solvers para programação semidefinida que inclui solvers que utilizam aritmética de alta-precisão.

Resolver problemas de programação semidefinida é uma aventura muito maior do que resolver problemas de programação linear, por exemplo, pois surgem diversas questões acerca de estabilidade numérica, precisão, etc., que não são freqüentes ao se resolver problemas de programação linear. Por isso, é interessante usar diversos solvers e comprar os resultados. Uma forma conveniente de ficar por dentro dos solvers que existem é através do NEOS server for optimization, que disponibiliza uma lista de solvers para diversos tipos de otimização que podem ser inclusive utilizados online.

Gerar entrada para os solvers pode ser um problema complicado em si mesmo. Uma forma conveninente de gerar entrada para os solvers e analisar os resultados é utilizar o software de manipulação matemática SAGE, que é baseado em Python. Eu recomendo fortemente que você instale o SAGE, que é software livre, e aprenda a usá-lo. Durante o curso pretendo dar algumas noções de como usar o SAGE.

Eu também escrevi uma biblioteca em C++ e SAGE, chamada SDPSL, que pode ser utilizada para gerar entrada para os solvers e analisar os resultados.

Arquivos para download

laurentv.pdf

Notas de aula de Monique Laurent e Frank Vallentin. Serão seguidas mais ou menos de perto durante o curso.

lovasz.pdf

Notas de aula de L. Lovász.

csdp.py

Módulo simples para usar o CSDP através do SAGE.

maxcut.sage

Função SAGE para resolver a relaxação do MAXCUT.

sage.pdf

Slides sobre SAGE, aula de 13.03.

sdpa.pdf

Slides sobre formato SDPA, aula de 13.03.

ell.pdf

Notas de aula sobre método dos elipsóides.

sym.pdf

Notas de aula sobre exploração de simetria em programação semidefinida.

Listas de exercício

lista0.pdf

Preliminares sobre álgebra linear. Entrega: 11.03.

lista1.pdf

Resolução de problemas de programação semidefinida com o computador. Veja o módulo para utilizar o CSDP através do SAGE e o exemplo de como resolver a relaxação do MAXCUT através do SAGE colocados na área de downloads. Entrega: 25.03.

lista2.pdf

Dualidade e método dos elipsóides. (Para treinar mais a noção de dualidade, faça alguns exercícios das notas de aula de Monique Laurent e Frank Vallentin.) Entrega: 08.04.

lista3.pdf

Desigualdade de Grothendieck, MAXCUT, etc. Entrega: 24.04.