O que pode ser resolvido com a programação semidefinida que não pode ser resolvida com a programação linear?

9

Eu estou familiarizado com programas lineares, pois eles podem resolver problemas com funções objetivas lineares e restrições lineares. Mas o que a programação semidefinida pode resolver que a programação linear não pode? Eu já sei que programas semidefinidos são uma generalização de programas lineares.

Além disso, como se reconhece um problema que pode ser resolvido usando a programação semidefinida? Qual é um problema típico para o qual a programação semidefinida é usada e que não pode ser resolvida via programação linear?

Muito obrigado por qualquer resposta.

linear-programming convex-optimization semidefinite-programming user11094
fonte
2
Talvez você possa tornar sua pergunta mais precisa? Afinal, a programação linear é concluída. P
Kristoffer Arnsfelt Hansen
5
@KristofferArnsfeltHansen Eu nunca paro de me perguntar por que as pessoas continuam trazendo esse fato para discussões semelhantes. P-completude é irrelevante, a menos que falemos em separar P de L ou NC - se estivermos falando em polytime, tudo em P é "P-complete". Para sugerir uma resposta para o OP: depois de corrigir uma codificação linear de um problema (por exemplo, escrever como otimizar uma funcionalidade linear sobre um polítopo), faz todo o sentido perguntar se um LP / SDP polisizado pode resolver o problema.
Sasho Nikolov

Respostas:

18

Um problema típico é o MaxCut: gera um corte em um gráfico que (aproximadamente) maximiza o número de arestas cortadas. Goemans e Williamson mostraram que um SDP aproxima o valor do MaxCut a um fator de pelo menos 0,878. Recentemente, Chan, Lee, Raghavendra e Steurer mostraram que, para uma codificação linear natural do problema MaxCut, todos os LPs de tamanho polinomial alcançam uma aproximação melhor que 0,5.

É difícil dizer de forma concisa que tipo de problemas geralmente se beneficiam de um SDP. Uma abordagem sistemática para construir relaxamentos de SDP é através de hierarquias, a mais poderosa das quais é a hierarquia de Lasserre: veja a pesquisa de Rothvoß para uma boa introdução. Até agora, existem muitos exemplos de sucessos de SDPs na otimização para listar. Além disso, Raghavendra mostrou que um SDP em particular fornece a melhor aproximação para todos os problemas do MaxCSP, se a conjectura dos Unique Games for verdadeira.

Veja os livros de Gaertner e Matousek , capítulos 6 e 13 do livro de Willimson e Shmoys , a pesquisa de Lovasz .

Sasho Nikolov
fonte
12

Para muitos problemas de otimização combinatória (por exemplo, Max-Cut), a programação semidefinida produz relaxações muito mais fortes do que o relaxamento LP das formulações IP. Isso permite o design de algoritmos de aproximação e de algoritmos exatos que são mais eficientes do que seus equivalentes lineares devido à melhor qualidade dos limites. Exemplos podem ser encontrados na tese de Habilitação de Christoph Helmberg , nesta pesquisa e nesta página do curso .

Outra sequência recente de resultados espetaculares que usam a programação semidefinida é a aplicação das álgebras de bandeira de Razborov para provar resultados em problemas do tipo Turan (veja esta pesquisa e o projeto emblemático ).

Thomas Kalinowski
fonte