Duale QP-Methode von Goldfarb und Idnani

• Mit dem Verfahren von Goldfarb und Idnani werden hier quadratische Optimierungsaufgaben
  f(x) = 1/2 x^TGx -g₀^Tx = min,
  H^Tx+h₀ = 0,
  C^Tx + c₀ >= 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 duale Maximierungsproblem gelöst, indem ausgehend vom unrestringierten Minimum von f der Wert von f laufend vergrößert wird (unter Beibehaltung der dualen Zulässigkeit), bis x zulässig geworden ist.
• Es gibt zwei verschiedene Eingabemöglichkeiten.
• Zum einen können Sie das Programm ein Problem generieren lassen, wobei Sie nur ein paar Parameter festlegen müssen. Bei der generierten Problemstellung hat die Ungleichungsrestriktion die einfache Form x >= 0.
• Oder Sie geben die Problemstellung, das heißt die Matrizen G, H, C und die Vektoren g₀, h₀, c₀ explizit an.

Es gibt zwei unterschiedliche Eingabeseiten: Generiertes Problem und Userdefined

Die Eingaben - Problemgenerierung

• Sie können das Problem vom Programm generieren lassen, wobei Sie dann angeben müssen:
• Die primale Dimension n der Matrix G. Wichtig : 1 <= n <= 100 !
• Die Anzahl der Gleichungsrestriktionen p. Wichtig : 0 <= p <= n !
• Die Anzahl der aktiven Schrankenrestriktionen i₀. Wichtig : 0 <= i₀+p <= n !
• Die reziproke Konditionszahl lammin der reduzierten Hessematrix. Wichtig : 0 < lammin < 1 ! Sinnvoll wäre 1.E-8 < lammin. Der maximale Eigenwert der reduzierten Hessematrix wird zu 1 gesetzt.
• Die reziproke Konditionszahl sigmin der Matrix der Gleichungsgradienten. Wichtig : 0 < sigmin < 1 ! Sinnvoll wäre 1.E-8 < sigmin. Der maximale Singulärwert von H wird zu 1 gesetzt. H wird mit Hilfe seiner Singulärwerte sig* generiert.
• Die untere Schranke xlow für die Variablen x(i), die in der Lösung nicht auf ihrer Schranke 0 liegen sollen. Wichtig : 0 < xlow < 1 ! Sinnvoll wäre 1.E-8 < xlow. Jedes "freie" x(i) liegt im Bereich [xlow,1], die bindenden Variablen x(i) liegen auf 0.
• Aus Ihren Eingaben und den Werten lammax = sigmax = 1 werden die Matrizen mittels Spektral- bzw. Singulärwertzerlegung aus Zufallszahlen generiert.
• Ebenso wird die Lösung x* generiert und dann werden die Vektoren h₀ und g₀ so gewählt, daß x* optimal ist, d.h. die Kuhn-Tucker-Bedingungen erfüllt.

Die Eingaben - Eigene Problemstellung

• Hier geben Sie eine eigene Problemstellung an:
• Einen Identifizierungstext, der dann in der Ausgabe erscheint.
• Die Dimension n der zu optimierenden Funktion bzw. der Matrix G. Wichtig : 1 <= n <= 100 !
• Die Anzahl der Gleichungsrestriktionen p. Wichtig : 0 <= p <= n !
• Die Anzahl der Ungleichungsestriktionen m. Wichtig : 0 <= m <= 300 !
• Die Matrizen G, H und C sowie die Vektoren g₀, h₀ und c₀.
  Bitte beachten Sie dabei die jeweiligen Dimensionen:
  G: n x n, g₀: n
  H: n x p, h₀: p
  C: n x m, c₀: m
  Das Programm fordert nur die Angabe der "Nicht-Null"-Elemente, und diese in der Form index1, index2, wert bzw. index, wert. Daraufhin wird dann dem jeweiligen Feld für den Index der entsprechende Wert zugeordnet.
  Bsp: Falls G_3,2=7, dann sieht das als Eintrag in das Formular von G folgendermaßen aus:
  3,2,7,
  Wichtig: jeder Datensatz für eine Komponente muss in eine eigene Zeile (Dies wird wegen der internen Eingabesteuerung benötigt). Wichtig: Sie geben C ein, nicht die Transponierte, der erste Index bezieht sich also auf die Variable x_index1 und der zweite Index auf die Nummer der Ungleichung index2, 1<= index2 <=m. Analog für H.
• Sie können wählen, ob Sie nur die Endergebnisse oder auch eine genaue Ausgabe der Zwischenergebnisse möchten.

Die Ausgaben

• Entweder der Identifizierungstext oder die von Ihnen gewählten Parameter für die Generierung.
• Die benötigte CPU-Zeit (auf 1/100 sec genau, d.h. 0, wenn das Problem in weniger als 1/100 sec gelöst ist).
• Bei der Problemgenerierung ist die wahre Lösung bekannt, daher werden hier die Fehler ausgegeben, d.h. Sie können hier den Rundungsfehlereinfluss in Abhängigkeit von sigmin, lammin und xlow studieren.
• Bei der eigenen Problemstellung sehen Sie stattdessen die Endergebnisse und eventuell das gesamte Verlaufsprotokoll.
• Der Verlauf der Unzulässigkeit über der Schrittzahl.
• Die zweite Graphik zeigt den Verlauf der Partialschrittzahlen über der Schrittzahl. Diese Grafik erscheint nur, wenn genügend (mindestens 3) Schritte durchgeführt wurden.

Das Eingabeformular - Generierung

Das Eingabeformular - Usereingabe

Zurück: Restringierte Minimierung