Lösung für quadratisches Problem mit Box-Constraints? Algorithmus?
-
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 nwobei 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 gradientender 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.