Prekondisi yang efisien untuk Augmented Lagrangian

12

Saya ingin menyelesaikan masalah non-linear dengan kendala kesetaraan non-linear dan saya menggunakan Lagrangian yang diperbesar dengan istilah regularisasi penalti yang, sebagaimana diketahui, merusak jumlah kondisi sistem linierisasi saya (pada setiap iterasi Newton yang saya maksud) . Semakin besar jangka waktu hukuman, semakin buruk jumlah kondisinya. Adakah yang tahu cara yang efisien untuk menyingkirkan kondisi buruk ini dalam kasus khusus itu?

Untuk lebih spesifik, saya menggunakan lagrangian augmented klasik karena saya punya banyak kendala yang umumnya dapat berlebihan. Jadi secara buta memasukkan directy kendala ke dalam variabel primal sangat nyaman. Saya mencoba pendekatan lain yang lebih canggih berdasarkan eliminasi variabel atau prekondisi efisien secara langsung pada sistem KKT tetapi, karena kendala redundansi, saya memiliki beberapa masalah.

Masalah yang berkaitan dengan variabel dirumuskan sebagai mengikuti Lagrangian saya sebagai bentuk L ( u , λ ) : = W ( u ) + ρ λ Tu=[u1,,un]

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

Jadi secara umum Tujuan pada setiap iterasi Newton adalah untuk menyelesaikan masalah bentuk Dengan (kita hessian batasan) A ( u , ρ ) : = 2 u W ( u ) + ρ C T ( u ) C ( u ) dan b ( u , ρ ) : = - (u W ( u ) + (

AΔu=b
A(u,ρ):=u2W(u)+ρCT(u)C(u)
dan modal C dimaksudkan untuk C ( u ) : = u c ( u ) .
b(u,ρ):=(uW(u)+(ρ+λTc(u))u(u))
CC(u):=uc(u)

Terima kasih.

Tom
sumber
Hai Tom. Selamat datang di Scicomp. Untuk membantu kami menjawab pertanyaan Anda, dapatkah Anda menulis persamaan yang Anda coba selesaikan?
Paul
AΔu=b
oops maaf. Ya tentu.
Tom

Jawaban:

6

Bergantung pada struktur masalahnya, Anda dapat memecahkan sistem Lagrangian Augmented yang dikondisikan secara langsung. Sebagai contoh, BDDC / FETI-DP dapat menyelesaikan elastisitas yang hampir tidak dapat dikompresikan dalam bentuk primal dengan tingkat konvergensi yang tidak tergantung pada rasio Poisson (konstan pada subdomain, tetapi dengan lompatan sewenang-wenang). Demikian pula, metode multigrid yang secara tepat mereproduksi mode volumetrik dapat memiliki properti ini. Metode seperti itu adalah masalah khusus dan secara umum, hukuman besar menghasilkan sistem yang sulit untuk dikondisikan.

Untuk memungkinkan lebih banyak fleksibilitas dalam pilihan prekondisi, saya sarankan memperkenalkan variabel ganda eksplisit dan menulis sistem sadel poin yang lebih besar

(ACTCρ1)(xy)=(b0)

Aρ~CTCρ~ρρ1CA1CTPCFIELDSPLIT

Jika Anda dapat lebih spesifik tentang sumber masalah Anda (apa yang Anda meminimalkan dan apa kendala), saya mungkin dapat menyarankan referensi yang lebih spesifik.

Jed Brown
sumber
preconditioners untuk sistem yang teregulasi membuka beberapa cara baru bagi saya! Namun saya perlu waktu untuk mencerna semua itu, saya mungkin akan kembali kepada Anda setelah beberapa saat jika Anda tidak keberatan. Terima kasih banyak atas jawaban Anda berdua.
Tom
4

Memperkenalkan variabel tambahan untuk spoiling terms dalam kondisi KT, dan Anda dapat menemukan sistem simetris yang lebih besar yang berperilaku baik secara numerik, dengan hanya kebalikan dari faktor penalti yang memasuki matriks.

(A+ρCTC)x=b ρy=ρCxAx+CTy=bCxρ1y=0

Arnold Neumaier
sumber
c(u)=0uc(xs,x1,x2)=(x2x1)nxs\[x1,x2\]
Tom
@ Tom: Saya tidak bermaksud masalah nonlinear tetapi persamaan yang dikondisikan buruk Anda akhirnya. Harap tulis (dengan mengedit pertanyaan Anda) bentuk sistem linier yang ingin Anda selesaikan, dan bagaimana parameter penalti masuk.
Arnold Neumaier
Saya mencoba mencari tahu bagaimana memperkenalkan variabel ekstra akan melakukan trik ... Bisakah Anda mengirimkan saya referensi? Terima kasih banyak!
Tom
@ Tom: lihat jawaban yang diedit.
Arnold Neumaier
ρρ10