Kuadrat terkecil nonlinear dengan batasan kotak

10

Apa cara yang disarankan untuk melakukan nonlinier kuadrat, min , dengan kotak kendala ? Menurut saya (orang-orang bodoh masuk) bahwa seseorang dapat membuat batasan kotak kuadratik, dan meminimalkan $\sum err_i(p)^2$ $lo_j <= p_j <= hi_j$ mana adalah "fungsi tub" berbentuk seperti \ ___ /, . Apakah ini berfungsi dalam teori, bekerja dalam praktik? (Tampaknya ada banyak banyak makalah teoritis tentang NLS +, tetapi minat saya praktis - kasus uji nyata atau realistis akan membantu saya untuk memilih di antara metode.)

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$

t u b (x, l o, h i)

$tub( x, lo, hi )$

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$

(Para ahli, harap tambahkan tag: "kuadrat-terkecil"?)

optimization constraints denis
sumber

5

Mengganti kendala ketat dengan fungsi penalti adalah teknik umum dalam optimasi numerik. Tampaknya apa yang Anda usulkan adalah bentuk khusus dari penggantian itu. Anda dapat membaca semua tentang teknik serupa, misalnya, di sini: stanford.edu/~boyd/cvxbook

David Ketcheson

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

11

Menambahkan persyaratan penalti kuadrat untuk menghilangkan kendala adalah pendekatan sederhana yang memberikan akurasi urutan 1 / faktor penalti saja. Oleh karena itu tidak disarankan untuk akurasi tinggi kecuali Anda membiarkan hukumannya hingga tak terbatas selama perhitungan. Tetapi faktor penalti yang tinggi membuat Hessian sangat tidak terkondisi, yang membatasi akurasi total yang dapat dicapai tanpa memperhitungkan kendala secara eksplisit.

Perhatikan bahwa batasan terikat jauh lebih mudah ditangani daripada kendala umum, di mana kendala itu hampir tidak pernah dikonversi menjadi penalti.

Solver L-BFGS-B (digunakan dengan sejarah sekitar 5 dimensi) biasanya memecahkan masalah yang terikat dengan sangat andal dan cepat di kedua dimensi rendah tinggi. Pengecualian adalah kesalahpahaman pada masalah yang bisa menjadi sangat jauh dari solusi, di mana mudah terjebak dengan metode keturunan.

Kami membuat banyak percobaan pada fungsi yang sangat beragam dalam banyak dimensi yang berbeda, dengan banyak solver yang berbeda tersedia, karena kami membutuhkan solver dengan batasan yang sangat kuat sebagai bagian dari perangkat lunak pengoptimalan global kami. L-BFGS-B jelas menonjol sebagai metode tujuan umum, meskipun tentu saja pada masalah kecil, pemecah lain berperforma lebih baik. Jadi saya akan merekomendasikan L-BFGS-B sebagai pilihan pertama, dan akan mencoba teknik alternatif kalau-kalau L-BFGS-B menangani masalah kelas khusus Anda dengan buruk.

Arnold Neumaier
sumber

L-BFGS tersedia di IPOPT, saya merevisi jawaban saya.

Ali

5

Saya hanya akan menggunakan IPLT pemecah NLP untuk tujuan umum . Ini adalah pemecah yang paling kuat di antara yang sudah saya coba.

Kecuali jika Anda memiliki beberapa persyaratan yang sangat khusus, tidak ada alasan mengapa Anda harus menuntut pemecah masalah khusus yang hanya berfungsi untuk NLS dengan kendala kotak.

Perubahan persyaratan (misalnya menambahkan kendala nonlinear) akan menyebabkan sakit kepala utama dengan pemecah masalah khusus. Anda tidak akan memiliki masalah seperti itu jika Anda menggunakan IPOPT untuk tujuan umum.

UPDATE: Anda dapat mencoba L-BFGS dengan IPOPT , lihat di bawah Quasi-Newton dalam dokumentasi.

Prosedur solusi dapat menjadi lebih cepat dengan mengorbankan memanjakan kekuatan IPOPT yang luar biasa. Menurut pendapat saya , gunakan derivatif yang tepat jika tersedia. Saya akan mulai mengacaukan perkiraan (seperti L-BFGS) hanya jika saya telah membuktikan masalah kinerja.

Ali
sumber

Saya tidak tahu seberapa baik IPOPT bekerja, tetapi saran Anda mengingatkan saya pada pernyataan serupa oleh para pendukung metode simpleks menurun. Karena kuadrat nonlinier adalah kelas masalah umum, langsung menolak menggunakan salah satu pemecah NLS yang ada tampaknya agak mencurigakan bagi saya.

Thomas Klimpel

@ThomasKlimpel Ya, denis harus memberi kami lebih banyak detail, maka kami bisa membantunya memilih pemecah yang tepat. :) Atau dia bisa memeriksanya sendiri dan mencari tahu mana yang paling sesuai dengan kebutuhannya. IPOPT tampaknya menjadi pemecah yang baik untuk memulai.

Ali

@ Ali, bisakah Anda menunjukkan beberapa "test case nyata atau realistis"?

denis

@denis aku bisa tapi aku tidak punya niat untuk melakukannya, itu akan membuatmu keluar dari jalur. Satu-satunya hal yang penting adalah bagaimana IPOPT menangani masalah Anda . Kecuali Anda memiliki beberapa persyaratan yang sangat khusus, itu harus menyelesaikannya dengan baik. IPOPT memiliki antarmuka untuk MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Pilih satu antarmuka dan uji apa yang terjadi dengan masalah Anda :) Menguji pemecah masalah spesifik juga tidak akan lebih mudah.

Ali

@ Thomas Klimpel, kira saya tidak jelas: Saya tidak menolak, tidak bertanya tentang paket, tetapi meminta wawasan atau menguji kasus: mengapa metode sepele ini tidak berfungsi dengan baik?

denis

1

Paket R minpack.lm CRAN menyediakan implementasi Levenberg-Marquardt dengan kendala kotak.

Secara umum, Levenberg-Marquardt jauh lebih cocok daripada L-BFGS-B untuk masalah kuadrat-terkecil. Ini akan bertemu (jauh) lebih baik pada masalah yang menantang. Ini juga akan jauh lebih cepat daripada tujuan umum IPOPT, karena dirancang untuk masalah non-linear kuadrat-terkecil.

Paket R memilih pendekatan proyeksi yang sangat mudah untuk menegakkan kendala (lihat kode sumber ). Bergantung pada implementasi LM yang Anda gunakan, bisa jadi sederhana untuk dimasukkan.

Sekarang, saran dalam komentar menggunakan transformasi, (misalnya transformasi sinus seperti dalam scipy) juga merupakan alternatif yang baik dan sederhana untuk mengubah algoritma LM Anda yang tidak dibatasi menjadi yang dibatasi. Anda juga perlu memasukkan transformasi dalam Jacobian jika Jacobian analitik.

jherek
sumber

0

(Bertahun-tahun kemudian) dua pemecah yang menangani batasan kotak:

Scipy least_squares memiliki 3 metode, dengan dokumen lengkap:
1. 'trf': Reflektif Wilayah Trust
2. 'dogbox'
3. 'lm': pembungkus lawas untuk MINPACK, tanpa batasan kotak.
ceres

denis
sumber

1

Scipy secara eksplisit mengatakan bahwa algoritma Levenberg-Marquardt tidak dapat menangani batasan kotak.

tholy

Kuadrat terkecil nonlinear dengan batasan kotak

Jawaban: