Resolução de programas semidefinidos em tempo polinomial

Sabemos que os programas lineares (LP) podem ser resolvidos exatamente em tempo polinomial usando o método elipsóide ou um método de ponto interior como o algoritmo de Karmarkar. Alguns LPs com número super-polinomial (exponencial) de variáveis / restrições também podem ser resolvidos em tempo polinomial, desde que possamos projetar um oráculo de separação de tempo polinomial para eles.

E os programas semidefinidos (SDP)? Quais classes de SDPs podem ser resolvidas exatamente no tempo polinomial? Quando um SDP não pode ser resolvido exatamente, sempre podemos projetar um FPTAS / PTAS para resolvê-lo? Quais são as condições técnicas sob as quais isso pode ser feito? Podemos resolver um SDP com número exponencial de variáveis / restrições em tempo polinomial, se pudermos projetar um oráculo de separação de tempo polinomial para ele?

Podemos resolver os SDPs que ocorrem em problemas de otimização combinatória (MAX-CUT, gráfico colorido) com eficiência? Se pudermos resolver apenas dentro de um fator de , isso não afetará os algoritmos de aproximação de fator constante (como 0,878 para o algoritmo MAX-CUT de Goemans-Williamson)? $1+\epsilon$

Qualquer boa referência sobre isso será muito apreciada.

linear-programming semidefinite-programming convex-optimization Arindam Pal
fonte

Na verdade, o método funciona para programação convexa em geral

Suresh Venkat

Há pelo menos duas razões pelas quais você não pode resolver um SDP geral em tempo polinomial. (1) Existem SDPs cuja solução é de tamanho exponencial. (2) SDPs podem codificar o problema da soma das raízes quadradas, que não é conhecido por ser polinomial em tempo solucionável.

precisa

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

@SureshVenkat: Digamos que temos uma matriz 2x2 com entradas [ab; CD]. Suponha que seja semidefinido positivo ed = 1. Isso significa b = ce a> = b ^ 2. Então b é superior delimitado pela raiz quadrada de a. Agora podemos maximizar a soma de vários desses b's. O valor ótimo será a soma das raízes quadradas dos respectivos a's.

224126 Robin Ontário

Não é multiplicativo, mas aditivo. Além disso, en.wikipedia.org/wiki/Semidefinite_programming#Algorithms

Suresh Venkat

Resolução de programas semidefinidos em tempo polinomial

Respostas: