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.
9
Jawaban:
sumber
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 .
sumber
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.)
sumber