www.wikidata.de-de.nina.az

Primal Dual Active Set Algorithmus Der ist ein Verfahren zur Lösung eines quadratischen Optimierungsproblems über einer

Primal-Dual-Active-Set-Algorithmus

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)

Problem 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. 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
  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. 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.

Weblinks 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Primal Dual Active Set Algorithmus ist ein Verfahren zur Losung eines quadratischen Optimierungsproblems uber einer konvexen Teilmenge S displaystyle S eines Hilbertraumes V displaystyle V uber der Menge W displaystyle Omega Dieser Artikel wurde auf der Qualitatssicherungsseite des Portals Mathematik eingetragen Dies geschieht um die Qualitat der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen Bitte hilf mit die Mangel dieses Artikels zu beseitigen und beteilige dich bitte an der Diskussion Artikel eintragen Inhaltsverzeichnis 1 Problem 2 Algorithmus 3 Anwendungen 4 Konvergenzeigenschaften 5 Weblinks 6 EinzelnachweiseProblem BearbeitenEin quadratisches Optimierungsproblem ist ein Problem der folgenden Form Gegeben sei eine konvexe Menge die durch eine obere Schranke v V displaystyle overline v in V nbsp beschrankt ist S v V v x v x x W displaystyle S v in V v x leq overline v x forall x in Omega nbsp Finde y S displaystyle y in S nbsp sodass gilt y argmin v S 1 2 a v v l v displaystyle y text argmin v in S frac 1 2 a v v l v nbsp Hierbei ist a V V V displaystyle a cdot cdot V times V rightarrow V nbsp eine symmetrische stetige Bilinearform und l V V displaystyle l V rightarrow V nbsp ein stetiger linearer Operator Siehe auch argmin Algorithmus BearbeitenDer Primal Dual Active Set Algorithmus verwendet den Lagrange Multiplikator l displaystyle lambda nbsp um zu einer Losung zu gelangen die sowohl erlaubt als auch optimal ist Der Algorithmus lauft wie folgt ab Berechnung der aktiven Menge A k x W y x l x v x displaystyle A k x in Omega y x lambda x geq overline v x nbsp und der inaktiven Menge I k W A k displaystyle I k Omega setminus A k nbsp Losung des folgenden Problems a y k v l v in A k displaystyle a y k v l v text in A k nbsp und y k x v x x A k displaystyle y k x overline v x forall x in A k nbsp Wenn die Losung nicht die Lagrangebedingungen erfullt wird k k 1 displaystyle k k 1 nbsp gesetzt und bei 1 neu begonnen Anwendungen BearbeitenDer Primal Dual Active Set Algorithmus findet insbesondere bei der Losung von restringierten Problemen uber partiellen Differentialgleichungen Anwendung weil die schwache Formulierung einer linearen elliptischen partiellen Differentialgleichung ein quadratisches Optimierungsproblem ist Konvergenzeigenschaften BearbeitenDurch die Betrachtung des Primal Dual Active Set Algorithmus als semiglattes Newtonverfahren lasst sich lokal superlineare Konvergenz zeigen 1 Fur einseitig beschrankte konvexe Teilmengen lasst sich die globale Konvergenz des Primal Dual Active Set Algorithmus uber endlich dimensionalen Hilbertraumen zeigen 2 Weblinks BearbeitenBeispielaufgabe PDF 17 kB englisch Einzelnachweise Bearbeiten M Hintermuller K Ito K Kunisch The primal dual active set strategy as a semismooth Newton method In SIAM J Optim 2003 A dual active set algorithm for positive semi definite quadratic programming NL Boland Mathematical Programming Springer 1996 Abgerufen von https de wikipedia org w index php title Primal Dual Active Set Algorithmus amp oldid 238581354