Mengoptimalkan fungsi yang tidak diketahui yang hanya dapat dievaluasi?

Diberikan fungsi yang tidak diketahui , kita dapat mengevaluasi nilainya di titik mana pun di domainnya, tetapi kami tidak memiliki ekspresinya. Dengan kata lain, seperti kotak hitam bagi kita. $f:\mathbb R^d \to \mathbb R$ $f$

Apa nama untuk masalah menemukan minimizer ? Apa saja metode di luar sana? $f$

Apa nama untuk masalah menemukan solusi untuk persamaan ? Apa saja metode di luar sana? $f(x)=0$

Dalam dua masalah di atas, apakah ide yang bagus untuk melakukan interpolasi atau menyesuaikan dengan beberapa evaluasi f: menggunakan fungsi dengan bentuk dan parameter yang diketahui ditentukan, dan kemudian meminimalkan atau menemukan akarnya? $(x_i, f(x_i)), i=1, \dots, n$ $g_\theta$ $\theta$ $g_\theta$

Terima kasih dan salam!

optimization Tim
sumber

Bisakah Anda mengevaluasi gradiennya pada titik tertentu?

chaohuang

@chaohuang: Ada dua kasus: Anda mungkin atau mungkin tidak mengevaluasi gradiennya, tergantung pada asumsi.

Tim

Jika gradien tersedia, tugas yang Anda minta dapat diselesaikan dengan algoritma berbasis gradien. Misalnya, minimum, atau setidaknya minimum lokal, dapat dihitung dengan metode penurunan paling curam, dan akar dapat ditemukan dengan metode Newton.

chaohuang

Dan jika gradien tidak diketahui, ada metode metaheuristik , yang juga disebut metode derivatif-bebas atau kotak-hitam dan biasanya dalam bentuk optimasi stokastik.

chaohuang

Apakah Anda tahu apakah fungsinya halus (bahkan jika Anda tidak dapat mengevaluasi gradien)? Apakah Anda tahu apakah fungsinya cembung? Jika tidak cembung, apakah Anda tahu apakah itu setidaknya Lipschitz terus menerus atau tidak? Jika fungsi ini sepenuhnya umum, maka ini adalah masalah yang tidak ada harapan.

Brian Borchers

Jawaban:

Metode yang Anda cari - yaitu, yang hanya menggunakan evaluasi fungsi tetapi bukan turunan - disebut metode optimasi bebas derivatif . Ada banyak literatur di dalamnya, dan Anda dapat menemukan bab tentang metode tersebut di sebagian besar buku tentang pengoptimalan. Pendekatan khas meliputi

Perkiraan gradien dengan perbedaan hingga jika seseorang dapat mengharapkan fungsi menjadi halus dan, mungkin, cembung;
Metode Monte Carlo seperti Simulasi Annealing;
Algoritma Genetika.

Wolfgang Bangerth
sumber

Bisakah saya menambahkan "Surrogate Modelling" ke daftar itu? Mereka sangat berlaku untuk optimasi kotak hitam, khususnya jika fungsinya mahal untuk dievaluasi.

OscarB

Ya, Anda bisa :-) Tentunya tambahan yang bagus.

Wolfgang Bangerth

Kita juga bisa menggunakan metode Nelder-Mead jika estimasi optima yang baik diketahui.

Ya, Anda bisa menggunakan Nelder-Mead, tapi ini algoritma yang mengerikan dibandingkan dengan kebanyakan yang lainnya.

Wolfgang Bangerth

@WolfgangBangerth: Komentar Anda tentang Nelder-Mead hanya valid dalam dimensi d> 2. Dalam dua dimensi, pada banyak masalah merupakan metode yang sangat baik dan sangat sulit dikalahkan.

Arnold Neumaier

Saya pikir Anda harus mulai dengan: Workshop GECCO tentang Benchmarking Optimalisasi Kotak Hitam Parameter Nyata (BBOB 2016) http://numbbo.github.io/workshops/index.html

Anda akan menemukan banyak algoritma berbeda yang telah digunakan dalam kompetisi sebelumnya, dan yang telah dibandingkan secara umum. Jika Anda mulai di tempat lain, Anda akan segera tenggelam dalam ratusan makalah yang mengklaim metode dan algoritme mereka berkinerja lebih baik daripada yang lain dengan sedikit bukti aktual untuk klaim tersebut.

Sampai baru-baru ini, sejujurnya, itu adalah keadaan yang memalukan dan semua kekuatan untuk INRIA, GECCO dan banyak lainnya atas upaya yang telah mereka lakukan dalam membangun kerangka kerja untuk perbandingan rasional.

Lysistrata
sumber

-1

Saya baru saja menambahkan bahwa salah satu kunci di sini adalah mampu mengukur metode optimasi pada CPU multicore . Jika Anda dapat melakukan beberapa evaluasi fungsi secara bersamaan, itu memberi Anda speedup sama dengan sejumlah core yang terlibat. Bandingkan ini dengan hanya menggunakan model respons yang sedikit lebih akurat, yang membuat Anda 10% lebih efisien atau lebih.

Saya akan merekomendasikan untuk melihat kode ini , dapat bermanfaat bagi orang yang memiliki akses ke banyak core. Matematika di belakangnya dijelaskan dalam makalah ini .

Paul
sumber

Jawaban ini terlalu pendek untuk berguna (dan tetap berguna, karena tautan dapat hilang kapan saja). Juga, harap sebutkan bahwa Anda adalah pembuat perangkat lunak ini .

Christian Clason