Menemukan minimum global fungsi 2D yang halus, terbatas, tidak cembung yang mahal untuk dievaluasi

17

Saya memiliki fungsi 2-D non-cembung terbatas yang ingin saya temukan minimum. Fungsinya cukup lancar. Mengevaluasi itu mahal. Kesalahan yang dapat diterima adalah sekitar 3% dari domain fungsi di setiap sumbu.

Saya mencoba menjalankan implementasi algoritma DIRECT di perpustakaan NLOPT, tetapi tidak memberikan peningkatan yang cukup besar terhadap pencarian brute force dalam hal jumlah evaluasi fungsi yang dibutuhkan untuk akurasi yang diperlukan dan ada beberapa pencilan.

Pemecah pengoptimalan global mana yang harus saya pertimbangkan?

Victor May
sumber
Bisakah Anda menghitung gradien, atau apakah Anda perlu memperkirakannya dengan quotients selisih?
Arnold Neumaier
Saya perlu memperkirakannya dengan quotients perbedaan.
Victor
Dalam hal ini, metode Newton tidak dapat direkomendasikan, karena turunan numerik kedua secara numerik sangat tidak stabil, dan sulit disetel untuk bekerja dengan aman.
Arnold Neumaier
@ Vik May, apa yang akhirnya Anda lakukan? (Jika Anda dapat memposting fungsi yang serupa dengan milik Anda, itu akan sangat membantu orang untuk membandingkan dan menyetel algoritme yang berbeda.)
denis
@Denis, saya mencoba untuk mendapatkan lebih cepat dari suatu algoritma untuk melacak suatu objek dalam video. Output dari algoritma adalah perkiraan kemungkinan untuk setiap lokasi gambar untuk mengandung objek yang dilacak. Gambar yang berisi perkiraan kemungkinan ini adalah fungsi yang saya coba optimalkan. Saya berakhir dengan kekerasan pada beberapa langkah resolusi. Untuk informasi lebih lanjut tentang algoritma pelacakan yang dimaksud, baca makalah "Pelacakan Berbasis Fragmen Kuat menggunakan Histogram Integral".
Victor

Jawaban:

12

Saya ingin menyarankan pendekatan yang agak berbeda dibandingkan dengan jawaban lain, meskipun @barron secara tidak langsung membahas hal yang sama.

Alih-alih mengoptimalkan fungsi Anda secara langsung, yaitu dengan mengevaluasinya pada serangkaian poin poin yang (semoga) menyatu dengan (lokal) optimal, Anda bisa menggunakan konsep , yang sangat cocok untuk masalah tipe yang Anda gambarkan (biaya tinggi, halus, terbatas, berdimensi rendah yaitu kurang dari 20 yang tidak diketahui).sebagai pemodelan penggantix1,x2,,xksurrogate modelling

Secara khusus, pemodelan pengganti bekerja dengan mengatur fungsi model dari fungsi Anda yang sebenarnya . Kuncinya adalah bahwa walaupun tentu saja tidak sepenuhnya mewakili , jauh lebih murah untuk mengevaluasi. f R dR c fcRdRfRdRcf

Jadi, proses pengoptimalan yang khas adalah sebagai berikut:

  1. Evaluasi pada set poin awal . Perhatikan bahwa turunan tidak diperlukan. Perhatikan juga bahwa titik-titik ini harus didistribusikan secara merata di seluruh ruang pencarian, misalnya dengan Latin Hypercube Sampling atau desain pengisian ruang yang serupa.j x 1 , x 2 , , x jfjx1,x2,,xj
  2. Berdasarkan dataset asli ini, buat fungsi model . Anda dapat menggunakan validasi silang untuk memvalidasi model Anda (yaitu, gunakan hanya sebagian dari titik asli untuk membuat , dan kemudian gunakan sisa dataset untuk memeriksa seberapa baik memprediksi nilai-nilai itu)j c ccjcc
  3. Gunakan kriteria seperti kriteria Expected Improvement (EI) untuk mencari tahu di mana '' mengisi 'lebih banyak sampel untuk membuat lebih akurat dengan pengambilan sampel . Ini sebenarnya jauh lebih baik dipelajari secara teoritis daripada yang mungkin terlihat, dan kriteria EI diteliti dengan sangat baik. Kriteria EI juga bukan kriteria serakah, sehingga Anda berdua mendapatkan peningkatan keseluruhan yang baik dari akurasi model, sementara memprioritaskan akurasi dekat potensi optima.fcf
  4. Jika model Anda tidak cukup akurat, ulangi langkah 3, jika tidak gunakan rutin optimasi favorit Anda untuk menemukan yang optimal , yang akan sangat murah untuk dievaluasi (sehingga Anda dapat menggunakan rutin apa pun yang Anda inginkan, bahkan yang membutuhkan turunan, atau hanya mengevaluasi fungsi dalam fine mesh).c

Secara umum, inilah yang dimaksud dengan EGO, Efficient Global Optimization, seperti yang disarankan @barron. Saya ingin menekankan bahwa untuk aplikasi Anda, ini tampaknya sangat cocok - Anda mendapatkan model yang sangat akurat berdasarkan evaluasi relatif sedikit , dan kemudian dapat menggunakan algoritma pengoptimalan yang Anda inginkan. Apa yang sering juga menarik adalah bahwa Anda sekarang dapat mengevaluasi pada mesh dan plot itu, sehingga mendapatkan wawasan tentang penampilan umum . Hal lain yang menarik adalah bahwa kebanyakan teknik pemodelan pengganti juga memberikan perkiraan kesalahan statistik, sehingga memungkinkan estimasi ketidakpastian.c ffcf

Bagaimana membangun tentu saja merupakan pertanyaan terbuka, tetapi sering kali Kriging atau yang disebut model pemetaan ruang digunakan.c

Tentu saja, ini semua sedikit pekerjaan pengkodean, tetapi banyak orang lain telah melakukan implementasi yang sangat baik. Di Matlab, saya hanya tahu DACE toolbox perangkat lunak gratis. TOMLAB mungkin juga menawarkan paket Matlab, tetapi membutuhkan biaya - namun, saya percaya itu juga bekerja di C ++ dan memiliki kemampuan yang jauh lebih banyak daripada yang pernah dimiliki DACE. (Catatan: Saya adalah salah satu pengembang DACE versi baru, yang akan segera dirilis, yang akan menawarkan dukungan tambahan untuk EGO.)

Semoga gambaran umum yang kasar ini membantu Anda, ajukan pertanyaan jika ada poin yang dapat dibuat lebih jelas atau hal-hal yang saya lewatkan, atau jika Anda ingin materi lebih lanjut tentang masalah ini.

OscarB
sumber
Fwiw, google surrogate-model memunculkan Surrogate Modelling Lab di Ghent University, dan buku Engineering Design via Surrogate Modelling , 2008 228p 0470770791. Masalah dengan pendekatan yang sangat umum adalah bahwa Anda segera memiliki wastafel dapur yang penuh dengan varian metode, lebih lanjut dari fungsi tes nyata .
denis
3

Untuk fungsi yang lancar, metode Optimasi Global yang Efisien harus berkinerja cukup baik dan secara dramatis lebih efisien daripada DIRECT. Implementasi tersedia di TOMLAB (belum pernah menggunakannya sendiri) dan DAKOTA (yang saya telah sukses dengannya).

Barron
sumber
1

Karena fungsinya halus, metode Newton akan menjadi metode yang paling efisien untuk menemukan nilai minimum. Karena fungsi ini tidak cembung, Anda harus menerapkan trik yang biasa untuk membuat metode Newton menyatu (modifikasi Levenberg-Marquardt, pencarian garis atau wilayah kepercayaan untuk mengglobal). Jika Anda tidak dapat memperoleh turunan dari fungsi Anda, cobalah menghitungnya melalui perbedaan hingga atau menggunakan pembaruan BFGS. Jika Anda mencurigai bahwa masalahnya memiliki lebih dari satu minimum lokal, orang hanya akan memulai metode Newton dari sekelompok titik yang dipilih secara acak atau tidak begitu acak dan melihat di mana mereka bertemu.

Wolfgang Bangerth
sumber
Masalah saya memang memiliki minimum lokal. Metode apa yang ada untuk memilih titik awal?
Victor
1
Kecuali Anda tahu apa-apa tentang masalah tersebut, pengambilan sampel statistik pada dasarnya adalah satu-satunya pilihan Anda.
Wolfgang Bangerth
@ Wolfgang: Ada ide bagaimana mendekati "sampling statistik"? Coba saja 10, 100, ... tebakan awal acak? Apakah ada pendekatan "lebih keras"? Saya bertanya, karena saya punya lebih atau kurang masalah yang sama (lihat scicomp.stackexchange.com/q/4708/1789 )
André
Itu semua tergantung pada apa yang Anda ketahui tentang fungsinya. Jika Anda tahu sesuatu seperti "skala panjang tipikal" untuk fungsi Anda yang akan memberikan indikasi seberapa jauh ekstremitas lokal akan dipisahkan. Ini juga akan memberi Anda indikasi berapa banyak poin yang Anda harus mulai dengan, dan seberapa jauh mereka harus dipilih satu sama lain.
Wolfgang Bangerth
0

Karena evaluasi Anda mahal, Anda perlu memanfaatkan menjalankan evaluasi fungsi sevaral secara paralel.

Saya akan merekomendasikan Anda untuk melihat kode ini . Matematika di belakang dijelaskan di sini .

Paul
sumber
1
Apakah kode dan artikel ini ditulis oleh Anda? Jika demikian, dapatkah Anda secara eksplisit mengatakannya dalam jawaban Anda? Juga, saat ini, Anda dapat meningkatkan jawabannya dengan memberikan deskripsi saran Anda.
nicoguaro