Saya mencoba memahami bagaimana metode pengoptimalan berbasis adjoint bekerja untuk optimisasi terbatas PDE. Khususnya, saya mencoba memahami mengapa metode adjoint lebih efisien untuk masalah di mana jumlah variabel desain besar, tetapi "jumlah persamaan kecil".
Apa yang saya mengerti:
Pertimbangkan masalah pengoptimalan terbatas PDE berikut:
di mana adalah fungsi objektif (cukup kontinu) dari variabel desain vektor dan vektor variabel lapangan tidak diketahui yang bergantung pada variabel desain, dan adalah bentuk residu dari PDE.
Jelas, kita dapat variasi pertama dari I dan R sebagai
Memperkenalkan vektor pengganda lagrange , variasi dalam fungsi tujuan dapat ditulis sebagai
Menyusun ulang istilah, kita dapat menulis:
Dengan demikian, jika kita dapat menyelesaikan untuk sehingga
Kemudian gradien dievaluasi hanya dalam hal variabel desain .
Dengan demikian, algoritma optimisasi berbasis adjoint akan mengulangi langkah-langkah berikut:
- Diberikan variabel desain saat ini
- Memecahkan variabel bidang (dari PDE)
- Memecahkan untuk pengganda lagrange (dari persamaan adjoint)
- Hitung gradien
- Perbarui variabel desain
Pertanyaan saya
Bagaimana 'trik' adjoin ini meningkatkan biaya optimasi per iterasi dalam kasus di mana jumlah variabel desain besar? Saya pernah mendengar bahwa biaya evaluasi gradien untuk metode adjoint adalah 'independen' dari jumlah variabel desain. Tetapi bagaimana tepatnya ini benar?
Saya yakin ada sesuatu yang sangat jelas bahwa saya entah bagaimana menghadap.
sumber
Jawaban:
Saya berpikir tentang biaya dari perspektif aljabar linier. (Lihat catatan ini oleh Stephen G. Johnson , yang saya temukan lebih intuitif daripada pendekatan pengali Lagrange). Pendekatan ke depan berarti penyelesaian untuk sensitivitas secara langsung:
yang melibatkan penyelesaian sistem linier untuk setiap parameter dalam vektor , lalu evaluasiβ
di mana menunjukkan turunan total, dan menunjukkan turunan parsial.d ∂
Pendekatan adjoint mencatat itu
sehingga variabel adjoint (pengali Lagrange) dapat didefinisikan olehλ
yang sesuai dengan persamaan adjoint
Pengelompokan ulang persyaratan ini hanya membutuhkan satu penyelesaian linier, alih-alih penyelesaian linier untuk setiap parameter, yang membuat evaluasi adjoin menjadi murah untuk banyak kasus parameter.
Itu tidak sepenuhnya independen; mungkin biaya evaluasi dan akan meningkat dengan jumlah parameter. Namun, penyelesaian linier masih akan memiliki ukuran yang sama, asalkan ukuran tidak berubah. Asumsinya adalah bahwa solves jauh lebih mahal daripada evaluasi fungsi.(∂I/∂β) (∂R/∂β) u
sumber
Singkatnya, keuntungan berasal dari fakta bahwa untuk menghitung turunan dari tujuan dikurangi , Anda tidak benar-benar perlu mengetahui turunan dari sehubungan dengan sebagai objek terpisah, tetapi hanya bagian itu yang mengarah ke variasi dalam .I(β,u(β)) u(β) β I(β,u(β))
Biarkan saya beralih ke notasi. Saya sedikit lebih nyaman dengan: ( menjadi variabel desain, menjadi variabel keadaan, dan menjadi objektif). Katakanlah cukup baik untuk menerapkan teorema fungsi implisit, sehingga persamaan memiliki solusi unik yang secara terus menerus dapat dibedakan sehubungan dengan , dan turunannya diberikan oleh solusi dari ( dan menjadi turunan parsial) .
Ini berarti Anda dapat mendefinisikan tujuan yang dikurangi , yang dapat dibedakan juga (jika adalah). Salah satu cara untuk mengkarakterisasi gradien adalah melalui turunan terarah (misalnya, hitung semua turunan parsial sehubungan dengan dasar ruang desain). Di sini, turunan terarah dalam arah diberikan oleh aturan rantai sebagai Jika baik, satu-satunya hal yang sulit untuk dihitung adalah untuk diberikan . Ini dapat dilakukan dengan mengalikan denganj(u):=J(y(u),u) J(y,u) ∇j(u) h
Namun, jika kita menemukan operator sehingga maka ini harus gradien yang diinginkan. Melihat , kita dapat menulis (dengan menjadi operator adjoint), jadi yang perlu kita hitung adalah . Dengan menggunakan , ini dapat dilakukan dengan menggunakan , yaitu, menghitung dan pengaturan Dalam optimasi terbatas-PDE,∇j
sumber