Saya sangat terkejut ketika saya mulai membaca sesuatu tentang optimasi non-cembung secara umum dan saya melihat pernyataan seperti ini:
Banyak masalah praktis yang penting adalah non-cembung, dan sebagian besar masalah non-cembung sulit (jika bukan tidak mungkin) untuk dipecahkan secara tepat dalam waktu yang wajar. ( sumber )
atau
Secara umum itu NP-sulit untuk menemukan minimum lokal dan banyak algoritma mungkin macet pada titik pelana. ( sumber )
Saya melakukan semacam optimasi non-cembung setiap hari - yaitu relaksasi geometri molekul. Saya tidak pernah menganggapnya sebagai sesuatu yang rumit, lambat dan mungkin macet. Dalam konteks ini, kami memiliki permukaan non-cembung yang jelas banyak dimensi (> 1000 derajat kebebasan). Kami menggunakan sebagian besar teknik tingkat pertama yang diturunkan dari penurunan paling curam dan pendinginan dinamis seperti FIRE , yang konvergen dalam beberapa ratus langkah ke minimum lokal (kurang dari jumlah DOF). Saya berharap bahwa dengan penambahan kebisingan stokastik itu harus kuat sekali. (Optimalisasi global adalah cerita yang berbeda)
Saya entah bagaimana tidak bisa membayangkan bagaimana permukaan energi potensial akan terlihat, untuk membuat metode optimasi ini macet atau perlahan-lahan bertemu. Misalnya PES yang sangat patologis (tetapi bukan karena ketidakcocokan) adalah spiral ini , namun ini bukan masalah besar.Bisakah Anda memberikan contoh ilustratif PES non-cembung patologis?
Jadi saya tidak ingin berdebat dengan kutipan di atas. Sebaliknya, saya merasa bahwa saya kehilangan sesuatu di sini. Mungkin konteksnya.
sumber
Jawaban:
Kesalahpahaman terletak pada apa yang merupakan "pemecahan" masalah optimasi, misalnya . Untuk ahli matematika, masalahnya hanya dianggap "terpecahkan" begitu kita memiliki:argminf(x)
Ketika adalah cembung, kedua bahan tersebut mudah didapat. Gradient descent menempatkan solusi kandidat x ⋆ yang membuat gradien menghilang ∇ f ( x ⋆ ) = 0 . Bukti optimalitas mengikuti dari fakta sederhana yang diajarkan dalam MATH101 bahwa, jika f adalah cembung, dan gradiennya ∇ f menghilang pada x ⋆ , maka x ⋆f x⋆ ∇ f( x⋆) = 0 f ∇ f x⋆ x⋆ adalah solusi global.
Ketika adalah nonconvex, solusi kandidat mungkin masih mudah ditemukan, tetapi bukti optimalitas menjadi sangat sulit. Sebagai contoh, kita dapat menjalankan gradient descent dan menemukan titik ∇ f ( x ⋆ ) = 0 . Tetapi ketika f adalah nonconvex, kondisi ∇ f ( x ) = 0 diperlukan tetapi tidak lagi cukup untuk optimalitas global. Memang, itu bahkan tidak cukup untuk optimalitas lokal , yaitu kita bahkan tidak dapat menjamin bahwa x ⋆f ∇ f( x⋆) = 0 f ∇ f( x ) = 0 x⋆ adalah minimum lokal berdasarkan pada informasi gradiennya saja. Salah satu pendekatan adalah untuk menghitung semua poin yang memenuhi , dan ini bisa menjadi tugas yang berat bahkan lebih dari satu atau dua dimensi saja.∇ f( x ) = 0
Ketika ahli matematika mengatakan bahwa sebagian besar masalah tidak mungkin diselesaikan, mereka benar-benar mengatakan bahwa bukti optimalitas (bahkan lokal) tidak mungkin dibangun . Tetapi di dunia nyata, kita sering hanya tertarik untuk menghitung solusi "cukup baik", dan ini dapat ditemukan dalam banyak cara. Untuk banyak masalah yang sangat non-konveks, intuisi kita memberi tahu kita bahwa solusi "cukup-baik" sebenarnya optimal secara global, bahkan jika kita sama sekali tidak dapat membuktikannya!
sumber
Contoh masalah dimensi rendah yang rumit dapat berupa:
Mengingat Anda menekan minimum lokal, bagaimana Anda bisa yakin itu mendekati sebaik global minimum? Bagaimana Anda tahu jika hasil Anda adalah solusi optimal yang unik, mengingat itu adalah optimal secara global? Bagaimana Anda bisa membuat algoritma yang kuat untuk semua bukit dan lembah sehingga tidak terjebak di suatu tempat?
Contoh seperti ini adalah di mana segala sesuatunya menjadi sulit. Jelas, tidak semua masalah seperti ini, tetapi beberapa ada. Yang lebih buruk adalah, dalam pengaturan dalam industri, fungsi biaya mungkin memakan waktu untuk menghitung DAN memiliki permukaan yang bermasalah seperti yang di atas.
Contoh Masalah Nyata
Contoh yang bisa saya tangani di tempat kerja adalah melakukan optimasi untuk algoritma panduan rudal yang bisa kuat di banyak kondisi peluncuran. Dengan menggunakan cluster kami, saya bisa mendapatkan pengukuran kinerja yang saya butuhkan dalam waktu sekitar 10 menit untuk satu kondisi. Sekarang untuk menilai ketahanan secara memadai, kami ingin setidaknya beberapa contoh kondisi untuk dihakimi. Jadi katakanlah kita menjalankan enam kondisi, membuat evaluasi fungsi biaya ini memakan waktu satu jam.
Dinamika rudal nonlinear, dinamika atmosfer, proses waktu diskrit, dll menghasilkan reaksi nonlinier yang cukup terhadap perubahan dalam algoritma panduan, membuat optimasi sulit untuk diselesaikan. Fakta bahwa fungsi biaya ini menjadi non-cembung membuat fakta bahwa memakan waktu untuk mengevaluasi masalah besar. Contoh seperti ini adalah di mana kita akan berusaha untuk mendapatkan yang terbaik yang kita bisa pada saat kita diberikan.
sumber
Masalahnya adalah poin sadel, yang dibahas di pos yang Anda tautkan. Dari abstrak salah satu artikel yang ditautkan :
Pada dasarnya Anda dapat memiliki fungsi di mana Anda memiliki titik pelana yang tidak dapat dibedakan dari minima lokal ketika melihat turunan 1, 2 dan 3. Anda dapat menyelesaikan ini dengan membuka pengoptimal pesanan yang lebih tinggi, tetapi mereka menunjukkan bahwa menemukan minimum lokal urutan ke-4 adalah NP sulit.
Anda bisa menggunakan sejumlah heuristik untuk menghindari poin-poin seperti itu, yang mungkin bekerja untuk banyak (kebanyakan?) Contoh dunia nyata, tetapi tidak dapat dibuktikan untuk selalu bekerja.
Dalam posting blog yang Anda tautkan mereka juga membahas kondisi di mana Anda dapat melarikan diri dari poin pelana seperti itu dalam waktu polinomial.
sumber