Saya mengajar kelas survei analisis numerik dan mencari motivasi untuk metode BFGS untuk siswa dengan latar belakang / intuisi terbatas dalam optimasi!
Meskipun saya tidak punya waktu untuk membuktikan dengan ketat bahwa semuanya menyatu, saya mencari untuk memberikan motivasi yang masuk akal mengapa pembaruan BFGS Hessian mungkin muncul. Sebagai analogi, metode pencarian-akar Broyden (artikel saya ada di sini ) dapat dimotivasi dengan meminta perkiraan Anda tentang Jacobian meminimalkan perbedaan dengan subjek Jacobian lama dengan batasan yang memperhitungkan garis potong terbaru: J_k (\ vec x_k- \ vec x_ {k-1}) = f (\ vec x_k) -f (\ vec x_ {k-1 }) . J k ( → x k - → x k - 1 ) = f ( → x k ) - f ( → x k - 1 )
Turunnya pembaruan BFGS tampaknya jauh lebih terlibat dan suram! Secara khusus, saya ingin tidak menganggap apriori bahwa pembaruan harus peringkat-2 atau mengambil bentuk tertentu. Apakah ada motivasi pendek yang mencari variasi untuk pembaruan BFGS Hessian seperti untuk Broyden?
sumber
Jawaban:
Derivasi BFGS lebih intuitif ketika seseorang menganggap (secara ketat) fungsional biaya cembung:
Namun, beberapa informasi latar belakang diperlukan: Asumsikan, seseorang ingin meminimalkan fungsional cembung Katakanlah ada solusi perkiraan . Kemudian, kita mendekati minimum dengan minimum ekspansi Taylor yang terpotong Artinya, orang mencari sehingga minimal dan set . Komputasi gradien dari - "sehubungan dengan " - dan pengaturannya ke nol memberikan hubungan x k f f ( x k + p ) ≈ f ( x k ) + ∇ f ( x k ) T p + 1
Karena perhitungan dan inversi Hessian mahal ...
... jawaban singkat
(lih. Pembaruan Broyden) mungkin karena pembaruan BFGS meminimalkan dalam norma Frobenius tertimbang yang dipilih secara cerdas, tunduk pada ‖ H - 1 k - H - 1 ‖ WH- 1k + 1
Maka pilihan bobot dalamW ∥ H∥W: = ∥ W1 / 2HW1 / 2∥F
G : = ∫10H( xk+ τp ) dτ αk= 1
sebagai kebalikan dariGoni rata-rata , lih. di sini untuk pernyataan tetapi tanpa bukti, berikan rumus pembaruan BFGS (dengan ).Poin utamanya adalah:
Sebuah jawaban yang lebih panjang , harus mencakup bagaimana memilih bobot, bagaimana membuat karya ini untuk masalah nonconvex (di mana kondisi kelengkungan muncul yang memerlukan skala dari arah pencarian ), dan bagaimana untuk menurunkan sebenarnya rumus untuk update. Referensi ada di sini (dalam bahasa Jerman).hal
sumber