Primal-Dual-Active-Set-Algorithmus

Verfahren zur Lösung quadratischer Optimierungsprobleme

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

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.

Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

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. Siehe auch argmin.

Algorithmus

Bearbeiten

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

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

Konvergenzeigenschaften

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]

Bearbeiten

Einzelnachweise

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.