Saya melakukan pencarian garis sebagai bagian dari algoritma BFGS kuasi-Newton. Dalam satu langkah pencarian baris saya menggunakan interpolasi kubik untuk bergerak lebih dekat ke minimizer lokal.
Biarkan menjadi fungsi yang menarik. Saya ingin mencari x ∗ sehingga f ′ ( x ∗ ) ≈ 0 .
Biarkan , f ′ ( x k ) , f ( x k + 1 ) dan f ′ ( x k + 1 ) diketahui. Juga asumsikan 0 ≤ x k < x ∗ < x k + 1 . Saya cocok dengan polinomial Q ( x ) = a x 3 + b x 2 + sehingga Q ( 0 ) = f ( x k ) , Q ′ ( 0 ) = f ′ ( x k ) , Q ( x k + 1 - x k ) = f ( x k + 1 ) dan Q ′ ( X k + 1 - x k ) = .
Aku memecahkan persamaan kuadrat: untuk saya dicari x * menggunakan solusi bentuk tertutup.
Karya-karya di atas baik dalam banyak kasus, kecuali bila sebagai solusi bentuk tertutup untuk ( 1 ) membagi oleh suatu yang menjadi sangat dekat dengan atau tepatnya 0 .
Solusi saya adalah dengan melihat dan jika "terlalu kecil" cukup ambil solusi bentuk tertutup untuk minimizer polinomial kuadrat Q 2 ( x ) = b x 2 + c x + d yang sudah saya miliki koefisiennya b , c , d dari fit sebelumnya ke Q ( x ) .
Pertanyaan saya adalah: Bagaimana cara membuat tes yang baik untuk kapan mengambil interpolasi kuadratik di atas kubik? Pendekatan naif untuk tes untuk adalah karena buruk untuk alasan numerik jadi saya sedang melihat | a | < ϵ τ di mana ϵ adalah presisi mesin, tapi aku tidak dapat memutuskan τ yang baik yang berskala invarian dari f .
Pertanyaan bonus: Apakah ada masalah numerik dengan menggunakan koefisien, , dari kubik yang gagal atau haruskah saya melakukan kuadratik baru dengan cara yang tepat untuk menghitung koefisien?
Edit untuk klarifikasi: Dalam pertanyaan saya sebenarnya adalah apa yang biasa disebut sebagai ϕ ( α ) = f ( ˉ x k + α ¯ p k ) dalam literatur. Saya hanya menyederhanakan rumusan pertanyaan. Masalah optimasi yang saya selesaikan adalah non-linear dalam 6 dimensi. Dan saya sangat menyadari bahwa kondisi Wolfe cukup untuk pencarian garis BFGS karena itu menyatakan bahwa saya tertarik pada f ′ ( x ∗ ) ≈ 0; Saya mencari sesuatu yang akan memuaskan kondisi Wolfe yang kuat dan mengambil minimizer dari pendekatan kubik adalah langkah yang baik di sepanjang jalan.
Pertanyaannya bukan tentang BFGS, melainkan bagaimana menentukan kapan koefisien kubik cukup kecil sehingga perkiraan kuadrat lebih tepat.
Sunting 2: Perbarui notasi, persamaan tidak berubah.
Ada sebuah makalah oleh Moré, yang diimplementasikan oleh Nocedal, tentang itu:
sumber