Erweiterte Lagrangefunktion nach Rockafellar bzw. Kiwiel

• Hier steht Ihnen ein Programm für die Multiplikatormethode mit gemischten Restriktionen zur Verfügung.
• Es soll also ein Minimierungsproblem der Form
  f(x) = min, h(x)=0, g(x)>=0
  mit der erweiterten Lagrangefunktion nach Rockafellar bzw. Kiwiel gelöst werden. (Sind nur Gleichungen vorhanden, ist dies die Funktion von Hestenes und Powell)
• Hierbei wird zu festen Multiplikatoren lam und my durch Minimierung der erweiterten Lagrangefunktion phi die Lösung x bestimmt. Die erweiterte Lagrangefunkion phi nach Rockafellar bzw. Kiwiel lautet :
  phi(x,lam,my;rho) =
  f(x)-my^Th(x)-||lam||**2/(4*rho)+rho*(||h(x)||**2+||(g(x)-lam/(2*rho))^(-)||**2
  bzw.
  phi(x,lambda,my;rho) =
  f(x) - my^Th(x)+rho*||h(x)||**2 + 1/(3*rho) sum_i=1,...,ng t_i
  mit
  t_i=max(0,(sign(lam(i))sqrt(abs(lam(i))))**3-rho*g_i(x))-|lam(i)|**1.5)
  
• Der Penaltyparameter rho wird mit den Parametern tau0 und gamma in Verbindung mit der Unzulässigkeit gesteuert.
• Dann werden my und lambda durch einen Maximierungsschritt von phi bezüglich my und lambda mit dem Gradientenverfahren mit fester Schrittweite 2*rho aufdatiert, das für grosses rho auch als vereinfachtes Newtonverfahren interpretierbar ist. Dabei ergibt sich eine explizite Korrektur von
  my = my-2*rho*hx
  und
  lam = max(0,abs(lam)**(1/(beta-1))-rho*g_i(x))**(beta-1)
  mit beta = 2 im Fall Rockafellar und beta = 3 im Fall Kiwiel.
• Dieser Zyklus wird wiederholt, bis Konvergenz eintritt.
• Zur unrestringierten Minimierung bzgl. x wird das BFGS-Verfahren benutzt.
• Der Penaltyparameter rho geht von rhomin bis höchstens rhomax, bleibt aber in der Regel auf einem maßvoll großen Wert stehen. rho wird erhöht, wenn die Unzulässigkeit in einem äusseren Zyklus zunimmt oder in der inneren Minimierung Nichtkonvexität von phi bzgl. x festgestellt wird.
• Die Funktion von Rockafellar ist höchstens lokal C², sonst nur C¹, während die Kiwiel-Funktion global C² ist.
• 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 gefolgt von einer Zahl und bei manchen Problemen ein scal (=skaliert). Diese Nummer tragen Sie dann bitte auf der Eingabeseite in das entsprechende Feld ein.
• Desweiteren können Sie wählen, ob die Rockafellarfunktion oder die Kiwielfunktion verwendet werden soll.
• Soll die Ausgabe detailliert sein, das heißt, soll der Iterationsverlauf oder nur das Endergebnis ausgegeben werden ?
• Es gibt eine Standardparametereinstellung, aber Sie können diese natürlich auch selbst einstellen:
  1. epsx: Die innere Iteration endet, falls
     ||grad phi|| <= epsx*(1+epsx*|phi|)
     oder
     ||x-x_previous|| <= epsx*(1+||x||).
     Wichtig : epsx > 0 !
  2. rhomin, rhomax: Den minimalen und den maximalen Wert des Penaltyparameters rho.
  3. rhofac: Faktor für die Erhöhung von rho. Wichtig : rhofac > 1 !
  4. gamma: Es wird in der inneren Iteration eine Zunahme der Unzulässigkeit maximal um den Faktor gamma erlaubt. Wichtig : gamma > 1 !
  5. tau0: Maximal erlaubte Unzulässigkeit. Die Unzulässigkeit wird hier als psi = ||h(x)||²+||(g^-)(x)||² berechnet. Wird dies größer als tau0, erfolgt ein Rücksetzen von x und Erhöhung von rho.
  6. 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 erweiterten Lagrangefunktion in der Lösung 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 Zielfunktion fx sowie die Gleichungsretriktionen hxi und Ungleichungsrestriktionen gxi spezifizieren.
• Rockafellar- oder die Kiwielfunktion ?
• Startwert. Wichtig : die Dimension des Startvektors muß natürlich an das Problem angepaßt sein.
• tau0: Maximal erlaubte Unzulässigkeit. Die Unzulässigkeit wird hier als psi = ||h(x)||²+||(g^-)(x)||² berechnet. Wird dies größer als tau0, erfolgt ein Rücksetzen von x und Erhöhung von rho.
• Soll die Ausgabe detailliert sein, das heißt, soll der Iterationsverlauf oder nur das Endergebnis ausgegeben werden ?
• Es gibt eine Standardparametereinstellung, aber Sie können diese natürlich auch selbst einstellen:
  1. epsx: Die innere Iteration endet, falls
     ||grad phi|| <= epsx*(1+epsx*|phi|)
     oder
     ||x-x_previous|| <= epsx*(1+||x||).
     Wichtig : epsx > 0 !
  2. rhomin, rhomax: Den minimalen und den maximalen Wert des Penaltyparameters rho.
  3. rhofac: Faktor für die Erhöhung von rho. Wichtig : rhofac > 1 !
  4. gamma: Es wird in der inneren Iteration eine Zunahme der Unzulässigkeit maximal um den Faktor gamma erlaubt. Wichtig : gamma > 1 !
• Falls Sie eine graphische Ausgabe der Höhenlinien der erweiterten Lagrangefunktion in der Lösung 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 das ausführliche Protokoll erwünscht, dann wird in der inneren Iteration, also bei festem rho, die erweiterte Lagrangefunktion, die Norm ihres Gradienten und die primale Unzulässigkeit (Normquadrat) protokolliert.
• eine graphische Darstellung der Funktion phi-phimin
• und ein Plot mit lg(||grad phi||) und lg(psi).
• Sprungstellen in den Plots treten an Stellen auf, an denen rho geändert wird.
• Falls Sie dies wollen, wird noch ein Höhenlinienbild der letzten benutzten erweiterten Lagrangefunktion erzeugt.

Predefinierte Variante

Userdefinierte Variante

Zurück: Restringierte Minimierung