Metode berbasis Newton dalam optimisasi vs. penyelesaian sistem persamaan nonlinier

Saya meminta klarifikasi tentang pertanyaan terbaru tentang minpack , dan mendapat komentar berikut:

Setiap sistem persamaan setara dengan masalah optimisasi, itulah mengapa metode berbasis Newton dalam optimasi sangat mirip dengan metode berbasis Newton untuk menyelesaikan sistem persamaan nonlinier.

Apa yang membingungkan saya tentang komentar ini (dan pendapat negatif terkait tentang pemecah kuadrat nonlinier khusus seperti minpack) mungkin paling baik dijelaskan pada contoh metode gradien konjugat . Metode ini berlaku untuk sistem $Ax=b$ dengan matriks pasti positif simetris positif $A$ . Hal ini juga dapat digunakan untuk memecahkan umum setidaknya masalah persegi $\operatorname{min}_x||Ax-b||^2$ untuk matriks arbitrer $A$ , tetapi melakukannya tidak dianjurkan. Satu penjelasan mengapa kita tidak melakukan ini adalah bahwa jumlah kondisi sistem akan meningkat secara signifikan.

Tetapi jika mengubah sistem persamaan menjadi masalah optimisasi dianggap bermasalah bahkan untuk kasus linier, mengapa harus kurang bermasalah untuk kasus umum? Tampaknya entah bagaimana terkait dengan menggunakan algoritma optimasi canggih, alih-alih menggunakan pemecah kuadrat terkecil nonlinear. Tetapi bukankah masalah yang terkait dengan membuang informasi dan meningkatkan jumlah kondisi sistem relatif independen dari algoritma optimasi yang sebenarnya digunakan?

optimization least-squares Thomas Klimpel
sumber

Jawaban:

Karena salah satu jawaban saya telah dikutip, saya akan mencoba menjelaskan mengapa saya menyarankan menggunakan IPOPT daripada MINPACK.

Keberatan saya untuk menggunakan MINPACK tidak ada hubungannya dengan algoritma yang digunakan MINPACK dan segala sesuatu yang berkaitan dengan implementasinya. Keberatan utama saya adalah bahwa perangkat lunak tanggal kembali ke 1980, dan terakhir diperbarui pada tahun 1999. Jorge Moré sudah pensiun; Saya ragu dia atau penulis perangkat lunak lain mengawasi hal itu lagi, dan tidak ada tim orang yang secara aktif mendukungnya. Satu-satunya dokumentasi yang dapat saya temukan pada perangkat lunak adalah laporan teknis Argonne 1980 asli yang ditulis oleh Jorge Moré dan penulis MINPACK lainnya. (Bab 1-3 dapat ditemukan di sini , dan Bab 4 dapat ditemukan di sini.) Setelah mencari kode sumber MINPACK dan membaca dokumentasi (PDF adalah gambar yang dipindai, dan tidak dapat dicari), saya tidak melihat opsi untuk mengakomodasi kendala. Karena poster asli dari masalah kuadrat-terkecil nonlinier ingin menyelesaikan masalah kuadrat-terkecil nonlinier, MINPACK bahkan tidak akan menyelesaikan masalah itu.

Jika Anda melihat milis IPOPT, beberapa pengguna menunjukkan bahwa kinerja paket pada masalah nonlinier kuadrat (NLS) dicampur relatif terhadap algoritma Levenberg-Marquardt dan algoritma NLS yang lebih khusus (lihat di sini , di sini , dan di sini ). Kinerja IPOPT relatif terhadap algoritma NLS, tentu saja, tergantung masalah. Mengingat umpan balik pengguna tersebut, IPOPT sepertinya merupakan rekomendasi yang masuk akal relatif terhadap algoritma NLS.

Namun, Anda menyatakan bahwa algoritma NLS harus diselidiki. Saya setuju. Saya hanya berpikir bahwa sebuah paket yang lebih modern dari MINPACK harus digunakan karena saya percaya itu akan berkinerja lebih baik, lebih bermanfaat, dan didukung. Ceres tampaknya seperti paket kandidat yang menarik, tetapi tidak dapat menangani masalah yang dibatasi saat ini. TAOakan bekerja pada masalah kuadrat-kotak terbatas, meskipun tidak mengimplementasikan Levenberg-Marquardt klasik, tetapi sebaliknya mengimplementasikan algoritma bebas-derivatif. Algoritma bebas derivatif mungkin akan bekerja dengan baik untuk masalah skala besar, tapi saya tidak akan menggunakannya untuk masalah skala kecil. Saya tidak dapat menemukan paket lain yang menginspirasi kepercayaan besar dalam rekayasa perangkat lunak mereka. Misalnya, GALAHAD tampaknya tidak menggunakan kontrol versi atau pengujian otomatis, sekilas. MINPACK sepertinya tidak melakukan hal-hal itu juga. Jika Anda memiliki pengalaman dengan MINPACK atau rekomendasi mengenai perangkat lunak yang lebih baik, saya akan mendengarkan.

Dengan semua itu dalam pikiran, kembali ke kutipan dari komentar saya:

Setiap sistem persamaan setara dengan masalah optimisasi, itulah mengapa metode berbasis Newton dalam optimasi sangat mirip dengan metode berbasis Newton untuk menyelesaikan sistem persamaan nonlinier.

Sebuah komentar yang lebih baik mungkin ada hubungannya dengan:

$n$ $n$ $g(x) = 0$

Pernyataan ini berlaku bahkan untuk memecahkan sistem persamaan di bawah kendala. Saya tidak tahu ada algoritma yang dianggap "pemecah persamaan" untuk kasus di mana ada kendala pada variabel. Pendekatan umum yang saya tahu, mungkin jaundice oleh beberapa semester kursus optimasi dan penelitian di laboratorium optimasi, adalah untuk memasukkan kendala pada sistem persamaan ke dalam formulasi optimasi. Jika Anda mencoba menggunakan batasan dalam skema mirip Newton-Raphson untuk penyelesaian persamaan, Anda mungkin akan berakhir dengan gradien yang diproyeksikan atau metode wilayah kepercayaan yang diproyeksikan, sama seperti metode yang digunakan dalam optimasi terbatas.

Geoff Oxberry
sumber

Saya punya pengalaman dengan MINPACK. Cukup bagus sebagai metode lokal. Saya suka itu kriteria berhenti bekerja dengan baik tanpa mengutak-atik. Saya tahu bahwa hal dengan kendala dapat mengganggu, terutama karena itu tidak akan menjadi perubahan besar pada algoritma itu sendiri. Saya bahkan tahu tentang implementasi LM yang menawarkan batasan pada variabel dan batasan linear umum, tetapi implementasi ini tidak jauh lebih muda dari MINPACK itu sendiri, dan saya belum repot-repot untuk mengevaluasinya.

Thomas Klimpel

g (x) = 0

$g(x)=0$

‖ g (x) ‖^{2}

$\lVert g(x) \rVert^2$

@JedBrown: Saya harus mengubah bahasa sekitar. Dalam pandangan saya, optimasi derivatif-bebas (DFO) hanya disukai ketika evaluasi fungsi sangat mahal. Untuk beberapa alasan, kasus mani yang muncul dalam pikiran adalah ketika tujuannya melibatkan penyelesaian PDE, itulah sebabnya saya mengatakan "skala besar" (tentu saja, bagi saya, dalam optimasi, "PDE skala besar" berarti sesuatu yang berbeda dari untuk Anda, yang memecahkan PDE secara paralel secara teratur). Ketika saya berpikir tentang "menyelesaikan persamaan dengan kendala", masalah yang saya pikirkan adalah . (lanjutan)

g (x) = 0, x \in S, S \subset R^{n}, S \neq R^{n}

$g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$

Geoff Oxberry

@JedBrown: Cara standar untuk mengatasi masalah itu adalah dengan menyelesaikan . Mungkin ada cara lain, tapi saya tidak tahu. Saya tidak menyarankan satu discard ; minima dengan nilai fungsi objektif nol tidak dengan jelas menyelesaikan sistem persamaan yang diselesaikan. Dalam kasus non-konveks, metode optimasi global diperlukan untuk mengesahkan ada atau tidak adanya solusi. Saya tidak punya banyak pengalaman dengan ketidaksetaraan variasi, jadi tidak segera jelas bagi saya di mana VI bermain di sini, terutama karena tidak selalu berbentuk kerucut.

min_{x \in S} ‖ g (x) ‖^{2}

$\min_{x \in S} \|g(x)\|^2$

g (x) = 0

$g(x) = 0$

S

$S$

Geoff Oxberry

Jadi, Anda masih perlu untuk dapat tepat menentukan apa yang Anda maksud dengan solusi yang terletak di batas . VIs, sering ditulis sebagai formulasi saling melengkapi, melakukan hal itu. Saya memiliki pendapat yang berlawanan tentang bebas turunan, terutama ketika ruang desainnya besar. Jika tujuannya melibatkan penyelesaian PDE yang mahal, saya melihat itu sebagai persyaratan bahwa kita memiliki adjoin sehingga kita dapat menggunakan gradien untuk menjelajahi ruang desain. Adjoin PDE hanya membutuhkan biaya beberapa kelipatan penyelesaian ke depan yang tidak tergantung pada dimensi ruang. Ini menempatkan persyaratan tambahan pada kelancaran model.

S

$S$

Jed Brown

Jika sistem nonlinear yang diberikan adalah kondisi optimalitas urutan pertama untuk masalah optimasi, maka kita sering dapat menghasilkan algoritma yang lebih kuat dengan menggunakan informasi itu. Sebagai contoh, perhatikan persamaannya

f (x) = x^{2} - \exp (- 4 (x - 2)^{2}) [click for Wolfram Alpha]

$f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$

Plot tujuan awal

Ini jelas memiliki minimum yang unik dan kami berharap metode optimasi kami menemukannya terlepas dari titik awal. Tetapi jika kita hanya melihat kondisi urutan optimalitas pertama, kami sedang mencari solusi dari [Wolfram Alpha] $x$ $\nabla f(x) = 0$

gradien

yang memiliki solusi unik, tetapi banyak metode pencarian root bisa macet seminimal mungkin.

Jika kita merumuskan masalah optimasi baru untuk meminimalkan norma gradien kuadrat, kami sedang mencari global minimum dari [Wolfram Alpha] yang memiliki beberapa minimum lokal. $x$ $\lVert\nabla f(x)\rVert^2$

masukkan deskripsi gambar di sini

Untuk meringkas, kami mulai dengan masalah optimisasi yang memiliki solusi unik yang kami dapat menjamin bahwa metode akan menemukan. Kami dirumuskan ulang sebagai masalah pencarian akar nonlinier yang memiliki solusi unik yang dapat kami identifikasi secara lokal, tetapi metode pencarian akar (seperti Newton) mungkin mandek sebelum mencapainya. Kami kemudian merumuskan kembali masalah pencarian root sebagai masalah optimisasi yang memiliki banyak solusi lokal (tidak ada ukuran lokal yang dapat digunakan untuk mengidentifikasi bahwa kami tidak pada tingkat minimum global).

Secara umum, setiap kali kami mengonversi masalah dari pengoptimalan ke penelusuran akar atau sebaliknya, kami membuat metode yang tersedia dan jaminan konvergensi terkait menjadi lebih lemah. Mekanik sebenarnya dari metode ini seringkali sangat mirip sehingga memungkinkan untuk menggunakan kembali banyak kode antara pemecah nonlinier dan optimisasi.

Jed Brown
sumber

Jed, tautan WA itu tidak cukup sesuai dengan apa yang Anda katakan. Tanda kurung diabaikan atau diteruskan dengan tidak benar di URL.

Bill Barth

Aneh, tautannya bekerja untuk saya. Bisakah ini tergantung pada browser web? Adakah saran cara alternatif untuk menyajikan ini?

Jed Brown

Tidak yakin. Memotong dan menempelkan tautan yang diformat ulang dari satu tab ke tab berikutnya menyebabkannya memasang WA untuk mengacaukannya sendiri!

Bill Barth

Apakah ada orang lain yang mengalami masalah dengan tautan? Saya telah mencoba di banyak browser dan berfungsi dengan baik dalam setiap kasus.

Jed Brown

Ini jawaban yang bagus. Namun, saya memutuskan untuk menerima jawaban Geoff Oxberry, karena bagian dari apa yang saya coba pahami adalah masalah "dunia nyata" yang terkait dengan pertanyaan itu. Ini termasuk bahwa orang-orang seperti saya menggunakan dan merekomendasikan MINPACK, meskipun mengetahui tentang kekurangannya, dan bahwa orang lain meminta nasihat tentang penyelesaian sistem non-linear "kecil", tetapi tidak berhasil menguji bahkan satu solver selama tiga bulan. jangka waktu.

Thomas Klimpel