|
SQP-Methode |
| |
- Hier steht Ihnen ein Programm für die SQP-Methode mit
gemischten Restriktionen zur Verfügung.
- Es soll also ein Minimierungsproblem der Form
f(x) = min, h(x)=0, g(x)>=0
mit der Methode der sequentiellen quadratischen
Minimierung gelöst werden.
- Bei diesem Verfahren wird eine exakte Penaltyfunktion,
deren Auswertung nur die Berechnung der Funktionswerte
von f, g und h erfordert, benutzt,
und zwar
f(x)+sumi=1,..,nh { (|ui|+1)|hi(x)|}
+sumi=1,..,ng{ (u(i)+1) max{0,-gi(x)} }
- Funktionen diesen Typs sind stets nichtdifferenzierbar,
und daher braucht man spezielle Techniken, um diese zu
minimieren.
Die SQP-Methode basiert auf der Methode der lokalen
Approximation durch ein quadratisches Optimierungsproblem, dessen
Lösung eine Abstiegsrichtung für diese Funktion liefert.
Das hier benutzte Verfahren (donlp2) benutzt soweit möglich
gleichungsrestringierte Ersatzprobleme, wobei die Schätzung der
bindenden Restriktionen auf der lokalen Auswertung der Kuhn-Tucker-Bedingungen
beruht.
- Sie können entweder festvorgegebene
Problembeispiele aus der
Hock&Schittkowski Sammlung berechnen
lassen, oder sie geben selbst ein Optimierungsproblem an.
- Hier findet eine spezielle Variante Verwendung, die eine höhere
algebraische Effizienz hat. Sie wird gesteuert durch eine Reihe von
Parametern, von denen Sie entweder die Standardsetzung übernehmen
oder die Sie selbst setzen:
tau0 ist die maximal erlaubte Unzulässigkeit, d.h.
die 1-Norm von h und dem negativen Teil von g.
Wenn der Startwert diese
Bedingung verletzt, wird eine Vorphase eingeschaltet, um zunächst
einen besseren Startwert zu finden.
del0 . Eine Ungleichungsrestriktion wird auf jeden Fall als
nicht bindend angesehen, wenn
gi(x)>del0*max{1,||grad gi(x)||}.
delmin Eine Ungleichungsrestriktion wird auf jeden Fall
als bindend angesehen, wenn
gi(x) < delmin*max{1,||grad gi(x)||}
gilt.
rho Die Gradienten der bindenden Restriktionen werden als linear
abhängig betrachtet, wenn die Diagonale des R-Teils ihrer QR-Zerlegung
eine Konditionszahl > 1/rho besitzt.
rho1 Die Hessematrix der Lagrangefunktion wird durch eine
Quasi-Newtonnäherung ersetzt. Eine Neuinitialisierung wird durchgeführt,
wenn diese eine Konditionszahl 1/rho1 besitzt.
|
| |
|
Es gibt zwei unterschiedliche Eingabeseiten:
Predefined und
Userdefined |
|
Die Eingaben - Predefined Variante |
| |
- Als erstes sollten Sie sich aus der
Beispielsammlung
eine Problemnummer suchen. Die Problemnummer besteht immer aus der
Zeichenfolge: hs dann eine Zahl und bei manchen Problemen ein
scal (=skaliert). Diese Nummer tragen Sie dann bitte auf der
Eingabeseite in das entsprechende Feld ein.
- Soll nur das Endergebnis oder auch der Iterationsverlauf ausgegeben
werden ?
- Es gibt eine Standardparametereinstellung, aber Sie können diese
natürlich auch selbst einstellen:
- tau0: Schranke für
psi(x) = ||h(x)||1 + ||g-(x)||1.
Wichtig : tau0 > 0 !
Sinnvoll z.b. tau0 = 1 oder größer.
0 < tau0 < 1 ist möglich, verschlechtert
aber die Effizienz.
(Es wird angenommen, daß das Problem in {x: psi(x)<=tau0}
wohldefiniert ist.)
- del0: Schranke für die bindenden Ungleichungen.
Wichtig: del0 > 0!
(gi mit
gi(x) > del*max{1,||grad gi(x)||}
werden (lokal) nicht berücksichtigt.)
del wird dabei zwischen del0 und delmin
gesteuert in Abhängigkeit von den lokal ausgewerteten
Kuhn-Tucker-Bedingungen.
- delmin:
Schranke für die zulässige Verletzung von Restriktionen
(notwendig, da nichtlineare Restriktionen wegen
Rundungsfehlereinfluss nie exakt zu erfüllen sind)
Wichtig: delmin > 0!
Sinnvoll wäre 1.d-10 <= delmin <= min{epsx,1.d-5}.)
- epsx: Die Iteration endet, falls
||gradx L || <= epsx(1+||grad f(x)||),
(L = Lagrangefunktion).
psi(x) <= delmin ''primale Unzulässigkeit''
Multiplikatoren zu den Ungleichungen >= -smallw
Komplementarität <= delmin*smallw*(nh+ng)
Wichtig : epsx > 0 !
Es gibt noch eine Reihe weiterer Abbruchbedingungen wie
''kleine Richtungsableitung'', ''keine signifikante Änderung in
x'' etc.
- smallw -smallw ist untere Grenze für die Multiplikatoren
zu den Ungleichungen.
- rho, rho1:
1/rho ist die Schranke für die Konditionszahl
der Matrix der bindenden Gradienten.
1/rho1 ist die Schranke für die Konditionszahl
der projizierten Hessematrix bzw. ihrer quasi-Newton-Approxiamtion.
Wird diese überschritten, wird mit
einem Vielfachen der Einheitsmatrix als Ersatz für diese
Matrix im QP-Problem fortgefahren.
Wird 1/rho von der Konditionszahl der Matrix der
bindenden Gradienten überschritten, dann wird auf ein
regularisiertes erweitertes QP-Problem ausgewichen,
sonst wird nur ein gleichungsrestringiertes QP-Problem
zur Bestimmung der Abstiegsrichtung benutzt.
- Standardstartwert oder eigene Wahl des Startwerts ?
Wichtig : die Dimension des Startvektors muß natürlich an
das Problem angepaßt sein.
- Falls Sie eine graphische Ausgabe der Höhenlinien
der exakten skalierten L1-Penaltyfunktion wünschen,
müssen Sie noch die Koordinaten und das Rechteck, bezüglich denen der Plot
erstellt werden soll, angeben. Es gibt dann noch die Wahl, ob
diese künstliche Rechenbox an die eventuell im Problem enthaltenen
Schrankenrestriktionen angepaßt werden soll.
|
| |
|
Die Eingaben - Userdefinierte Variante |
| |
- Bei dieser Variante braucht das Verfahren die Anzahl n der Variablen der zu
minimierenden Funktion fx
- sowie die Anzahl nh der Gleichungs- und ng der
Ungleichungsrestriktionen.
- Des weiteren können Sie hier die Funktion fx sowie die
Gleichungs- hxi und Ungleichungsrestriktionen gxi
spezifizieren. Beachten Sie bitte dazu die
Anleitung
- Startwert. Wichtig : die Dimension des Startvektors muß natürlich an
das Problem angepaßt sein.
- Soll nur das Endergebnis oder auch der Iterationsverlauf ausgegeben
werden ?
- Es gibt eine Standardparametereinstellung, aber Sie können diese
natürlich auch selbst einstellen:
- tau0: Schranke für
psi(x) = ||h(x)||1 + ||g-(x)||1.
Wichtig : tau0 > 0 !
Sinnvoll z.b. tau0 = 1 oder größer.
0 < tau0 < 1 ist möglich, verschlechtert
aber die Effizienz.
(Es wird angenommen, daß das Problem in {x: psi(x)<=tau0}
wohldefiniert ist.)
- del0: Schranke für die bindenden Ungleichungen.
Wichtig: del0 > 0!
(gi mit
gi(x) > del0*max{1,||grad gi(x)||}
werden (lokal) nicht berücksichtigt.)
- delmin:
Schranke für die zulässige Verletzung von Restriktionen
(notwendig, da nichtlineare Restriktionen wegen
Rundungsfehlereinfluss nie exakt zu erfüllen sind)
Wichtig: delmin > 0!
Sinnvoll wäre 1.d-10 <= delmin <= min{epsx,1.d-5}.)
- epsx: Die Iteration endet, falls
||gradx L || <= epsx(1+||grad f(x)||),
(L = Lagrangefunktion).
psi(x) <= delmin ''primale Unzulässigkeit''
Multiplikatoren zu den Ungleichungen >= -smallw
Komplementarität <= delmin*smallw*(nh+ng)
Wichtig : epsx > 0 !
Es gibt noch eine Reihe weiterer Abbruchbedingungen wie
''kleine Richtungsableitung'', ''keine signifikante Änderung in
x'' etc.
- smallw -smallw ist untere Grenze für die Multiplikatoren
zu den Ungleichungen.
- rho, rho1:
1/rho ist die Schranke für eine Näherung der Konditionszahl
der Matrix der bindenden Gradienten.
1/rho1 ist die Schranke für die Konditionszahl
der projizierten Hessematrix bzw. ihrer quasi-Newton-Approximation.
Wird diese überschritten, wird mit
einem Vielfachen der Einheitsmatrix als Ersatz für diese
Matrix im QP-Problem fortgefahren.
Wird 1/rho von der Konditionszahl der Matrix der
bindenden Gradienten überschritten, dann wird auf ein
regularisiertes erweitertes QP-Problem ausgewichen,
sonst wird nur ein gleichungsrestringiertes QP-Problem
zur Bestimmung der Abstiegsrichtung benutzt.
- Standardstartwert oder eigene Wahl des Startwerts ?
Wichtig : die Dimension des Startvektors muß natürlich an
das Problem angepaßt sein.
- Falls Sie eine graphische Ausgabe der Höhenlinien
der exakten skalierten L1-Penaltyfunktion wünschen,
müssen Sie noch die Koordinaten und das Rechteck, bezüglich denen der Plot
erstellt werden soll, angeben. Es gibt dann noch die Wahl, ob
diese künstliche Rechenbox an die eventuell im Problem enthaltenen
Schrankenrestriktionen angepaßt werden soll.
|
| |
|
Die Ausgaben |
| |
- Ausgegeben wird das Aufwandsprotokoll und die Lösung,
- Wird eine detailliertere Ausgabe erwünscht, dann wird
pro Schritt protokolliert: FX=Zielfunktionswert, B2N=Norm des
projizierten Gradienten (bezogen auf die jeweils als bindend angesehenen
Restriktionen), UPSI=L1-Norm von (h,g-),
UMI=algebraisch kleinster negativer Multiplikator zu den Ungleichungen,
NR=Anzahl der bindenden Restriktionen, SI=1, wenn linear abhängige Gradienten
auftreten, sonst =-1.
- eine graphische Darstellung des Iterationsverlaufes
(B2N und UPSI , s.o.)
- und einen Plot der dualen Unzulässigkeit und Komplementarität.
- Falls Sie dies wollen, wird noch ein Höhenlinienbild der exakten
Penaltyfunktion erzeugt.
|
| |
|
|
| |
|
|
| |
|
|