Algoritmos exatos para programação quadrática não convexa

Esta questão é sobre problemas de programação quadrática com restrições de caixa (box-QP), ou seja, problemas de otimização do formulário

minimizar sujeito a . $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ $\mathbf{x} \in [0,1]^n$

Se fosse semi-definido positivo, tudo seria agradável, convexo e fácil, e poderíamos resolver o problema em tempo polinomial. $A$

Por outro lado, se tivéssemos a restrição de integralidade , poderíamos resolver facilmente o problema no tempo por força bruta. Para os fins desta pergunta, isso é razoavelmente rápido. $\mathbf{x} \in \{0,1\}^n$ $O(2^n \cdot \mathrm{poly}(n))$

Mas e o caso contínuo não convexo? Qual é o algoritmo mais rápido conhecido para QPs gerais em caixa?

Por exemplo, podemos resolvê-los em tempo moderadamente exponencial, por exemplo, , ou a pior complexidade dos algoritmos mais conhecidos é algo muito pior? $O(3^n \cdot \mathrm{poly}(n))$

Antecedentes: Eu tenho alguns QPs de caixa bastante pequenos que realmente gostaria de resolver e fiquei um pouco surpreso ao ver o desempenho de alguns pacotes de software comercial, mesmo para valores muito pequenos de . Comecei a me perguntar se existe uma explicação do TCS para essa observação. $n$

ds.algorithms optimization exp-time-algorithms Jukka Suomela
fonte

Você pode resolver exatamente mesmo para o PSD ? A solução pode ser irracional, não? Se você estiver disposto a perder aditivo, talvez seja possível obter um algoritmo de tempo exponencial fazendo uma pesquisa de força bruta em uma grade suficientemente fina. Apenas uma sugestão vaga.

A

$A$

ϵ

$\epsilon$

Chandra Chekuri

Desvantagem é que a "base" do expoente seria algo como , mas talvez engenharia grade inteligente pode ajudar para "pequeno"

1 / ϵ

$1/\epsilon$

n

$n$

Suresh Venkat

@ChandraChekuri: As aproximações são perfeitas se você conseguir, por exemplo, . No entanto, forçar brutalmente uma grade tão fina não é viável.

ϵ = 10^{- 9}

$\epsilon = 10^{-9}$

Jukka Suomela

Pela eliminação do quantificador em campos fechados reais, sempre é possível resolver exatamente esses sistemas.

Se for permitido, você poderá otimizar a função em cada uma das faces do cubo apenas anotando os critérios de otimização de primeira ordem.

O (3^{n})

$O(3^n)$

Yoshio Okamoto

Uma solução ideal está em algum rosto. Assim, podemos percorrer todas as faces do cubo e encontrar todos os pontos estacionários em cada uma das faces.

Aqui está um procedimento mais concreto. Uma face do cubo pode ser caracterizada por dois conjuntos de índices disjuntos $I_0$ $I_1$ $i \in I_0$ $x_i = 0$ $i \in I_1$ $x_i = 1$ $\tilde{x}$ $x$

{\tilde{x}}^{⊤} \tilde{A} \tilde{x} + {\tilde{c}}^{⊤} \tilde{x} + d,

$\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,$

$\tilde{A}$ $\tilde{c}$ $d$ $0 < \tilde{x} < 1$

Para esse fim, adotamos a diferenciação da função objetivo para obter

\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.

$\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.$

A solução desse sistema de equações lineares fornece os pontos estacionários, os candidatos a soluções ideais. Examinamos todos eles, verificamos a condição e escolhemos um com o valor objetivo mínimo.

$O(3^n \text{poly}(n))$ $n$ $3^n$ $n$

Yoshio Okamoto
fonte

f

$f$

@ cody: Isso porque todo politopo é a união disjunta de seus rostos.

Yoshio Okamoto

f

$f$

@ codigo: A propriedade ainda é válida, mas precisamos resolver uma equação algébrica de grau mais de um. Receio que isso não seja trivial para casos multivariados.

Yoshio Okamoto

Algoritmos exatos para programação quadrática não convexa

Respostas: