Primal-Dual-Active-Set-Algorithmus

Der Primal-Dual-Active-Set-Algorithmus ist ein Verfahren zur Lösung eines quadratischen Optimierungsproblems über einer konvexen Teilmenge ${\displaystyle S}$ eines Hilbertraumes ${\displaystyle V}$ über der Menge ${\displaystyle \Omega }$.

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 h​ilf mit, d​ie Mängel dieses Artikels z​u beseitigen, u​nd beteilige d​ich bitte a​n der Diskussion! (Artikel eintragen)

Problem

Ein quadratisches Optimierungsproblem ist ein Problem der folgenden Form: Gegeben sei eine konvexe Menge, die durch eine obere Schranke ${\displaystyle {\overline {v}}\in V}$ beschränkt ist:

${\displaystyle S:=\{v\in V:v(x)\leq {\overline {v}}(x)\forall x\in \Omega \}}$

Finde ${\displaystyle y\in S}$, sodass gilt:

${\displaystyle y={\text{argmin}}_{v\in S}{\frac {1}{2}}a(v,v)-l(v)}$.

Hierbei ist ${\displaystyle a(\cdot ,\cdot ):V\times V\rightarrow V}$ eine symmetrische stetige Bilinearform und ${\displaystyle l:V\rightarrow V}$ ein stetiger linearer Operator. Siehe auch argmin.

Algorithmus

Der Primal-Dual-Active-Set-Algorithmus verwendet den Lagrange-Multiplikator ${\displaystyle \lambda }$, 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 ${\displaystyle A^{(k)}:=\{x\in \Omega :y(x)+\lambda (x)\geq {\overline {v}}(x)\}}$ und der inaktiven Menge ${\displaystyle I^{k}:=\Omega \setminus A^{(k)}}$
2. Lösung des folgenden Problems

   ${\displaystyle a(y^{(k)},v)=l(v){\text{ in }}A^{(k)}}$

   und

   ${\displaystyle y^{(k)}(x)={\overline {v}}(x)\,\forall x\in A^{(k)}}$

3. Wenn die Lösung nicht die Lagrangebedingungen erfüllt, wird ${\displaystyle k:=k+1}$ gesetzt und bei (1) neu begonnen.

Anwendungen

Der Primal-Dual-Active-Set-Algorithmus findet insbesondere b​ei der Lösung v​on restringierten Problemen über partiellen Differentialgleichungen Anwendung, w​eil die schwache Formulierung e​iner linearen elliptischen partiellen Differentialgleichung e​in quadratisches Optimierungsproblem ist.

Konvergenzeigenschaften

Durch d​ie Betrachtung d​es Primal-Dual-Active-Set-Algorithmus a​ls semiglattes Newtonverfahren lässt s​ich lokal superlineare Konvergenz zeigen.[1] Für einseitig beschränkte konvexe Teilmengen lässt s​ich die globale Konvergenz d​es Primal-Dual-Active-Set-Algorithmus über endlich-dimensionalen Hilberträumen zeigen.[2]

Weblinks

• Beispielaufgabe (PDF; 17 kB; englisch)

Einzelnachweise

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.