Paket perangkat lunak untuk optimasi terbatas?

21

Saya mencari untuk memecahkan masalah optimasi terbatas di mana saya tahu batas-batas pada beberapa variabel (khususnya kendala kotak).

\arg min_{kamu} f (kamu, x)

$\arg \min_u f(u,x)$

tunduk pada

c (kamu, x) = 0

$c(u,x) = 0$

Sebuah \leq d (kamu, x) \leq b

$a \le d(u,x) \le b$

di mana adalah vektor variabel desain, adalah vektor variabel keadaan, dan adalah kendala kesetaraan (biasanya PDE). Batasan bawah dan atas dan dapat bervariasi secara spasial. $u$ $x$ $c(u,x)$ $a$ $b$

Paket mana yang dapat menangani sistem formulir ini?

pde optimization nonlinear-programming Sean Farley
sumber

1

Versi yang diedit tidak terlihat seperti masalah optimisasi kotak-dibatasi. Masalah optimasi kotak-dibatasi akan memiliki sebagai kendala. Apakah seharusnya merupakan fungsi dari ? Apakah linier di dalam ? Jika tidak, apakah bisa dibedakan dua kali? Apakah convex di dalam ? Apakah ini dua kali dapat dibedakan dalam diri ? Akhirnya, menunjukkan himpunan poin di di mana nilai minimum diperoleh. Apakah yang Anda maksudkan ?

a \leq u \leq b

$a \leq u \leq b$

u

$u$

x

$x$

c

$c$

u

$u$

f

$f$

u

$u$

u

$u$

\arg min_{u}

$\arg \min_{u}$

u

$u$

f

$f$

min_{u}

$\min_{u}$

Geoff Oxberry

d (u, x) = u

$d(u,x) = u$ adalah satu kasus khusus, tetapi bentuk yang lebih umum ini sebenarnya umum dalam praktik. Anda selalu dapat memperkenalkan variabel tambahan jika metode Anda hanya dapat menangani kendala langsung pada . Kami biasanya lebih tertarik pada nilai di mana minimum dicapai daripada dalam nilai minimum . Sean menambahkan tag [pde], jadi Anda mungkin mendapatkan keteraturan dari itu. Dia tidak menyatakan apakah sistem itu hiperbolik atau tidak, jadi jangan berasumsi. Jangan berasumsi bahwa adalah cembung, karena seringkali tidak.

u

$u$

u

$u$

f

$f$

f

$f$

Jed Brown

Sudah cukup umum untuk melibatkan regularisasi atau , jadi kita tidak boleh mengasumsikan dua turunan.

f

$f$

L^{1}

$L^1$

W^{1, 1}

$W^{1,1}$

Jed Brown

@JedBrown: Masuk akal; itu membingungkan untuk melihat "batasan kotak" yang disebutkan tanpa, well, batasan kotak eksplisit. Untuk jenis masalah yang Anda bicarakan (masalah desain, masalah kontrol), jelas lebih menarik, tetapi masalah pengoptimalan biasanya dinyatakan menggunakan notasi , dan set solusinya dijelaskan menggunakan notasi .

u

$u$

m i n

$min$

\arg min

$\arg \min$

Geoff Oxberry

Mungkin bermanfaat untuk menentukan dalam bahasa / lingkungan apa Anda memodelkan PDE. Ini dapat membatasi pilihan pengoptimal.

Dominique

18

Saya memutuskan untuk secara radikal mengedit jawaban saya berdasarkan beberapa komentar.

Saya belum pernah menggunakan TAO. Dari membaca dengan teliti dokumentasi, sepertinya satu-satunya cara TAO dapat menangani masalah optimisasi terbatas (tidak termasuk kasus khusus hanya kendala kotak) adalah untuk mengubah masalah menjadi ketidaksetaraan variasional menggunakan kondisi Karush-Kuhn-Tucker (KKT) , yang diperlukan di bawah kualifikasi kendala (tipe yang biasanya saya lihat adalah kondisi titik Slater ), dan cukup di bawah konveksitas tujuan dan kendala (lebih umum, tipe 1 inveksitas). Jika $f$ adalah nonconvex, formulasi ketidaksetaraan variasional menggunakan kondisi KKT TIDAK setara dengan masalah optimisasi asli, jadi, jika Anda menginginkan optimal global untuk masalah optimasi, Anda tidak boleh menyatakannya sebagai ketidaksetaraan variasional. Akan sulit untuk menemukan optimum global pula untuk optimasi yang dibatasi oleh PDE (lihat di bawah), jadi mungkin mengabaikan detail ini baik-baik saja. Mengingat apa yang dikatakan Wolfgang, saya akan skeptis menggunakan TAO; Saya sudah skeptis karena tidak menerapkan metode untuk menyelesaikan program nonlinier (NLP) sebagai NLP, daripada ketidaksetaraan variasi.

Saya bukan ahli tentang optimasi yang dibatasi oleh PDE; rekan kerja dan rekan kerja tambang mengerjakan masalah optimisasi yang dibatasi ODE. Saya tahu bahwa untuk formulasi yang mengganggu, Larry Biegler (dan lainnya) akan menggunakan metode kolokasi untuk mendiskritasikan PDE dan menjadikannya NLP yang sangat besar dan jarang, dan kemudian ia akan menyelesaikannya menggunakan metode titik interior. Untuk benar-benar menyelesaikan masalah ke optimalitas global, Anda juga perlu menghasilkan relaksasi cembung, tetapi sejauh yang saya tahu, pendekatan ini tidak diambil karena masalah optimisasi yang dibatasi oleh PDE menyebabkan NLP yang besar sehingga akan sulit untuk menyelesaikannya. optimalitas global. Saya menyebutkan rincian ini hanya karena perumusan masalah sangat mempengaruhi pilihan paket solver. Untuk formulasi yang tidak mengganggu, PDE berulang memecahkan informasi gradien hasil untuk algoritma optimasi.

Beberapa orang yang mempelajari masalah optimasi ODE-menggunakan pendekatan yang sama dari diskritisasi masalah menggunakan kolokasi dan metode numerik, dan kemudian mengendurkan NLP yang dihasilkan untuk menghasilkan formulasi cembung yang digunakan dalam algoritma optimasi global. Pendekatan alternatif untuk optimasi yang dibatasi oleh ODE adalah untuk mengendurkan masalah, dan kemudian mendiskritisasi ODE, yang merupakan pendekatan yang diambil di lab saya. Mungkin saja untuk mengendurkan kelas tertentu dari masalah optimisasi terbatas PDE, tapi saya tidak tahu ada pekerjaan yang masih dilakukan pada masalah itu. (Itu adalah proyek potensial di lab saya pada satu titik.)

Pada akhirnya, yang penting bukanlah diferensiabilitas PDE asli, tetapi diferensiabilitas diskritisasi sehubungan dengan variabel keputusan.

Jika masalah yang didiskritkan dua kali dapat dibedakan sehubungan dengan variabel keputusan, paket berikut ini akan menghitung solusi lokal:

IPOPT adalah pemecah titik interior open source yang dikembangkan oleh Andreas Wächter di IBM. Ini kode berkualitas sangat tinggi. Sebagai pemecah titik-interior, lebih baik untuk fungsi-fungsi objektif dengan matriks Jacobian yang besar dan jarang, dan akan berguna untuk optimasi yang dibatasi oleh PDE
SNOPT adalah pemecah pemrograman kuadratik sekuensial komersial yang merupakan kode berkualitas tinggi lainnya. Itu lebih baik untuk fungsi objektif dengan matriks Jacobian yang kecil dan padat, jadi saya tidak berharap itu berguna untuk optimasi yang dibatasi oleh PDE, tetapi Anda bisa mencobanya.
NLopt adalah kode sumber terbuka kecil yang ditulis oleh Steven Johnson di MIT yang berisi implementasi dasar dari sejumlah algoritma optimasi nonlinier. Semua algoritme harus memadai untuk menyelesaikan masalah yang terbatas.
fmincon di Matlab mengimplementasikan sejumlah algoritma (termasuk titik interior dan pemrograman kuadratik berurutan) untuk optimasi nonlinier
GAMS dan AMPL keduanya bahasa pemodelan komersial yang digunakan untuk merumuskan masalah optimasi, dan mengandung antarmuka untuk sejumlah besar pemecah pemrograman nonlinier. Saya tahu bahwa GAMS memiliki versi uji coba yang dapat digunakan untuk masalah yang lebih kecil, dan contoh masalah juga dapat dikirimkan ke server NEOS untuk mendapatkan solusi.

Namun, ada kemungkinan bahwa diskritisasi hanya sekali terdiferensiasi sehubungan dengan variabel keputusan, dalam hal ini, Anda harus menggunakan penurunan curam yang diproyeksikan atau metode optimasi tingkat pertama lainnya ketika menghitung solusi lokal. Karena banyak penelitian berfokus pada masalah di mana metode orde dua dapat digunakan (dan ketika Anda dapat menggunakannya, sifat konvergensi superiornya membuat mereka menjadi pilihan yang lebih baik), saya tidak dapat menemukan banyak implementasi penurunan paling curam yang bukan solusi untuk masalah pekerjaan rumah. The GNU Scientific Library memiliki implementasi, tapi itu hanya untuk tujuan demonstrasi. Anda mungkin perlu membuat kode implementasi Anda sendiri.

Jika masalahnya hanya terus menerus sehubungan dengan variabel keputusan, maka Anda dapat menggunakan metode langsung untuk menyelesaikannya secara lokal. Ada survei yang sangat baik tentang metode langsung oleh Kolda, Lewis, dan Torczon . Yang paling dikenal luas dari metode ini adalah algoritma simpleks Nelder-Mead . Ini tidak dijamin untuk menyatu dengan minimum lokal dalam berbagai dimensi, tetapi bagaimanapun juga telah menemukan penggunaan praktis yang cukup.

Pilihan paket benar-benar tergantung pada bahasa yang ingin Anda gunakan untuk menyelesaikan masalah, jika menyelesaikan masalah yang dibatasi hanya bagian dari algoritma yang ingin Anda implementasikan (atau jika itu satu-satunya langkah dalam algoritma Anda, dalam hal ini memodelkan bahasa menjadi lebih layak untuk kode produksi), jenis dan ukuran masalah, dan jika Anda memerlukan paralelisme.

Geoff Oxberry
sumber

4

Kami telah mencoba TAO tetapi ternyata tidak terlalu berguna untuk masalah-masalah yang membatasi ketimpangan. Ini juga pada dasarnya hanya dalam mode pemeliharaan setidaknya sejak tahun 2003, tanpa fitur baru yang nyata selain dari pembaruan untuk melacak perubahan dalam PETSc di mana ia dibangun.

Wolfgang Bangerth
sumber

3

Alternatif lain adalah OPT ++ . Ini mendukung kendala linier dan nonlinier dengan pemecah titik interior nonlinier yang efisien, memberikan kontrol untuk akurasi fungsi (jika diperlukan pembedaan numerik), kontrol untuk ukuran langkah, dll. Saya biasanya mengoptimalkan fungsi implisit besar (misalnya FEM) di mana jenis kontrol dapat bermanfaat.

Barron
sumber

Bisakah Anda menjelaskan mengapa OPT ++ adalah paket yang baik untuk digunakan? Apakah Anda (atau kolega Anda) memiliki pengalaman dengannya?

Geoff Oxberry

Untuk lebih jelasnya, saya tidak punya alasan untuk mengatakan bahwa OPT ++ lebih unggul daripada yang Anda sebutkan sebelumnya karena saya tidak punya pengalaman dengan itu (meskipun saya telah membookmark beberapa dari mereka untuk memeriksa). Tetapi saya memiliki pengalaman dengan OPT ++ dan telah menemukannya cocok untuk kebutuhan saya. Ini mendukung kendala linier dan nonlinier dengan pemecah titik interior nonlinier yang efisien, memberikan kontrol untuk akurasi fungsi (jika diperlukan pembedaan numerik), kontrol untuk ukuran langkah, dll. Saya biasanya mengoptimalkan fungsi implisit besar (misalnya FEM) di mana jenis kontrol dapat bermanfaat.

Barron

2

@ Barron: Anda harus meletakkan itu di jawaban Anda untuk memulai. :)

JM

2

Jika masalah dirumuskan sebagai masalah saling melengkapi, Anda dapat menggunakan TAO (Toolkit untuk Pengoptimalan Lanjutan). Beberapa metode dalam TAO, seperti metode ruang direduksi (varian dari metode set aktif), saat ini tersedia sebagai bagian dari SNES di PETSc ( SNESVI ).

Jungho Lee
sumber

1

$[-\infty,+\infty]$

Saya tidak berpikir MINUTE akan bekerja dengan baik untuk kebutuhan Anda, tetapi perubahannya mungkin jika Anda dipaksa untuk menulis sendiri beberapa atau semua kode.

dmckee
sumber

Transformasi itu terlihat buruk; tidak heran itu disertai dengan beberapa paragraf.

Geoff Oxberry

1

Seperti yang ditunjukkan @Geoff Oxberry, beberapa paket memungkinkan Anda menemukan solusi lokal. Jika Anda ingin dapat membandingkan pemecah NLP yang berbeda ini untuk masalah yang sama, Anda dapat menggunakan RobOptim .

Meskipun RobOptim awalnya dikembangkan dengan masalah optimasi robotika dalam pikiran, ini cocok untuk masalah optimasi nonlinier. Ini menyediakan antarmuka C ++ sederhana dengan plugin untuk beberapa pemecah NLP (mis. Ipopt, NAG). Jika Anda tidak dapat memberikan gradien, perhitungan beda hingga dapat dilakukan secara otomatis.

Ini open source sehingga Anda dapat memeriksa kode sumber di GitHub: https://github.com/roboptim/

Catatan: Saya salah satu pengembang proyek ini.

BenC
sumber

1

Harus menunjukkan bahwa jawaban lain menggambarkan solver , bukan kerangka kerja. Lebih mudah untuk menemukan kerangka kerja ( driver ) yang dapat diterima daripada pemecah yang baik,

Deer Hunter

@DeerHunter Ketika Anda mencari solver untuk memecahkan masalah yang diberikan, seringkali sulit untuk mengetahui apriori mana solver yang akan menghitung solusi terbaik dan / atau menjadi yang tercepat. Anda berbicara tentang "pemecah yang baik", tetapi ini benar-benar tergantung pada apa yang Anda pecahkan: tidak ada satu pemecah "terbaik secara keseluruhan". Selain itu, API solver biasanya sangat berbeda, sehingga menggunakan kerangka kerja yang baik yang memungkinkan Anda untuk dengan mudah beralih dari satu solver ke solver lainnya bisa sangat membantu. Pertanyaannya adalah tentang "paket perangkat lunak untuk optimasi terbatas", dan kerangka kerja juga termasuk dalam kategori ini.

BenC

1

Berikut adalah sebagian daftar paket optimasi yang dibatasi oleh PDE.

Dolfin Adjoint adalah bagian dari FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance adalah bagian dari Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Contoh PYOMO untuk optimasi terbatas-PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

Manual TAO memberikan contoh penyelesaian masalah optimasi yang dibatasi oleh PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
sumber

1

Selamat datang di SciComp.SE! Hanya dengan menyediakan tautan (mungkin bermanfaat) bukanlah jawaban yang benar-benar baik; lihat meta.stackexchange.com/questions/8231 . Bisakah Anda sedikit memperluas ini (bahasa komputasi, kendala apa yang bisa ditangani, metode mana yang diterapkan, dll.)?

Christian Clason

Saya setuju dengan @ChristianClason. Sudah ada pengembangan substansial dalam pemecah masalah untuk perangkat lunak pengoptimalan yang dibatasi oleh PDE; Namun, jawaban ini pada dasarnya tidak memberikan latar belakang tentang algoritma apa yang sebenarnya diimplementasikan oleh paket-paket tersebut.

Geoff Oxberry

0

Paket APM MATLAB dan APM Python dapat menyelesaikan skala besar (100.000+ variabel) dari sistem persamaan Aljabar Gabungan Diferensial Campuran-Integer. Perangkat lunak ini tersedia sebagai layanan web untuk penggunaan komersial atau akademik. Jika Anda memecahkan sistem PDE, Anda bisa diskresi sekali untuk memasukkannya ke dalam bentuk DAE atau ODE untuk memasukkannya ke dalam bahasa pemodelan APMonitor. Bahasa pemodelan menggunakan pemecah APOPT , BPOPT, IPOPT, SNOPT, dan MINOS.

John Hedengren
sumber

1

Harap ungkapkan afiliasi Anda sebagai pengembang APMonitor dalam jawaban ini dan mendatang yang menyebutkan perangkat lunak Anda. Lihat FAQ untuk detail tentang kebijakan pengungkapan kami.

Geoff Oxberry

Geoff, terima kasih atas tipnya. Saya mulai bekerja pada platform APMonitor pada tahun 2004 sebagai mahasiswa pascasarjana di University of Texas di Austin. Kami sekarang menggunakannya dalam kelompok penelitian kami di Universitas Brigham Young untuk kontrol proses dan optimalisasi ( apm.byu.edu/prism ) biologi, kimia, aerospace, dan aplikasi lainnya. Saya membuatnya tersedia secara bebas untuk pengguna komersial atau akademik.

John Hedengren

Paket perangkat lunak untuk optimasi terbatas?

Jawaban: