Primal-Dual-Active-Set-Algorithmus
# Primal-Dual-Active-Set-Algorithmus

* 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)

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

## Problem

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

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

Finde $y\in S$, sodass gilt:

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

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

## Algorithmus

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

* Berechnung der aktiven Menge $A^{(k)}:=\{x\in \Omega :y(x)+\lambda (x)\geq {\overline {v}}(x)\}$ und der inaktiven Menge $I^{k}:=\Omega \setminus A^{(k)}$
* Lösung des folgenden Problems

    $a(y^{(k)},v)=l(v){\text{ in }}A^{(k)}$
    und
    $y^{(k)}(x)={\overline {v}}(x)\,\forall x\in A^{(k)}$
* Wenn die Lösung nicht die Lagrangebedingungen erfüllt, wird $k:=k+1$ gesetzt und bei (1) neu begonnen.

## Anwendungen

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

Durch die Betrachtung des Primal-Dual-Active-Set-Algorithmus als semiglattes Newtonverfahren lässt sich lokal superlineare Konvergenz zeigen. 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.

