Quelltext der Seite Primal-Dual-Active-Set-Algorithmus

{{QS-Mathematik}}Der '''Primal-Dual-Active-Set-Algorithmus''' ist ein Verfahren zur Lösung eines [[Optimierung (Mathematik)|quadratischen Optimierungsproblems]] über einer [[Konvexe Menge|konvexen Teilmenge]] <math>S</math> eines [[Hilbertraum]]es <math>V</math> über der Menge <math>\Omega</math>.

== Problem ==
Ein [[Quadratische Optimierung|quadratisches Optimierungsproblem]] ist ein Problem der folgenden Form: Gegeben sei eine konvexe Menge, die durch eine obere Schranke <math>\overline{v} \in V</math> beschränkt ist:
:<math>S := \{ v \in V: v(x) \leq \overline{v}(x) \forall x \in \Omega \}</math>
Finde <math>y \in S</math>, sodass gilt:
:<math>y = \text{argmin}_{v \in S} \frac{1}{2}a(v,v) - l(v)</math>.
Hierbei ist <math>a(\cdot,\cdot):V \times V \rightarrow V</math> eine symmetrische stetige [[Bilinearform]] und <math>l:V \rightarrow V</math> ein stetiger [[linearer Operator]]. Siehe auch [[Arginin|argmin]].

== Algorithmus ==
Der Primal-Dual-Active-Set-Algorithmus verwendet den [[Lagrange-Multiplikator]] <math>\lambda</math>, 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 <math>A^{(k)} := \{x \in \Omega: y(x) + \lambda(x) \geq \overline{v}(x)\}</math> und der inaktiven Menge <math>I^{k} := \Omega \setminus A^{(k)}</math>
# Lösung des folgenden Problems
#:<math>a(y^{(k)},v) = l(v)  \text{ in }  A^{(k)}</math>
#: und
#:<math>y^{(k)}(x) = \overline{v}(x) \, \forall x \in A^{(k)}</math>
# Wenn die Lösung nicht die Lagrangebedingungen erfüllt, wird <math>k := k+1</math> gesetzt und bei (1) neu begonnen.

== Anwendungen ==
Der Primal-Dual-Active-Set-Algorithmus findet insbesondere bei der Lösung von restringierten Problemen über [[Partielle Differentialgleichung|partiellen Differentialgleichungen]] Anwendung, weil die schwache Formulierung einer linearen [[Elliptische partielle Differentialgleichung|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.<ref name="hintermuller-ito-kunisch-2003">M. Hintermuller, K. Ito, K. Kunisch: ''The primal-dual active set strategy as a semismooth Newton method''. In: ''SIAM J. Optim'', 2003.</ref> 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.<ref name="NL-Boland">''A dual-active-set algorithm for positive semi-definite quadratic programming''. NL Boland - Mathematical Programming. Springer, 1996.</ref>

== Einzelnachweise ==
<references />

[[Kategorie:Numerische Mathematik]]