Bagaimana cara memilih algoritma optimasi yang tepat?

16

Saya perlu menemukan fungsi minimum. Membaca dokumen di http://docs.scipy.org/doc/scipy/reference/optimize.html Saya melihat bahwa ada beberapa algoritma yang melakukan hal yang sama, yaitu menemukan minimum. Bagaimana saya tahu yang mana yang harus saya pilih?

beberapa algoritma terdaftar

  • Minimalkan fungsi menggunakan algoritma simpleks downhill.
  • Minimalkan fungsi menggunakan algoritma BFGS.
  • Minimalkan fungsi dengan algoritma gradien konjugasi nonlinear.
  • Minimalkan fungsi f menggunakan metode Newton-CG.
  • Minimalkan fungsi menggunakan metode Powell yang dimodifikasi.

Fungsi saya linear. dimensi adalah sekitar 232750 (ini adalah berapa banyak gradien berbeda yang harus saya hitung setiap kali), dibutuhkan sekitar 2 menit untuk menghitung gradien dan biaya sekali, jadi tidak murah. Saya rasa saya tidak memiliki kendala. itu deterministik dan berkelanjutan.

siamii
sumber
Nah, Anda harus menyelidiki sifat masalah Anda: Apakah linear atau tidak? Apa dimensi itu? Apakah fungsi biaya Anda murah untuk dievaluasi? Bisakah Anda mengevaluasi derivatif Anda secara analitik dan / atau murah? Apakah Anda memiliki kendala? Jika Anda memiliki kendala dapatkah Anda menulis masalah Anda dengan mudah sebagai tidak dibatasi? Tolong uraikan hal-hal ini lebih lanjut.
usεr11852 mengatakan Reinstate Monic
@ user11852 Itu linear. Dimensi adalah sekitar 50 fitur, dibutuhkan sekitar 2 menit untuk menghitung gradien dan biaya satu kali, jadi tidak murah. Saya rasa saya tidak memiliki kendala.
siamii
Saya tidak yakin apa yang Anda maksud dengan "linear" di sini. Jika masalah Anda linier, gradiennya konstan dan murah untuk dihitung. Jika fungsi objektif Anda linier dan tidak memiliki kendala, minimumnya adalah -infinity (atau mungkin 0).
paul
@ paul: Dalam optimasi linearitas biasanya merujuk pada kendala, bukan ke fungsi itu sendiri. Saya (diberikan secara keliru) mengacu pada "linearitas" dalam kaitannya dengan kelancaran fungsi dan saya pikir itulah yang disebut OP juga. Dalam jawaban saya, saya sebagian besar didasarkan pada kenyataan bahwa dia berkata "terus menerus" sesudahnya.
usεr11852 mengatakan Reinstate Monic

Jawaban:

14

Berdasarkan apa yang Anda katakan: Saya berasumsi Anda harus mengoptimalkan 50 variabel; Saya juga berasumsi bahwa Anda mengalami situasi yang sangat mahal untuk menemukan turunan analitik (apalagi mengeluarkan angka) dan optimasi Anda tidak dibatasi.

Biarkan saya tekankan, Anda sedikit tidak beruntung menyebabkan antara 25-30 dan 100 variabel itu adalah sedikit zona senja ketika datang untuk memilih antara rutinitas optimasi skala besar atau kecil. Karena itu, tidak ada yang hilang.

Mengingat bahwa turunan orde pertama sekalipun mahal untuk menghilangkan jenis itu dapat membunuh ide metode Newton. Anda mungkin memiliki sedikit keberuntungan dengan Quasi-Newton (BFGS) meskipun jika Goni Anda agak diagonal seperti memulai. CG biasanya sedikit lebih lambat dari BFGS jadi mungkin itu tidak akan banyak meningkatkan hal-hal; gunakan jika memori juga merupakan masalah (atau gunakan saja L-BFGS dalam kasus itu). Selain itu mengingat betapa lambatnya mengevaluasi fungsi Anda, algoritma pencarian garis / curam paling sederhana akan sangat lambat; hal yang sama berlaku dengan Simulated Annealing dan varian pencarian acak lainnya (saya berasumsi Anda tidak memiliki akses ke HMC dan semua jazz itu).

Jadi, ketika Anda membutuhkan bang terbaik untuk uang Anda ketika datang ke evaluasi fungsi tunggal: Pergilah dengan metode Powell dan juga tes COBYLA; meskipun merupakan algoritma optimasi terbatas karena akan linier secara internal memperkirakan gradien fungsi Anda untuk mempercepat, ia akan dapat memanfaatkan linearitas fungsi Anda. Pasti juga mencoba NLopt untuk Python . Mereka memiliki banyak pengoptimal bebas-gradien; coba UOBYQA; itu adalah gagasan Powell juga (Optimasi Tanpa Batas DENGAN Perkiraan Kuadratik).

Secara singkat: Algoritma N-CG tergantung pada komputasi Hessian, dan Hessian Anda tampaknya sangat mahal untuk dihitung. NLCG dan BFGS tidak memerlukannya meskipun mungkin mencoba untuk mencoba menghitungnya sekali pada langkah pertama mereka.

Saya sengaja mengabaikan algoritma simpleks karena ini adalah binatang yang sama sekali berbeda; tidak ada hubungannya dengan gradien seperti itu. Cobalah tetapi saya tidak bisa mengomentarinya; itu benar-benar tergantung pada sifat masalah Anda.

Untuk referensi pertama yang baik tentang pengoptimalan numerik Buku CTKelly, Metode Iteratif untuk Pengoptimalan akan membuat Anda cukup jauh, cukup baik.

usεr11852 kata Reinstate Monic
sumber
Untuk referensi di masa mendatang: Anda mungkin tertarik untuk memeriksa beta Ilmu Komputasi di Stackexchange untuk pertanyaan serupa.
usεr11852 mengatakan Reinstate Monic
Terima kasih atas jawabannya. Sebenarnya, dimensi saya adalah 232.750. Ini adalah jumlah gradien yang saya hitung setiap kali. Saya melakukan evaluasi fungsi dan perhitungan gradien pada GPU. Apakah itu kompatibel dengan NLopt?
siamii
Saya belum pernah menggunakan NLopt pada GPU tetapi saya tidak melihat alasan yang jelas mengapa itu harus menjadi masalah terkait kompatibilitas. Saya mungkin mempertanyakan masalah ini meskipun sering operasi I / O dari dan ke GPU.
usεr11852 mengatakan Reinstate Monic
@ usεr11852, Dapatkah juga membahas perbandingan penurunan gradien & metode penguraian QR untuk meminimalkan fungsi biaya regresi linier? Apakah saya perlu mengajukan pertanyaan terpisah?
Dr Nisha Arora
@DrNishaArora: Ya. Itu akan sesuai untuk pertanyaan terpisah. Silakan lihat utas Mengapa menggunakan gradient descent untuk regresi linier, ketika solusi matematika bentuk-tertutup tersedia? untuk memastikan Anda menghindari duplikasi!
usεr11852 mengatakan Reinstate Monic
1

Mungkin Anda harus mendapatkan sendiri buku pengantar tentang optimasi numerik. Anda harus mempertimbangkan fungsi Anda untuk memutuskan algoritma.

Di antara algoritma yang Anda sebutkan, perbedaan penting adalah apakah Jacobian atau Hessian diperlukan atau hanya fungsi itu sendiri.

Menimbang bahwa ini adalah situs tanya jawab statistik dan dengan demikian berkaitan dengan variabel acak: pastikan fungsi Anda deterministik dapat dievaluasi dengan cara yang menghasilkan hasil yang berkelanjutan di ruang pencarian.

Cbeleites mendukung Monica
sumber
itu deterministik dan berkelanjutan.
siamii