Dokładne algorytmy dla niewypukłego programowania kwadratowego

To pytanie dotyczy kwadratowych problemów programistycznych z ograniczeniami pudełkowymi (box-QP), tj. Problemów optymalizacyjnych formularza

minimalizuj zastrzeżeniem . $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ $\mathbf{x} \in [0,1]^n$

Gdyby było pozytywnie półokreślone, wtedy wszystko byłoby miłe, wypukłe i łatwe, i moglibyśmy rozwiązać problem w czasie wielomianowym. $A$

Z drugiej strony, gdybyśmy mieli ograniczenie integralności , moglibyśmy z łatwością rozwiązać problem w czasie siłą brutalną. Dla celów tego pytania jest to dość szybkie. $\mathbf{x} \in \{0,1\}^n$ $O(2^n \cdot \mathrm{poly}(n))$

Ale co z nie wypukłym ciągłym przypadkiem? Jaki jest najszybszy znany algorytm dla ogólnych QP?

Na przykład, czy możemy rozwiązać je w umiarkowanie wykładniczym czasie, np. , czy też złożoność najbardziej znanych algorytmów w najgorszym przypadku jest czymś znacznie gorszym? $O(3^n \cdot \mathrm{poly}(n))$

Tło: Mam kilka dość małych QP, które chciałbym rozwiązać, i byłem nieco zaskoczony, widząc, jak słabo radzą sobie niektóre komercyjne pakiety oprogramowania, nawet przy bardzo małych wartościach . Zacząłem się zastanawiać, czy istnieje wyjaśnienie TCS dla tej obserwacji. $n$

ds.algorithms optimization exp-time-algorithms

— Jukka Suomela
źródło

A

$A$

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

n

$n$

ϵ = 10^{- 9}

$\epsilon = 10^{-9}$

Dzięki eliminacji kwantyfikatora na rzeczywistych zamkniętych polach zawsze można dokładnie rozwiązać te systemy.

O (3^{n})

$O(3^n)$

Optymalne rozwiązanie leży na niektórych twarzach. Możemy więc przejść przez wszystkie ściany sześcianu i znaleźć wszystkie nieruchome punkty na każdej z nich.

$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$

W tym celu przyjmujemy zróżnicowanie funkcji celu

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

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

Rozwiązanie tego układu równań liniowych daje punkty stacjonarne, będące kandydatami do optymalnych rozwiązań. Przeglądamy je wszystkie, sprawdzamy warunek i wybieramy taki o minimalnej wartości celu.

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

— Yoshio Okamoto
źródło

f

$f$

@cody: To dlatego, że każdy polytop jest rozłącznym połączeniem jego twarzy.

— Yoshio Okamoto,

f

$f$

@cody: Właściwość nadal obowiązuje, ale musimy rozwiązać równanie algebraiczne stopnia więcej niż jeden. Obawiam się, że nie jest to trywialne w przypadkach wielowymiarowych.

— Yoshio Okamoto