Effizienter Vorkonditionierer für Augmented Lagrangian

12

Ich möchte ein nichtlineares Problem mit nichtlinearen Gleichheitsbeschränkungen lösen und verwende ein erweitertes Lagrange mit einem Term der Strafregulierung, der bekanntlich die Bedingungszahl meiner linearisierten Systeme verdirbt (bei jeder von mir genannten Newton-Iteration). . Je größer die Strafe ist, desto schlechter ist die Konditionszahl. Würde jemand einen effizienten Weg kennen, um diese schlechte Konditionierung in diesem speziellen Fall loszuwerden?

Genauer gesagt verwende ich den klassischen Augmented Lagrangian, weil ich viele Einschränkungen habe, die im Allgemeinen überflüssig sein können. Es ist daher sehr praktisch, die Bedingungen direkt in die ursprünglichen Variablen zu integrieren. Ich habe andere ausgefeiltere Ansätze ausprobiert, die auf variablen Eliminierungen oder effizienten Vorkonditionierern direkt auf dem KKT-System basieren, aber aufgrund von Redundanzbeschränkungen habe ich einige Probleme.

Das Problem bezüglich der Variablen wird wie folgt formuliert: my Lagrangian als die Form L ( u , λ ) : = W ( u ) + ρ λ Tu=[u1,,un]

L(u,λ): =W(u)+ρλTc(u)+ρ2c2(u)

So Im allgemeinen ist das Ziel bei jedem Newton - Iteration ein Problem von der Form zu lösen mit (wir Tropfen Hessian des constraint) A ( u , ρ ) : = 2 u W ( u ) + ρ C T ( u ) C ( u ) und b ( u , ρ ) : = - (u W ( u ) + (

EINΔu=b
EIN(u,ρ): =u2W(u)+ρCT(u)C(u)
und das Kapital C ist für C ( u ) bestimmt : = u c ( u ) .
b(u,ρ): =-(uW(u)+(ρ+λTc(u))u(u))
CC(u): =uc(u)

Vielen Dank.

Tom
quelle
Hallo Tom. Willkommen bei Scicomp. Können Sie die zu lösenden Gleichungen aufschreiben, um uns bei der Beantwortung Ihrer Frage zu helfen?
Paul
Meinen Sie ? EINΔu=b
Arnold Neumaier
Ups, Entschuldigung. Ja, sicher.
Tom

Antworten:

6

Abhängig von der Problemstruktur können Sie das schlecht konditionierte Augmented Lagrangian-System direkt lösen. Zum Beispiel kann BDDC / FETI-DP eine nahezu inkompressible Elastizität in ursprünglicher Form mit einer Konvergenzrate unabhängig vom Poisson-Verhältnis (stückweise konstant auf Subdomänen, aber mit willkürlichen Sprüngen) lösen. In ähnlicher Weise können Multigrid-Methoden, die den volumetrischen Modus exakt reproduzieren, diese Eigenschaft haben. Solche Methoden sind problemspezifisch und im Allgemeinen führen große Strafen zu Systemen, die nur schwer vorkonditioniert werden können.

Um mehr Flexibilität bei der Auswahl der Vorkonditionierer zu ermöglichen, empfehle ich, explizite duale Variablen einzuführen und das größere Sattelpunktsystem zu schreiben

(EINCTC-ρ-1)(xy)=(b0)

EIN-ρ~CTCρ~ρ-ρ-1-CEIN-1CTPCFIELDSPLIT

Wenn Sie die Ursache Ihres Problems genauer bestimmen können (was minimieren Sie und was ist die Einschränkung), kann ich möglicherweise spezifischere Referenzen vorschlagen.

Jed Brown
quelle
vorkonditionierer für regularisierte systeme eröffnen mir neue möglichkeiten! Wie auch immer, ich werde einige Zeit brauchen, um all das zu verdauen. Wenn es Ihnen nichts ausmacht, werde ich vielleicht nach einer Weile zu Ihnen zurückkehren. Vielen Dank an Sie beide für Ihre Antworten.
Tom
4

Wenn Sie zusätzliche Variablen für die verderblichen Terme in die KT-Bedingung einfügen, finden Sie ein größeres symmetrisches System, das sich numerisch gut verhält und bei dem nur die Umkehrung des Straffaktors in die Matrix eintritt.

(EIN+ρCTC)x=b ρy=ρCxEINx+CTy=bCx-ρ-1y=0 , was im Allgemeinen gut konditioniert ist.

Arnold Neumaier
quelle
Im Allgemeinen sind meine Einschränkungen von der Form c(u)=0 wo ubeinhaltet in der Regel nur sehr wenige Freiheitsgrade. Zum Beispiel können wir einige Projektionsbeschränkungen haben, wie zc(xs,x1,x2)=(x2-x1)n entsprechend der Projektion des 3D-Punktes xs auf dem Segment \ [x1,x2\].
Tom
@Tom: Ich meinte nicht das nichtlineare Problem, sondern die schlecht konditionierten Gleichungen, mit denen Sie enden. Bitte notieren Sie sich (durch Bearbeiten Ihrer Frage) die Form des zu lösenden linearen Systems und die Eingabe des Strafparameters.
Arnold Neumaier
Ich versuche herauszufinden, wie das Einführen von zusätzlichen Variablen den Trick machen würde ... Könnten Sie mir eine Referenz schicken? Vielen Dank!
Tom
@Tom: Siehe die bearbeitete Antwort.
Arnold Neumaier
Doch wenn ρ ist dann groß ρ-10und das System ist dem ursprünglichen KKT-System sehr ähnlich, das ist unbestimmt, nicht wahr?
Tom