Lösung für quadratisches Problem mit Box-Constraints? Algorithmus?



  • Hi alle,

    Ich bin ein echter Newbie in disen Optimierungsgeschichten. Ich weiß, dass quadratische Probleme mit beliebigen konvexen constraints schwierig sind, aber ich finde für meinen Spezialfall keine Literatur, die das bestätigt

    konkret geht es um folgendes Problem:

    \max_x L(x)= b^Tx - 1/2 x^TQx\\ 0 \leq x_i \leq 1, \quad \forall\; i = 1\dots n

    wobei x b vektoren und Q eine Matrix ist.

    Was ich nun suche ist ein algorithmus, der das analytisch löst, und nicht numerisch über Dekompositionsalgorithmen/IPM etc. Der Grund ist, dass ich nachvollziehen möchte, warum alle Welt das mit Dekompositionsalgorithmn löst, und nicht irgendwelche "intelligenteren" Methoden verwendet - dazu gibt es leider nur wenige Informationen, ausser dass mal vor vielen Jahren jemand das mit nem All-Purpose-Solver implementiert hat und das - oh wunder - langsamer war (und das Problem war auch noch ein Ticken komplizierter).

    Kennt da jemand was, was speziell dafür entwickelt wurde? Was mich am meisten interessiert ist, wie schwer es ist herauszukriegen, welche constraints in der echten Lösung aktiv sind (d.h. für welche indizes gilt x_i = 0 oder x_i = 1)

    Ich dachte zuerst, das wäre einfach und man könnte das in maximal n iterationn lösen(gegeben die Inverse von Q). Ein Bekannter meint, dass herauszukriegen, auf welcher Site des Würfels die Lösung liegt, 2^N sein könnte aber er wusste nix genaueres.

    //edit ich hasse meine tastatur





  • Hi, dank schon einmal für den Link.

    Wenn ich das richtig verstanden habe, war das nur für gleichheits-Nebenbedingungen. Das ist bei mir aber nicht anwendbar. Etwas schlimmer noch: auch das scheint wieder ein allgemeines Verfahren sein, aber ich suche speziell etwas für mein Problem.

    Es geht nicht darum, das Problem zu lösen, dafür habe ich hier sehr schnelle Algorithmen da, es geht darum, dass ich mich frag, warum gerade einfachste Algorithmen (wähle x_i, x_j mit i != j und löse das 2-d problem optimal, iteriere bis konvergenz) verwendet werden und keine anderen Verfahren. Leider ist es etwas trickreich, den Algorithmus auf beleibig große Subsets zu erweitern und ich suche gerade nach Literatur, die ich einfach auf das Problem werfen kann.



  • otze schrieb:

    Wenn ich das richtig verstanden habe, war das nur für gleichheits-Nebenbedingungen.

    Nein, das ist für Schrankennebenbedingungen (box constraints). Ich seh grade, dass das Problem (QP) am Anfang falsch formuliert ist, die i in I sind natürlich inequalities, das muss dort ≤ statt = heißen. Lies mal weiter unten, bei (QPSN).

    Etwas schlimmer noch: auch das scheint wieder ein allgemeines Verfahren sein, aber ich suche speziell etwas für mein Problem.

    Dein Problem ist: quadratische Zielfunktion, Schrankennebenbedingungen. Oder nicht? Das Verfahren ist genau dafür.



  • Ohja, Danke 🙂



  • otze schrieb:

    konkret geht es um folgendes Problem:

    \max_x L(x)= b^Tx - 1/2 x^TQx\\ 0 \leq x_i \leq 1, \quad \forall\; i = 1\dots n

    wobei x b vektoren und Q eine Matrix ist.

    Du willst wirklich L maximieren? Nicht minimieren? Wenn dem so ist, sollte die Lösung ja irgendwie auf dem Rand der Box oder sogar vielleicht in einer Ecke liegen, oder? Da bin ich mir gerade nicht sicher.

    Zum Minimieren fällt mir da der SPG ein (spectral projected gradient method).



  • Du willst wirklich L maximieren?

    Vor dem quadratischen Term steht ein Minus. Also vereinfacht f(x) = -x^2.



  • genau, knivil hat recht.

    Inzwischn hab ich einen hübschen Algorithmus gefunden:

    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.8006

    (leider ist das der einzige link der nicht vor eine paywall führt..)

    Im Kern löst der Algorithmus eine Sequenz von Gleichungssystemen. Ich habe das jetzt mit einem CG als numerische appoximation implementiert, aber wirklich schnell ist das nicht. gegenüber der einfachen Dekompositionstechnik ( http://en.wikipedia.org/wiki/Sequential_minimal_optimization) bin ich immernoch so zwischen Faktor 2 und 20 langsamer, wobei ich für Faktor 2 das Problem schon echt übel konditionieren muss.

    Schad, geht wohl wirklich nicht bsser. Mal wieder gewinnt der einfachste Algorithmus...



  • otze schrieb:

    Mal wieder gewinnt der einfachste Algorithmus...

    Ist doch super?



  • Tim schrieb:

    otze schrieb:

    Mal wieder gewinnt der einfachste Algorithmus...

    Ist doch super?

    In disem Fall nicht. Der Algorithmus hat einige Nachteile, die sich nicht so einfach lösen lassen. Zum Beispiel ist er nicht gut parallelisierbar, weil er hoch iterativ ist (im Grunde ist der Algorithmus nur 2 Schleifen die immer und immer wiederholt werden:
    1. schleife: finde das set von 2 Variablen, das das beste Update verspricht,
    2. schleife: update vom gradienten

    der Rest - die Lösung des 2D-subproblems - ist vernachlässigbar. Dadurch ist der Algorithmus zwar schnell, hat aber ein ziemliches Skalierungsproblem. Momentan rechnen bei uns einzeln Instanzen dieses Problems bis zu einem Monat - und die Datensätze sind im Vergleich was da noch so kommt recht winzig. Wenn die Datensätze groß werden kriegen wir zum einen Cache Probleme (d.h. die Ausführungsgeschwindigkeit der beiden Schleifen wird durch die Geschwindigkeit des Speichers begrenzt), zum anderen ist nicht ganz klar, wie man das sinnvoll auf Großrechner verteilen kann, dafür sind die einzelnen Iterationen einfach zu winzig.



  • Quadratische Programme habe ich nur im Zusammenhang mit Support Vector Machines kennen gelernt. Die benutzten 'interior point' Methoden, was natuerlich sehr iterative ist. Vielleicht kann der jeweilige Iterationsschritt gut parallelisiert werden. Bibliotheken wie svmlight sollten als Quelltext zu finden sein.



  • Niemand verwendet IPMs mehr für SVM*. Svmlight hat das mal gemacht, jetzt machen die auch decomposition.
    LibSVM macht auch SMO
    Wir(Shark) machen SMO/S2DO

    *Ausser im ganz großn large scale berich, wo sie die Lösung des Gleichungssystems von einem Cluster erledigen ließen...



  • Niemand verwendet IPMs mehr für SVM*. Svmlight hat das mal gemacht, jetzt machen die auch decomposition.

    Echt? Ich werde alt. 🙂



  • knivil schrieb:

    Du willst wirklich L maximieren?

    Vor dem quadratischen Term steht ein Minus. Also vereinfacht f(x) = -x^2.

    Ah ok. Ja dann wäre der SPG (spectral projected gradient method) auch anwendbar. Ich verwende das Teil für Systeme mit Milliarden Unbekannten, genauer: Nicht-lineare Kleinste-Quadrate-Probleme mit dem Constraint dass die Koeffizienten der Lösung nicht negativ sein dürfen.


Log in to reply