Bagaimana berusaha dengan cermat mengesampingkan kecemburuan?

9

Saya ingin meminimalkan fungsi tujuan yang rumit, dan saya tidak yakin apakah itu cembung. Apakah ada algoritma yang bagus yang mencoba membuktikan bahwa itu bukan cembung? Tentu saja algoritme dapat gagal untuk membuktikan ini, dalam hal ini saya tidak akan tahu apakah itu cembung atau tidak, dan ini OK; Saya hanya ingin mencoba mengesampingkan cembung sebelum saya menghabiskan banyak waktu mencoba untuk secara analitis menentukan apakah fungsi objektif cembung, misalnya dengan mencoba untuk menulis ulang masalah dalam bentuk standar yang dikenal sebagai cembung. Salah satu tes cepat akan mencoba untuk meminimalkan dari berbagai titik awal dan jika beberapa minimum lokal ditemukan dengan cara ini maka itu bukan cembung. Tapi saya bertanya-tanya apakah ada algoritma yang lebih baik yang dirancang dengan tujuan ini dalam pikiran.

MLE
sumber
Apakah fungsi tujuan lancar? Apakah itu satu dimensi? Apakah derivatif ke-2 (atau Goni) mahal untuk dievaluasi? Jika memungkinkan, saya ingin melihat formula, atau setidaknya memiliki gagasan yang lebih baik mengapa itu "rumit".
hardmath

Jawaban:

10

f(αx+(1α)y)αf(x)+(1α)f(y)α(0,1)x,yx,yαα={1/4,1/2,3/4}

Wolfgang Bangerth
sumber
6

Untuk sejumlah tes verifikasi konveksitas / non-konveksitas yang praktis bermanfaat, lihat (sanggahan diri, saya adalah penulis ketiga dalam makalah ini):

R. Fourer, C. Maheshwari, A. Neumaier, D. Orban, dan H. Schichl, Deteksi Convexity dan Concavity dalam Grafik Komputasi. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.

Perhatikan bahwa ada banyak fungsi yang cembung dalam domain yang diminati tetapi tidak dapat dengan mudah menjadi "disiplin", yaitu, ditulis dalam salah satu bentuk yang diperlukan oleh pemecah cembung terstruktur seperti CVX .

Arnold Neumaier
sumber
Apakah ini evolusi dari DrAmpl, Arnold?
Michael Grant
1
@MichaelGrant: Ya, ini adalah publikasi resmi dari materi Dr. AMPL.
Arnold Neumaier
2

Suatu fungsi bisa berupa non-cembung tanpa memiliki beberapa minimum. Ada berbagai metode optimasi yang menerapkan iterasi gradien konjugat (linier atau nonlinier), terpotong ketika norma operator negatif dihitung. Nilai negatif menunjukkan arah kelengkungan negatif (yang tidak dapat terjadi untuk fungsi cembung). Jika kelengkungan negatif jarang dijumpai, metode ini menyatu dalam sejumlah kecil iterasi optimisasi. (Jika prekondisi kualitas tersedia, langkah-langkah dalam juga harus menyatu dengan cepat.)

Jed Brown
sumber
2
Hanya untuk memperjelas, apa yang dirujuk Jed ketika dia mengatakan "negatif" adalah bahwa matriks turunan kedua dari fungsi memiliki nilai eigen negatif.
Wolfgang Bangerth