|
Penalty- und Barriere-Methode |
| |
- Hier steht Ihnen ein Programm für die äussere Penalty-Methode
bzw. Barrieremethode mit
gemischten Restriktionen zur Verfügung.
- Es soll also ein Minimierungsproblem der Form
f(x) = min, h(x)=0, g(x)>=0
mit der Penalty-Methode bzw. der gemischten Penalty-Barriere-Methode
gelöst werden.
- Hierbei wird eine Funktion phi konstruiert,
deren lokale und globale Minima in einer Umgebung des
zulässigen Gebietes die lokalen und globalen
Lösungen des Problems approximieren.
Die Güte der Approximation ist bei einem streng regulären
Problem (mit der LICQ-Bedingung, strikter Komplementarität
und hinreichender Bedingung zweiter Ordnung) O(1/rho).
In anderen Fällen kann die Approximationsgüte wesentlich
schlechter sein.
- phi(x;rho) = f(x)+rho*(||h(x)||2+||g(x)-||2)
bzw.
phi(x;rho) = f(x)+rho*(||h(x)||2)-(1/rho)*sumi log(gi(x))
Man kann zwischen den beiden Varianten wählen.
- Hier geht rho gegen unendlich, wenn die Lösung des Ausgangsproblems
beliebig genau approximiert werden soll. Numerisch beschränken wir rho
auf einen Wert rhomax.
- phi wird mit dem BFGS-Verfahren minimiert.
- Der Penaltyparameter rho geht von rhomin bis rhomax.
- Sie können entweder festvorgegebene
Problembeispiele aus der
Hock&Schittkowski Sammlung berechnen
lassen, oder sie geben selbst ein Optimierungsproblem an.
|
| |
|
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.
- Penalty- oder gemischte Barrierefunktion ?
- Soll der Iterationsverlauf ausgegeben werden ?
- Es gibt eine Standardparametereinstellung,
( epsx=1.E-5, rhomin=100, rhomax=1.E6 und rhofac=1.5,)
aber Sie können diese natürlich auch selbst einstellen:
- epsx: Die innere Iteration endet, falls
||grad phi|| <= epsx*(1+epsx*|phi|)
oder
||x-xprevious|| <= epsx*(1+||x||).
Wichtig : epsx > 0 !
- rhomin, rhomax: Den minimalen und den maximalen Wert des
Penaltyparameters rho.
- rhofac: Faktor für die Erhöhung von rho.
Wichtig : rhofac > 1 !
- Standardstartwert oder eigene Wahl des Startwerts ?
Wichtig : die Dimension des Startvektors muß natürlich an
das Problem angepaßt sein.
Die Iteration bezüglich rho wird abgebrochen,
wenn die primale und die duale Unzulässigkeit <= epsx sind
und der Gradient der Lagrangefunktion in der Norm
<= max(epsx,epsmach*100*cond) ist, spätestens aber bei
Erreichen von rhomax, was dann als ''Versagen'' interpretiert wird.
cond ist dabei eine Schätzung der Konditionszahl der Hessematrix
der Penaltyfunktion, die aus der aufdatierten BFGS-Näherung gewonnen
wird. Diese Konditionszahl wächst mit rho gegen unendlich unbeschränkt.
Die Lagrangemultiplikatoren werden aus
den Restriktionswerten nach der Standardformel geschätzt.
Eine zweite Schätzung benutzt die Lagrangebedingung mit einem
Least Squares Minimierungsansatz für den Gradienten der
Lagrangefunktion.
||grad(f(x)) - N * lambda||_2 = minlambda
N = Matrix der Gradienten der bindenden Restriktionen in x.
Dabei werden alle Ungleichungsrestriktionen mit
Werten <= epsx als bindend betrachtet und natürlich die
Gleichungsrestriktionen.
- Falls Sie eine graphische Ausgabe der Höhenlinien
der Penaltyfunktion bzw. Barrierefunktion wünschen,
müssen Sie noch die Koordinaten und das Rechteck, bezüglich derer
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.
- Penalty- oder gemischte Barrierefunktion ?
- Startwert. Wichtig : die Dimension des Startvektors muß natürlich an
das Problem angepaßt sein.
- Soll der Iterationsverlauf ausgegeben werden ?
- Es gibt eine Standardparametereinstellung,
( epsx=1.E-5, rhomin=100, rhomax=1.E6 und rhofac=1.5,)
aber Sie können diese natürlich auch selbst einstellen:
- epsx: Die innere Iteration endet, falls
||grad phi|| <= epsx*(1+epsx*|phi|)
oder
||x-xprevious|| <= epsx*(1+||x||).
Wichtig : epsx > 0 !
- rhomin, rhomax: Den minimalen und den maximalen Wert des
Penaltyparameters rho.
- rhofac: Faktor für die Erhöhung von rho.
Wichtig : rhofac > 1 !
- Falls Sie eine graphische Ausgabe der Höhenlinien
der Penaltyfunktion bzw. Barrierefunktion 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.
Beim Höhenlinienbild der Barrierefunktion wird außerhalb des zulässigen
Bereiches ein sehr grosser Wert als Repräsentant von "unendlich" benutzt.
|
| |
|
Die Ausgaben |
| |
- Ausgegeben wird das Aufwandsprotokoll und die Lösung,
- Wird das ausführliche Protokoll erwünscht, dann wird
in der inneren Iteration, also bei festem rho, die
Penalty- bzw. Barrierefunktion, die Norm ihres Gradienten und
die Größe der Unzulässigkeit protokolliert.
Weil der Penaltyparameter anwächst, wird der Gradient nicht
wirklich "klein".
- eine graphische Darstellung des Iterationsverlaufes
- und einen Plot mit dem dekadischen Logarithmus der
Penalty- bzw. Barrierefunktion und des Penalty- bzw. Barriereterms (psi).
Die Sprünge in den Graphen treten an den Stellen auf, an denen rho
erhöht wird.
- Falls Sie dies wollen, wird noch ein Höhenlinienbild der
letzten benutzten Penalty- bzw Barrierefunktion erzeugt.
|
| |
|
|
| |
|
|
| |
|
|