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 .
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.
Z drugiej strony, gdybyśmy mieli ograniczenie integralności , moglibyśmy z łatwością rozwiązać problem w czasie O ( 2 n ⋅ p o l y ( n ) ) siłą brutalną. Dla celów tego pytania jest to dość szybkie.
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?
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.
źródło
Odpowiedzi:
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.
W tym celu przyjmujemy zróżnicowanie funkcji celu
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.
źródło