Menguji metode optimasi numerik: Rosenbrock vs fungsi pengujian nyata

15

Tampaknya ada dua jenis fungsi pengujian utama untuk pengoptimal tanpa-derivatif:

  • satu garis seperti fungsi Rosenbrock , dengan titik awal
  • set poin data nyata, dengan interpolator

Apakah mungkin untuk membandingkan katakanlah 10d Rosenbrock dengan masalah 10d nyata?
Orang dapat membandingkan dengan berbagai cara: menggambarkan struktur minimum lokal,
atau menjalankan pengoptimal ABC di Rosenbrock dan pada beberapa masalah nyata;
tetapi keduanya tampaknya sulit.

(Mungkin para ahli teori dan peneliti hanyalah dua budaya yang sangat berbeda, jadi saya minta chimera?)

Lihat juga:


(Ditambahkan di September 2014):
Plot bawah ini membandingkan 3 algoritma DFO pada 14 fungsi tes di 8d dari 10 random start poin: BOBYQA PRAXIS SBPLX dari NLOpt
14 N-dimensi fungsi tes, Python bawah gist.github dari ini Matlab oleh A. Hedar × 10 titik awal seragam-acak di kotak pembatas fungsi masing-masing.×
×

Di Ackley, misalnya, baris atas menunjukkan bahwa SBPLX adalah yang terbaik dan PRAXIS mengerikan; pada Schwefel, panel kanan bawah menunjukkan SBPLX menemukan minimum pada titik awal acak ke-5.

Secara keseluruhan, BOBYQA yang terbaik pada 1, PRAXIS pada 5, dan SBPLX (~ Nelder-Mead dengan restart) pada 7 dari 13 fungsi tes, dengan Powersum melakukan undian. YMMV! Secara khusus, Johnson berkata, "Saya akan menyarankan Anda untuk tidak menggunakan fungsi-nilai (ftol) atau toleransi parameter (xtol) dalam optimasi global."

Kesimpulan: jangan letakkan semua uang Anda di atas satu kuda, atau pada satu fungsi tes.

masukkan deskripsi gambar di sini

denis
sumber

Jawaban:

13

Fungsi sederhana seperti Rosenbrock digunakan untuk debug dan pra-tes algoritma yang baru ditulis: Mereka cepat diimplementasikan dan dieksekusi, dan metode yang tidak dapat menyelesaikan masalah standar dengan baik tidak mungkin bekerja dengan baik pada masalah kehidupan nyata.

Untuk perbandingan menyeluruh terbaru dari metode bebas-derivatif untuk fungsi-fungsi mahal, lihat Optimalisasi bebas-derivatif: Tinjauan algoritma dan perbandingan implementasi perangkat lunak . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Jurnal Global Optimization, 2012. (Lihat juga halaman web yang menyertainya: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
sumber
Neumaier, dapatkah Anda menunjukkan beberapa masalah nyata, bukti, untuk "metode yang tidak dapat menyelesaikan masalah standar dengan baik tidak mungkin berhasil dengan baik pada masalah kehidupan nyata"? Saya menyadari bahwa itu tidak mudah. (Saya akan tertarik dengan komentar Anda tentang Hooker.) Juga, sekilas melihat model c dari tautan Anda menunjukkan princetonlibgloballib membutuhkan AMPL, dan source_convexmodels * .c semua ada yang hilang ";" setelah fscanf () - sepele tapi
denis
@Denis: Masalah-masalah seperti Rosenbrock berasal dari masa-masa awal optimasi otomatis, di mana orang mengisolasi kesulitan-kesulitan tipikal dalam contoh-contoh representatif sederhana yang dapat dipelajari tanpa kompleksitas numerik dari masalah-masalah kehidupan nyata. Dengan demikian mereka tidak benar-benar buatan, tetapi model kesulitan nyata yang disederhanakan. Sebagai contoh, Rosenbrock menggambarkan efek gabungan dari nonlinier yang kuat dan kondisi sakit ringan.
Arnold Neumaier
Situs AMPL ampl.com menawarkan versi siswa gratis untuk AMPL.
Arnold Neumaier
7

Keuntungan dari testis sintetik seperti fungsi Rosenbrock adalah bahwa ada literatur yang ada untuk dibandingkan, dan ada perasaan di masyarakat bagaimana metode yang baik berperilaku pada testcases tersebut. Jika setiap orang menggunakan testcase mereka sendiri, akan jauh lebih sulit untuk mencapai konsensus mana metode bekerja dan mana yang tidak.

Wolfgang Bangerth
sumber
1

(Saya harap tidak ada keberatan untuk menempelkan saya pada akhir diskusi ini. Saya baru di sini, jadi tolong beri tahu saya jika saya telah melampaui batas!)

Fungsi uji untuk algoritma evolusioner sekarang jauh lebih rumit daripada yang bahkan 2 atau 3 tahun yang lalu, seperti yang dapat dilihat oleh suite yang digunakan dalam kompetisi di konferensi seperti (sangat baru) 2015 Congress on Evolutionary Computation 2015. Lihat:

http://www.cec2015.org/

Suite tes ini sekarang mencakup fungsi-fungsi dengan beberapa interaksi non-linear antar variabel. Jumlah variabel bisa sebesar 1000, dan saya kira itu akan meningkat dalam waktu dekat.

Inovasi terbaru lainnya adalah "Kompetisi Optimalisasi Kotak Hitam". Lihat: http://bbcomp.ini.rub.de/

Algoritme dapat meminta nilai f (x) untuk titik x, tetapi tidak mendapatkan informasi gradien, dan khususnya tidak dapat membuat asumsi apa pun pada bentuk analitik fungsi objektif.

Dalam beberapa hal, ini mungkin lebih dekat dengan apa yang Anda sebut sebagai "masalah nyata" tetapi dalam pengaturan yang terorganisir dan objektif.

Lysistrata
sumber
1) "tidak keberatan": sebaliknya, tautan baik Anda dipersilakan! 2) ada plot bagus di sana? Metode dan masalah sama-sama retak, sehingga semakin sulit bagi siapa pun untuk menemukan masalah seperti mereka. Secara khusus, apakah Anda tahu metode untuk peramalan seri waktu ?
denis
Fungsi obyektif untuk Kompetisi CEC 2015 tentang Optimalisasi Multi-Objective Dynamic dapat dilihat di: sites.google.com/site/cec2015dmoocomp/competition-process/... Untuk kompetisi lain, buka cec2015.org dan klik kompetisi, lalu klik pada kompetisi yang diterima. Masing-masing memiliki fungsi sendiri. Makalah pada beberapa dari mereka memiliki plot yang bagus (untuk kasus 2D). Kompetisi konferensi GECCO dapat ditemukan di: sigevo.org/gecco-2015/competitions.html#bbc Hasil akan tersedia setelah 15 Juli.
Lysistrata
0

Anda dapat memiliki yang terbaik dari kedua dunia. NIST memiliki serangkaian masalah untuk minimizer, seperti pemasangan polinomial tingkat 10 ini , dengan hasil yang diharapkan dan ketidakpastian. Tentu saja, membuktikan bahwa nilai-nilai ini adalah solusi terbaik aktual, atau keberadaan dan sifat-sifat minimum lokal lainnya lebih sulit daripada pada ekspresi matematika yang terkontrol.

Davidmh
sumber
Nah, masalah NIST kecil (2 3 1 1 11 7 6 6 6 6 6 params). Apakah ada set tes yang "nyata" dan dapat direproduksi , untuk setiap sudut "nyata"? Lih sebuah Permintaan Masalah Simulasi Berbasis Optimization
denis