Um Método de Ponto Interior para Programação Semidefinida

Propomos um novo método baseado em ponto interior para minimizar uma função linear de uma variável matriz sujeita a restrições lineares de igualdade e desigualdade sobre o conjunto de matrizes semidefinidas positivas. Mostramos que a abordagem é muito eficiente para problemas de bisseção de grafos, como o max-cut. Outras aplicações incluem problemas de autovalores max-min e relaxamentos para o problema do conjunto estável.