Primal-Dual-Active-Set-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Primal-Dual-Active-Set-Algorithmus ist ein Verfahren zur Lösung eines quadratischen Optimierungsproblems über einer konvexen Teilmenge eines Hilbertraumes über der Menge .

Das Problem[Bearbeiten | Quelltext bearbeiten]

Ein quadratisches Optimierungsproblem ist ein Problem der folgenden Form: Gegeben sei eine konvexe Menge, die durch eine obere Schranke beschränkt ist:

Finde , sodass gilt:

.

Hierbei ist eine symmetrische stetige Bilinearform und ein stetiger linearer Operator.

Der Algorithmus[Bearbeiten | Quelltext bearbeiten]

Dieser Artikel oder Abschnitt ist nicht allgemeinverständlich formuliert. Die Mängel sind unter Diskussion:Primal-Dual-Active-Set-Algorithmus beschrieben. Wenn du diesen Baustein entfernst, begründe dies bitte auf der Artikeldiskussionsseite und ergänze den automatisch erstellten Projektseitenabschnitt Wikipedia:Unverständliche Artikel#Primal-Dual-Active-Set-Algorithmus um {{Erledigt|1=~~~~}}.

Folgendes sollte noch verbessert werden: Verschiedenes ist unklar. Zum Beispiel: Ist ein Vektor (wie in der Formulierung der KKT-Bedingungen) oder eine Zahl? Wie wird initialisiert? Was ist eine Lösung von „in “? Bezieht sich das auf die s? Oder die s? Oder beide? Hinzu kommt, dass die Formulierung in ihrer abstrakten Form über einem Hilbertraum der Allgemeinverständlichkeit nicht gerade zuträglich ist.

Der Primal-Dual-Active-Set-Algorithmus verwendet den Lagrange-Multiplikator , um zu einer Lösung zu gelangen, die sowohl erlaubt als auch optimal ist. Der Algorithmus läuft wie folgt ab:

  1. Berechnung der aktiven Menge und der inaktiven Menge
  2. Lösung des folgenden Problems
    und
  3. Wenn die Lösung nicht die Lagrangebedingungen erfüllt, wird gesetzt und bei (1) neu begonnen

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Der Primal-Dual-Active-Set-Algorithmus findet insbesondere bei der Lösung von restringierten Problemen über partiellen Differentialgleichungen Anwendung, da die schwache Formulierung einer linearen elliptischen partiellen Differentialgleichung gerade ein quadratisches Optimierungsproblem ist.

Konvergenzeigenschaften[Bearbeiten | Quelltext bearbeiten]

Durch die Betrachtung des Primal-Dual-Active-Set-Algorithmus als semiglattes Newtonverfahren lässt sich lokal superlineare Konvergenz zeigen.[1] Für einseitig beschränkte konvexe Teilmengen lässt sich die globale Konvergenz des Primal-Dual-Active-Set-Algorithmus über endlich-dimensionalen Hilberträumen zeigen.[2]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. M. Hintermuller, K. Ito, K. Kunisch: The primal-dual active set strategy as a semismooth Newton method. In: SIAM J. Optim, 2003.
  2. A dual-active-set algorithm for positive semi-definite quadratic programming. NL Boland - Mathematical Programming. Springer, 1996.