Quadratische Programmierung, wenn die Matrix nicht positiv bestimmt ist

8

http://cran.r-project.org/web/packages/quadprog/quadprog.pdf

Das R-Paket quadprogscheint in der Lage zu sein, das quadratische Programmierproblem nur zu lösen, wenn die Matrix positiv definit ist.D

Es gibt jedoch einen Fall, in dem die Matrix nicht eindeutig positiv ist. sowieD

min(x2+y2−6xy)subject tox+y≤1,3x+y≤1.5,x,y≥0.

Wie kann ich ein solches Problem lösen?

r optimization user67275
quelle
Das Problem könnte mit der Tatsache zusammenhängen, dass das Quadrat, wenn es nicht positiv definitiv ist, kein lokales Minimum hat. In diesem Fall sollte es immer noch ein globales Minimum geben, da die Region begrenzt ist.
Glen_b -Rate State Monica
1
Wenn nicht PSD ist, ist das Problem nicht konvex. Jeder Gradientenabstiegsalgorithmus bringt Sie auf ein lokales Minimum, mehr oder weniger abhängig von seinem Startpunkt. Möglicherweise müssen Sie eine Heuristik erstellen, um zu entscheiden, wann die Suche beendet werden soll. D
user603
4
Es ist gar nicht so schwer zu entscheiden, auf welchem ​​Segment der Grenze das Minimum liegt. Angesichts dieser Einschränkung ist es einfach genug, sie als ein Problem zu betrachten, das ein lokales Minimum aufweist ... aber der Vorschlag von @ user603, einen Standard-Minimierungsalgorithmus wie den Gradientenabstieg zu verwenden, kann als allgemeiner Ansatz sehr nützlich sein.
Glen_b -State Monica

Antworten:

4

Es gibt Optimierungsroutinen speziell für die lokale oder globale Optimierung quadratischer Programmierprobleme, unabhängig davon, ob die Zielfunktion konvex ist oder nicht.

BARON ist ein universeller globaler Optimierer, der konvexe oder nicht konvexe quadratische Programmierprobleme bewältigen und nutzen kann.

CPLEX verfügt über einen quadratischen Programmierlöser, der mit solutiontarget = 2 aufgerufen werden kann, um ein lokales Optimum zu finden, oder = 3, um ein globales Optimum zu finden. In MATLAB kann dies mit cplexqp aufgerufen werden.

Lokale Allzweckoptimierer, die lineare Einschränkungen verarbeiten können, können ebenfalls verwendet werden, um ein lokales Optimum zu finden. Ein Beispiel in R ist https://cran.r-project.org/web/packages/trust/trust.pdf . Optimierer für R sind unter https://cran.r-project.org/web/views/Optimization.html aufgeführt .

In MATLAB kann die Funktion quadprog in der Optimization Toolbox verwendet werden, um ein lokales Optimum zu finden.

In Julia gibt es eine Vielzahl von Optimierern.

"Jeder" Gradientenabstiegsalgorithmus landet Sie möglicherweise nicht auf irgendetwas, geschweige denn auf Einschränkungen. Verwenden Sie ein Paket, das von jemandem entwickelt wurde, der weiß, was er tut.

Das bereitgestellte Beispielproblem lässt sich leicht zu einer nachweisbaren globalen Optimalität lösen. Vielleicht wird es im Laufe von mehr als 2 Jahren nicht mehr benötigt, oder vielleicht war es nie ein Beispiel, aber auf jeden Fall liegt das globale Optimum bei x = 0,321429, y = 0,535714

Mark L. Stone
quelle
1
+1. Lagrange-Multiplikatormethoden zur Lösung solcher Probleme werden routinemäßig in Kalkülklassen im zweiten Jahr unterrichtet. Mit ihnen erhält man leicht und (was entlang der Grenze ). x=9/28y=15/283x+y=3/2
whuber
1

Sie können eine Problemumgehung erstellen, indem Sie nearPDaus dem MatrixPaket Folgendes verwenden :
nearPD(D)$mat.

nearPD berechnet die nächste positive definitive Matrix.

vonjd
quelle
2
+1, da es sich um eine relativ einfache Näherungslösung handelt . (Ich kann mich nicht erinnern, diese Frage gesehen zu haben, sonst hätte ich sie selbst in einem Kommentar angegeben.) Allerdings setzt man bei Verwendung dieser Technik die negativen Eigenwerte im Wesentlichen auf Null und rekonstruiert dann die ursprüngliche Matrix. Wenn die entsprechenden Variationsmodi signifikant sind, kann diese Annäherung ernsthaft fehlerhaft sein.
usεr11852
3
Stimmen Sie dem letzten Satz im vorhergehenden Kommentar zu. Dies ist eine ausgezeichnete Technik, solange Sie sich nicht im geringsten darum kümmern, ob Ihre Antwort richtig ist oder sogar im richtigen Stadion, in der richtigen Stadt oder im richtigen Bundesstaat. Wenn Ihre objektive "hessische" Matrix innerhalb der "Toleranz" liegt und nicht positiv definitiv ist, könnte dieser Ansatz tatsächlich vernünftig sein, andernfalls nicht.
Mark L. Stone