Dokładne algorytmy dla niewypukłego programowania kwadratowego

13

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

  • minimalizuj zastrzeżeniem x[ 0 , 1 ] n .f(x)=xTAx+cTxx[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 O ( 2 np o l y ( n ) ) siłą brutalną. Dla celów tego pytania jest to dość szybkie.x{0,1}nO(2npoly(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(3npoly(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

Jukka Suomela
źródło
1
Aϵ
1/ϵn
ϵ=109
Dzięki eliminacji kwantyfikatora na rzeczywistych zamkniętych polach zawsze można dokładnie rozwiązać te systemy.
2
O(3n)

Odpowiedzi:

12

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.

I0I1iI0xi=0iI1xi=1x~x

x~A~x~+c~x~+d,

A~c~d0<x~<1

W tym celu przyjmujemy zróżnicowanie funkcji celu

12A~x~+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(3npoly(n))n3nn

Yoshio Okamoto
źródło
1
f
@cody: To dlatego, że każdy polytop jest rozłącznym połączeniem jego twarzy.
Yoshio Okamoto,
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