GRG-Methode
 
  • Hier steht Ihnen ein Programm für die Methode der generalisierten reduzierten Gradienten (GRG) mit gemischten Restriktionen zur Verfügung. D.h. das Problem wird auf unrestringierte Minimierung auf Stücken von Randmannigfaltigkeiten der zulässigen Menge zurückgeführt. Alle Näherungswerte sind also zulässig. Ein Wechsel der Randmannigfaltigkeit erfolgt auf der Basis der Optimalitätsbedingungen.
  • Es soll also ein Minimierungsproblem der Form
    f(x) = min, h(x)=0, g(x)>=0
    gelöst werden. Im allgemeinen Fall benutzen wir das BFGS-Verfahren als Minimierer. In Spezialfällen arbeiten wir mit der exakten Hessematrix.
  • Bei diesem Typ von Verfahren wird bei jedem Schritt eine Einteilung von x in "freie" und "gebundene" Variablen mit Hilfe der aktiven Restriktionen vorgenommen und anschließend f bezüglich der freien Variablen minimiert.
  • Das Programm unterscheidet vier verschiedene Problemfälle: Linear, konvex quadratisch, f allgemein mit linearen Restriktionen oder das allgemeine nichtlineare Problem und paßt das Verfahren entsprechend an.
    1. Sind f,g und h affin linear, dann benutzt das Verfahren ein Vielfaches der Einheitsmatrix als Ersatz für die Hessematrix der Lagrangefunktion und benutzt stets die maximal mögliche Schrittweite. Es entspricht dann einem Verfahren der projizierten Gradienten bzw. dem Simplexverfahren, letzteres, sobald die Menge der aktiven Restriktionen die Mächtigkeit n erreicht hat.
    2. Ist f quadratisch und sind h und g affin linear, das Problem also ein QP-Problem, so wird die Hessematrix von A exakt berechnet. Ist A positiv definit, ist das Verfahren ein primales QP-Verfahren. Es wird stets die optimale bzw. maximal mögliche Schrittweite benutzt, man hat dann ein finites Verfahren. Ist A singulär oder indefinit, wird A durch Addition eines Vielfachen der Einheitsmatrix regularisiert. Dann entspricht das Verfahren einem regularisierten Newton-grg-Verfahren.
    3. Wenn f nichtquadratisch ist oder g,h nichtlinear sind, wird das grg-BFGS-Verfahren mit Mehrfachinaktivierung benutzt. In diesem Fall wird die projizierte Hessematrix nach der BFGS-Formel aufdatiert.
    4. Zur Restoration der Unzulässigkeit im Falle nichtlinearer Restriktionen wird das vereinfachte Newtonverfahren benutzt. In allen Fällen kann der Startwert jedoch unzulässig sein. Dann wird zuerst die L1-Norm von (h,g-) mit einem modifizierten Newtonverfahren minimiert, bis ein zulässiger Punkt gefunden ist. Falls dies fehlschlägt, bricht die Rechnung mit einer entsprechenden Meldung ab.
  • 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.
  • Soll die Ausgabe sehr detailliert sein ?
  • Standardstartwert oder eigene Wahl des Startwerts ? Wichtig : die Dimension des Startvektors muß natürlich an das Problem angepaßt sein.
  • Es gibt eine Standardparametereinstellung, aber Sie können diese natürlich auch selbst einstellen:
    1. itermax: maximale Iterationsanzahl.Wichtig: itermax <= 1000
    2. epsx: Die Minimierung auf einem Randstück endet, falls ||grad(f_reduziert)|| <= epsx*(1+epsx*|f|) oder ||x-xprevious|| <= epsx*(1+||x||). Wichtig : epsx > 0 !
    3. delmin: Schranke für die zulässige Verletzung von Restriktionen (dies ist notwendig, da nichtlineare Restriktionen wegen des Rundungsfehlereinflusses nie exakt zu erfüllen sind)
    4. rho, rho1: 1/rho ist die Schranke für die Konditionszahl der Matrix der bindenden Gradienten. Wird die Konditionszahl 1/rho von der Matrix der aktiven Gradienten überschritten, bricht das Verfahren ab.
      1/rho1 entsprechend für die Konditionszahl der Hessematrix der Lagrangefunktion. Wird die Konditionszahl 1/rho1 von der projizierten Hessematrix bzw. ihrer BFGS-Näherung überschritten, so wird durch ein geeignetes Vielfaches der Einheitsmatrix regularisiert bzw ein Neustart ausgelöst.
    5. c2u: alle Ungleichungsrestriktionen, deren Multiplikatorschätzungen <= c2u* minimaler (negativer) Multiplikator sind, werden zur simultanen Inaktivierung vorgesehen.
  • Falls Sie eine graphische Ausgabe der Höhenlinien der zugeordneten exakten l1-Zielfunktion wünschen, hier
    f(x)+sumi=1,..,nh { (|ui|+1){hi(x)|} +sumi=1,..,ng{ (u(i)+1) max{0,-gi(x)} }
    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.
  • Ein Identifizierungstext.
  • Startwert. Wichtig : die Dimension des Startvektors muß natürlich an das Problem angepaßt sein.
  • Bitte spezifizieren Sie das Problem: linear, quadratisch oder allgemein ?
  • Des weiteren können Sie hier die Funktion fx sowie die Gleichungs- hxi und Ungleichungsrestriktionen gxi spezifizieren.
  • Soll ein Iterationsprotokoll ausgegeben werden ?
  • Es gibt eine Standardparametereinstellung, aber Sie können diese natürlich auch selbst einstellen:
    1. itermax: maximale Iterationsanzahl.Wichtig: itermax <= 1000
    2. epsx: Die innere Iteration endet, falls ||grad(f) || <= epsx*(1+epsx*|f|) oder ||x-xprevious|| <= epsx*(1+||x||). Wichtig : epsx > 0 !
    3. delmin: Schranke für die zulässige Verletzung von Restriktionen (notwendig, da nichtlineare Restriktionen wegen Rundungsfehlereinfluss nie exakt zu erfüllen)
    4. rho, rho1: 1/rho ist die Schranke für die Konditionszahl der Matrix der bindenden Gradienten. Wird die Konditionszahl 1/rho von der Matrix der aktiven Gradienten überschritten, bricht das Verfahren ab.
      1/rho1 entsprechend für die Konditionszahl der Hessematrix der Lagrangefunktion. Wird die Konditionszahl 1/rho1 von der projizierten Hessematrix bzw. ihrer BFGS-Näherung überschritten, so wird durch ein geeignetes Vielfaches der Einheitsmatrix regularisiert bzw ein Neustart ausgelöst.
    5. c2u: alle Ungleichungsrestriktionen, deren Multiplikatorschätzungen <= c2u* minimaler (negativer) Multiplikator sind, werden zur simultanen Inaktivierung vorgesehen.
  • Falls Sie eine graphische Ausgabe der Höhenlinien der zugeordneten exakten l1-Penaltyfunktion wünschen, also
    f(x)+sumi=1,..,nh { (|ui|+1){hi(x)|} +sumi=1,..,ng{ (u(i)+1) max{0,-gi(x)} }
    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,
  • Falls Sie ein ausführliches Protokoll gewünscht haben, werden pro Iterationsschritt angegeben: f(x)=Zielfunktionswert, projgrad=Norm des projizierten Gradienten, infeas=L1-Norm von (h,g-), uminsc=eine skalierte Version des kleinsten negativen Ungleichungsmultiplikators, dirder=die Richtungsableitung der Zielfunktion entlang der laufenden Abstiegsrichtung, sigma=Schrittweite, sigma*=T, wenn eine neue Restriktion in die bindende Menge aufgenommen wird, sonst=F, #restor = die in diesem Schritt erforderliche Gesamtzahl der Schritte des vereinfachten Newtonverfahrens zur Restoration, einschliesslich eventuell fehlgeschlagener (mit anschliessender sigma-Reduktion). Bei festem sigma werden maximal 10 Newtonschritte versucht. phase=1 normale Minimierung, phase=-1 : suche eines zulässigen Punktes.
  • eine graphische Darstellung des Iterationsverlaufes f - fmin
  • und einen logarithmischen Plot der Norm des reduzierten Gradienten und der Norm der dualen Unzulässigkeit.
  • Falls Sie dies wollen, wird noch ein Höhenlinienbild erzeugt.
 

Predefinierte Variante

 

Userdefinierte Variante

 
 

Zurück: Restringierte Minimierung
 Back to the top!

04.02.2009