Mengatasi masalah optimisasi nonlinier tanpa kendala pada GPU

18

Saya mencoba menyelesaikan beberapa masalah optimasi nonlinear pada GPU (CUDA).

Fungsi obyektif adalah fungsi nonlinier yang halus, dan gradiennya relatif murah untuk dihitung secara analitis, jadi saya tidak perlu repot dengan perkiraan numerik.

Saya ingin menyelesaikan masalah ini dengan sebagian besar ops matematika fp32 (karena berbagai alasan), jadi metode optimasi nonlinear mana yang lebih kuat terhadap kesalahan pembulatan sementara memiliki kinerja yang baik? (misalnya konjugasi gradien / kuasi newton / wilayah kepercayaan), adakah yang pernah mencoba BFGS pada GPU dengan hasil yang baik?

BTW, Hessian, jika diperlukan, relatif kecil dalam kasus saya (<64x64 biasanya), tapi saya harus menyelesaikan ribuan masalah optimasi skala kecil ini secara bersamaan.

optimization cuda pengguna0002128
sumber
4
Mengingat ukuran kecil masalah Anda, saya tidak berpikir pilihan algoritma tertentu (misalnya, BFGS) akan menjadi tantangan Anda yang paling signifikan. Sebagai gantinya, itu akan meminimalkan GPU <-> overhead komunikasi CPU. Mungkin cara terbaik untuk melakukannya adalah dengan memecahkan banyak contoh masalah Anda secara paralel pada GPU. Muat semuanya sekaligus, selesaikan semuanya sekaligus, unduh hasilnya sekaligus. Saya tidak punya saran khusus tentang algoritma, tetapi saya akan mengatakan bahwa GPU lebih baik dengan loop daripada dengan cabang.
Michael Grant
1
@Michael C. Grant: Nah, overhead komunikasi dapat disembunyikan dengan perhitungan dengan mudah dalam kasus saya, jadi itu bukan hambatan di sana, saya sangat cenderung untuk menggunakan BFGS dengan memori terbatas atau BFGS standar di sini, tetapi tidak yakin apakah ada pendekatan yang lebih baik.
user0002128
Beberapa orang menerapkan LBFGS dengan CUDA .
BenC

Jawaban:

8

Saya telah menerapkan cukup beragam pemecah non-linear pada GPU, termasuk LBFGS, Barzilai Borwein gradient descent dan gradien konjugat non-linear.

Untuk ini, gradien konjugat non-linier dari Dai & Yuan adalah yang paling efisien. Secara umum, versi lain dari gradien konjugasi nonlinear mungkin lebih efisien (seperti CG-DESCENT), tetapi juga bisa lebih sulit untuk diterapkan.

LBFGS pada umumnya merupakan pilihan yang sangat solid, dan kecuali Anda benar-benar kekurangan memori, mungkin ini adalah tempat terbaik untuk memulai.

Baik gradien konjugasi dan BFGS membutuhkan pencarian baris, yang merupakan masalah fp32. Daripada menggunakan kondisi Wolfe standar untuk pencarian baris, saya sarankan menggunakan perkiraan kondisi Wolfe yang disarankan di sini . Makalah ini sedikit terlibat, tetapi yang penting adalah persamaan 4.1. Pada dasarnya mereka secara eksplisit memperkenalkan presisi yang dapat Anda gunakan untuk menghitung fungsi Anda.

Pertimbangan untuk GPU:

Anda memiliki banyak masalah kecil, yang sedikit berbeda dari kasus penggunaan saya untuk satu masalah besar. Pertimbangkan menjalankan 1 masalah per blok GPU (atau warp, lebih tepatnya) jika Anda dapat memparalelkan evaluasi fungsi dan gradien untuk menggunakan semua utas dalam sebuah blok. Dengan begitu itu bukan masalah jika masalah yang berbeda membutuhkan jumlah iterasi yang berbeda.

Jika ini bukan pilihan, saya akan pergi dengan pemecah LBFGS. Jika fungsi Anda berperilaku baik, Anda mungkin lolos hanya dengan menggunakan ukuran langkah 1 (menghindari pencarian baris) dan hanya menjalankan semua masalah untuk sejumlah iterasi yang tetap.

LKlevin
sumber
0

Saya menyarankan Anda untuk menggunakan Levenberg Marquardt (varian wilayah kepercayaan) karena digunakan dalam banyak aplikasi praktis dan menunjukkan kinerja kecepatan vs akurasi yang sangat baik. Selain itu, untuk GPU ada beberapa perpustakaan (misalnya cuLM https://github.com/zitmen/cuLM ), yang dapat Anda coba. Jika mereka tidak melakukan pekerjaan itu, ada banyak sumber daya untuk Anda terapkan. Menerapkan LM sama sekali tidak sulit. Anda hanya harus berhati-hati dalam meminimalkan komunikasi GPU. Untuk mendapatkan ide singkat:

http://on-demand.gputechconf.com/gtc/2012/presentations/S0231-Levenberg-Marquardt-Using-Block-Sparse-Matrices-on-CUDA.pdf

Tolga Birdal
sumber
2
Levenberg-Marquart adalah untuk kuadrat terkecil nonlinier. Saya tidak berpikir dia menyebutkan sesuatu tentang kuadrat terkecil.
Kurt
0

Mungkin prosedur annealing yang disimulasikan dapat menangani kesalahan pembulatan lebih baik (dan mudah diparalelkan).

Anda mulai dengan grid kasar area pencarian dan parameter "suhu" awal

Pada setiap langkah Anda menghitung poin solusi yang memungkinkan (satu juga dapat menerima poin non-solusi, dengan beberapa probabilitas berbanding terbalik dengan suhu)

Kemudian pertahankan hanya solusi pada langkah itu dan naikkan suhu yang menyediakan kisi-kisi yang lebih halus untuk iterasi berikutnya

Lakukan ini sampai suhu <batas / ambang batas akurasi yang diberikan

Nikos M.
sumber