Pustaka C ++ untuk minimisasi terbatas nonlinear

Saat ini saya mencoba untuk menyelesaikan masalah minimisasi terbatas nonlinear seperti yang diterapkan dalam fungsi "fmincon" matlab. Harapan saya adalah, meminimalkan (fun1, x0, uB, lB, fun2) di mana x0 adalah keadaan awal, fun1 adalah fungsi yang perlu diminimalkan, uB adalah batas atas, lB adalah batas bawah dan fungsi fun2 adalah yang menyediakan vektor persamaan nonlinear / Ketidaksetaraan seperti dijelaskan dalam http://www.mathworks.com/help/optim/ug/fmincon.htmlsebagai fungsi nonlcon. Vektor ini berubah melalui iterasi juga (mereka tidak linear tergantung pada x_n, iterasi vektor solusi ke-n). Dalam implementasi matlab mereka dalam bentuk c (x) <= 0. Ini adalah bagian terakhir dari kode yang perlu porting dari matlab ke c ++ dan saya telah banyak berjuang ketika mencoba menemukan pustaka c ++ yang sesuai yang berisi algoritma ini. Inilah mengapa saya mencari bantuan di sini dan saya akan sangat menghargai jika Anda dapat memberikan keahlian Anda.

Contoh yang baik dari apa yang ingin saya lakukan adalah yang pertama di halaman ini http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b Satu-satunya perbedaan adalah saya butuh batasan juga ...

Terima kasih sebelumnya.

Peter

c++ nonlinear-programming Peter Kottas
sumber

Ada kemungkinan menggunakan NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference tetapi saya perlu menghitung perbedaan hingga menggunakan beberapa panggilan ke evaluasi fungsi "diminimalkan" dari fungsi tujuan dan saya baik-baik saja. berharap bahwa itu akan diurus oleh algoritma itu sendiri untuk meningkatkan kinerja. Fungsi saya yang diperkecil sangat mahal untuk dihitung. Hanya untuk memperjelas, fungsi yang diminimalkan adalah log-kemungkinan model yang diperkirakan dengan data asli dalam estimasi model markov-switching model time-series.

Peter Kottas

Sudahkah Anda melihat jawaban untuk pertanyaan ini ? Jika persyaratan Anda tidak dipenuhi di sana, Anda harus mengedit pertanyaan Anda untuk menunjukkannya untuk mendapatkan rekomendasi yang bermanfaat.

Christian Clason

Terima kasih, ada beberapa informasi berguna di sana. Saat ini saya sampai ke siku saya di perpustakaan NLOPT karena saya menemukan bahwa itu mungkin cocok dengan masalah saya juga. Saya akan menyimpan topik ini diposting dan akan memberikan solusi ketika saya datang dengan satu. Setiap bantuan yang mungkin membuat proses lebih cepat masih dihargai. Implementasi aktual misalnya, dll.

Peter Kottas

Beberapa pertanyaan: 1. Apakah masalah Anda cembung? 2. Apakah tujuan dan kendala dapat dibedakan? Jika ya, berapa kali? Sekali? Dua kali? 3. Bisakah Anda menghitung turunannya dengan mudah, jika ada? Apakah perkiraan perbedaan hingga mudah untuk dihitung jika Anda tidak memiliki turunannya yang tersedia? 4. Berapa banyak variabel keputusan yang Anda miliki? (yaitu, berapa banyak variabel yang ingin Anda perkecil?) Perkiraan kasar sudah cukup. 5. Apakah evaluasi fungsi mahal? Akan sangat membantu jika Anda memiliki semua informasi ini untuk memberikan jawaban yang lebih baik.

Geoff Oxberry

Hai! Pertama-tama, terima kasih atas balasannya. 1. Sulit dikatakan tetapi kemungkinan besar tidak, karena fungsi yang diminimalkan adalah log-kemungkinan antara estimasi model switching markov dari deret waktu dalam aplikasi finansial dan dari sifatnya saya berasumsi semacam output berisik. 2.tidak 3. hanya menggunakan perbedaan hingga 4. vektor solusi terdiri dari n variabel di mana n tergantung pada parameter model yang diinginkan, secara umum dari 12 hingga katakanlah 30 5. kemungkinan log antara model dan data asli mahal, ketidaksetaraan nonlinier tambahan ciak menghitung

Peter Kottas

Jawaban:

Jika fungsi Anda tidak dapat dibedakan, Anda harus berhati-hati tentang bagaimana Anda menggunakan perbedaan hingga. Jika Anda ingin menggunakan informasi turunan, taruhan terbaik Anda mungkin adalah semacam metode tipe Newton semismooth. Seperangkat catatan yang menjelaskan metode semacam itu dapat ditemukan di sini .

Dua belas hingga tiga puluh variabel mungkin berada di ujung atas dari apa yang bisa dilakukan dengan metode pencarian pola (juga disebut pencarian langsung). Sebuah makalah ulasan baru-baru ini oleh Rios dan Sahinidis dalam Journal of Global Optimization mengenai metode optimisasi bebas turunan (seperti metode pencarian pola) dapat ditemukan di sini , bersama dengan halaman web pendamping . Makalah ulasan yang kurang baru tentang metode ini oleh Kolda, Lewis, dan Torczon di SIAM Review dapat ditemukan di sini . Metode-metode ini bekerja cukup baik dengan evaluasi fungsi yang mahal, dan tidak perlu memerlukan diferensiasi atau informasi turunan.

Banyak dari metode ini memerlukan semacam konveksitas untuk menjamin konvergensi ke optimal global, jadi jika Anda ingin menyelesaikan masalah Anda dengan ketat, Anda mungkin perlu memasangkan metode ini di atas dengan strategi cabang-dan-terikat. Namun, jika Anda tidak peduli dengan ketelitian, pendekatan seperti MATLAB fminconmungkin cukup berhasil (tidak ada jaminan lagi). Perbedaan yang terbatas kemungkinan besar akan memberi Anda anggota subdifferential dari fungsi Anda yang tidak dapat dibeda-bedakan, yang mungkin cukup untuk instance masalah Anda dan data input tertentu untuk mengembalikan hasil yang cukup akurat untuk tujuan Anda. Dalam hal ini, Anda mungkin harus melihat perpustakaan yang disebutkan dalam jawaban atas pertanyaan yang dikaitkan Christian dalam komentarnya.

Geoff Oxberry
sumber

Jika yang Anda butuhkan adalah pustaka C ++ untuk menyelesaikan masalah optimasi nonlinier, Anda bisa menggunakan RobOptim . Meskipun RobOptim awalnya dikembangkan dengan masalah optimasi robotika dalam pikiran, itu cocok untuk masalah optimasi nonlinier. Ini menyediakan antarmuka C ++ sederhana dengan plugin untuk beberapa pemecah nonlinier ( Ipopt , NAG , dll.). Menggunakan pembungkus semacam itu membuatnya mudah untuk menggunakan pemecah NLP lain. 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/

Analisis yang dilakukan oleh @Geoff Oxberry sangat penting untuk pemilihan pemecah nonlinier yang akan dipanggil oleh RobOptim. Perhatikan bahwa ketika berhadapan dengan jenis pemecah seperti itu, penyesuaian parameter dapat memiliki dampak besar pada kinerja, dan Anda mungkin masih terjebak dalam minimas lokal (itu benar-benar tergantung pada jenis masalah yang Anda hadapi).

Catatan: Saya salah satu pengembang proyek ini.

BenC
sumber