| |
- Mit dem Verfahren von Goldfarb und Idnani werden hier quadratische
Optimierungsaufgaben
f(x) = 1/2 xTGx -g0Tx = min,
HTx+h0 = 0,
CTx + c0 >= 0
gelöst.
- Hierbei muß die Matrix G der Dimension n
symmetrisch und positiv definit sein,
die Matrix H (Spaltenzahl p) muß vollen Spaltenrang
haben. Die Spaltenzahl der Matrix C und damit die Anzahl der
Ungleichungsrestriktionen ist m.
- Um diese Aufgabe zu lösen, wird bei diesem Verfahren das
äquivalente Maximierungsproblem gelöst, indem ausgehend vom
unrestringierten Minimum von f(x) der Wert von f(x)
laufend vergrößert wird ,
bis x zulässig geworden ist.
- Das duale Verfahren von Goldfarb und Idnani löst nacheinander QP-Probleme
mit nur einem Teil der Ungleichungsrestriktionen J als
Teilmenge von {1,...,m},
ausgehend von einem Problem ohne Ungleichungsrestriktionen,also J0=leer,
das direkt lösbar ist (lineares Gleichungssystem).
- Zu Anfang jedes Hauptschrittes hat man die Loesung eines solchen Problems,
beschrieben durch die Indexmenge J0.
Es ist auch der zugehörige Vektor der Lagrangemultiplikatoren
bekannt.
Nun wird die Indexmenge der zu berücksichtigenden Ungleichungen zunächst
vergrößert : J01 = J0+{p},
wobei die Restriktion Nr. p verletzt ist. Die Korrektur
zur Lösung dieses Problems beschreibt einen linearen Pfad im
n+p+m dimensionalen Raum. Diesen verfolgt man solange, bis
man diese Lösung erreicht hat oder bis einer der
Multiplikatoren für eine Ungleichung in J0 null
geworden ist. Dann wird die entsrechende Restriktion aus J0
entfernt. Dies wird fortgesetzt, bis man bei
vergrößertem Wert für f wieder die Lösung
eines solchen Problems, jetzt mit der Indexmenge J1,
erhält.
- Die Anzahl der notwendigen Indexaustauschschritte heißt
die Anzahl der Partialschritte dieses Hauptschrittes.
- Die Partialschritte sorgen dafür, daß die
Multilikatorschätzungen immer das richtige Vorzeichen haben.
Das Verfahren ist beendet, wenn
x auf diese Art zulässig geworden ist.
|