Acelerações polinomiais com algoritmos baseados em programação semidefinida

Este é o seguimento de uma pergunta recente feita por A. Pal: Resolvendo programas semidefinidos em tempo polinomial .

Ainda estou intrigado com o tempo de execução real de algoritmos que calculam a solução de um programa semidefinido (SDP). Como Robin apontou em seu comentário à pergunta acima, os SDPs não podem ser resolvidos no tempo polinomial em geral.

Acontece que, se definirmos nosso SDP com cuidado e impormos uma condição de quão bem limitada é a região primal viável, podemos usar o método elipsóide para fornecer um limite polinomial para o tempo necessário para resolver o SDP (consulte a Seção 3.2 em L. Lovász, programas semidefinidos e otimização combinatória ). O limite dado existe um " tempo polinomial " genérico e aqui estou interessado em um limite menos grosso.

A motivação vem da comparação de dois algoritmos usados para o problema da separabilidade quântica (o problema real não é relevante aqui, portanto, não pare de ler os leitores clássicos!). Os algoritmos são baseados em uma hierarquia de testes que podem ser convertidos em SDPs, e cada teste na hierarquia está em um espaço maior, ou seja, o tamanho do SDP correspondente é maior. Os dois algoritmos que eu quero comparar diferem na seguinte troca: no primeiro, para encontrar a solução, você precisa escalar mais etapas da hierarquia e no segundo, as etapas da hierarquia são mais altas, mas você precisa escalar menos deles. É claro que, na análise dessa troca, é importante um tempo de execução preciso do algoritmo usado para resolver o SDP. A análise desses algoritmos é feita por Navascués et al. em arxiv: 0906.2731, onde eles escrevem:

... a complexidade de tempo de um SDP com variáveis e com tamanho de matriz é (com um pequeno custo extra proveniente de uma iteração de algoritmos). $m$ $n$ $O(m^2 n^2)$

Em outro artigo , onde essa abordagem do problema foi proposta pela primeira vez, os autores dão o mesmo limite, mas usam o termo mais cauteloso " número de operações aritméticas " em vez de " complexidade do tempo ".

Minha pergunta é dupla:

Qual algoritmo / limite são Navascués et al. referindo-se a?
Posso substituir a expressão "tempo polinomial" em Lovász por algo menos grosseiro (mantendo as mesmas suposições)?

quantum-information semidefinite-programming analysis-of-algorithms Alessandro Cosentino
fonte

Meu entendimento é que o método elipsóide deu respostas que estavam dentro do erro aditivo

no polinômio do tempo no

. Para a maioria dos problemas, pode-se suspeitar que

pode ser suficiente.

ϵ

$\epsilon$

\log (1 / ϵ)

$\log(1/\epsilon)$

ϵ = Ω (1 / 2^{n})

$\epsilon = \Omega(1/2^n)$

precisa

@SureshVenkat: Isso mesmo, o método elipsóide funciona em tempo polinomial no tamanho das matrizes de entrada, no tamanho das restrições e no

. O problema é que, para o aplicativo que mencionei na pergunta, dizer apenas "polinomial" não é suficiente, preciso de um limite mais preciso.

\log (1 / ϵ)

$\log(1/\epsilon)$

Alessandro Cosentino

Respostas:

Não estou familiarizado com detalhes do método elipsóide especificamente para programas semi-definidos, mas mesmo para programas lineares , a análise do método elipsóide é bastante sutil.

Primeiro, é necessário vincular o número de iterações do algoritmo elipsóide ideal . Vamos ser o ellispoid usado no th iteração do algoritmo elipsóide, e deixe ser seu centróide. No algoritmo ideal, um oráculo de separação / filiação lhe dá uma halfspace que contém o ideal ponto , mas não o centróide . O próximo elipsóide é o menor elipsóide que contém . Para cada , temos $E_i$ $i$ $c_i$ $h_i$ $x^*$ $c_i$ $E_{i+1}$ $E_i\cap h_i$ $i$ , onderepresenta a dimensão. Assim, dado um elipsóide inicial razoável, o número de iterações é polinomial eme. Calculandodeerequer (grosseiramente)operações aritméticas. Portanto, o número de operações aritméticas também é polinomial eme $vol(E_{i+1}) < (1-\frac{1}{n})\cdot vol(E_i)$ $n$ $n$ $\log(1/\varepsilon)$ $E_{i+1}$ $E_i$ $h_i$ $O(n^2)$ $n$ . $\log(1/\varepsilon)$
No entanto, algumas dessas operações aritméticas têm raízes quadradas! Segue-se que os coeficientes do ideal elipsóide são números irracionais de grau , e assim não há nenhuma esperança de realmente computação exatamente em qualquer tempo razoável. Então, ao invés, um calcula uma aproximação exterior perto a cada iteração usando aritmética de precisão finito. Grötschel, Lovasz e Schrijver provar que, se uma utilidades (digamos) bits de precisão do th iteração, ainda temos $E_i$ $2^i$ $E_{i+1}$ $\tilde{E}_i \supset E_i$ $10i$ $i$ , de modo que o número de iterações aumenta por, no máximo, um factor constante. Mas agora cada operação aritmética durante oth iteração (incluindo as operações realizadas pelo oráculo de separação) requertempo. $vol(\tilde E_{i+1}) < O(1-\frac{1}{n})\cdot vol(\tilde E_i)$ $i$ $O(i~\text{polylog}~i)$

Ao todo, o tempo total do método elipsóide de execução é muito aproximadamente o quadrado do número de operações aritméticas. Uma vez que o número de operações aritméticas é polinomial em e , de modo que o tempo de execução. $n$ $\log(1/\varepsilon)$

Jeffε
fonte

\sum_{i = 1}^{n. of iterations} O (n^{2})

$\sum_{i = 1}^{\text{n. of iterations}} O(n^2)$

\times O (i polylog i)

$\times O(i \operatorname{polylog}i)$

n

$n$

\log (1 / ϵ)

$\log(1/\epsilon)$

n

$n$

n^{2}

$n^2$

Mais uma coisa: o número de restrições também não deveria aparecer em algum lugar da análise? Além disso, isso é específico para programas lineares?

Alessandro Cosentino

Você também deve levar em consideração o tempo de execução do oráculo de separação; é aí que o número de restrições aparece. Para LPs explícitos, o oráculo de separação apenas tenta as restrições uma de cada vez. Para LPs representados implicitamente, é mais complicado.

Jeffε