Kebingungan tentang aturan Armijo

13

Saya bingung tentang aturan Armijo yang digunakan dalam pencarian baris. Saya membaca kembali pencarian garis pelacakan tetapi tidak mendapatkan apa aturan Armijo ini semua tentang. Adakah yang bisa menguraikan aturan Armijo? Wikipedia tampaknya tidak menjelaskan dengan baik. Terima kasih

pengguna34790
sumber
Bagaimana jika dalam persamaan variabel x bukan vektor tetapi sebuah matriks? Bagaimana seharusnya aturan Armijo diperbarui?
Frank Puk
tidak ada yang berubah. Anda hanya harus membentuk kembali Anda Xk -matrix menjadi vektor (kolom) xk .
GoHokies
Di situlah saya terjebak. Ketika menjadi matriks, nilai di sisi kiri ( f ( x k + α p k ) ) masih skalar. Tetapi nilai di sisi kanan tidak - sebagai gantinya, ini adalah matriks ( f ( x k )xkf(xk+αpk)f(xk) adalah skalar dan adalah sebuah matriks.)βαf(xk)Tpk
Frank Puk
Anda harus bekerja dengan vektor, bukan matriks. sehingga Anda membentuk kembali matriks variabel kontrol (saya sudah dilambangkan dengan X k ) menjadi vektor x k dengan N 2 elemen. Arah pencarian dan gradien juga akan menjadi vektor denganelemen N 2 . dengan cara ini baik RHS dan LHS dari kondisi Armijo adalah skalar dan dapat dibandingkan. N×NXkxkN2N2
GoHokies

Jawaban:

19

Setelah Anda mendapatkan arah penurunan untuk fungsi tujuan Anda f ( x ) , Anda harus memilih panjang langkah "baik". Anda tidak ingin mengambil langkah yang terlalu besar sehingga fungsi pada titik baru Anda lebih besar dari titik Anda saat ini. Pada saat yang sama, Anda tidak ingin membuat langkah Anda terlalu kecil sehingga perlu waktu lama untuk bisa bertemu.pf(x)

Kondisi Armijo pada dasarnya menunjukkan bahwa panjang langkah "baik" adalah sedemikian rupa sehingga Anda memiliki "penurunan yang cukup" pada pada titik baru Anda. Kondisi ini secara matematis dinyatakan sebagai f ( x k + α p k ) f ( x k ) + β α f ( x k )f mana p k adalah arah keturunan di x k dan ß ( 0 , 1 ) .

f(xk+αpk)f(xk)+βαf(xk)Tpk
pkxkβ(0,1)

Intuisi di balik ini adalah bahwa nilai fungsi pada titik baru harus di bawahberkurang"garis singgung" di x k ke arah p k . Lihat buku Nocedal & Wright "Numerical Optimization". Dalam Bab 3, ada deskripsi grafis yang sangat baik tentang kondisi penurunan armijo yang cukup.f(xk+αpk)xkpk

Paul
sumber
1
Daripada menganggapnya sebagai garis singgung Anda juga bisa menganggapnya sebagai ekspansi Taylor urutan pertama. Dalam hal ini β hanya memastikan bahwa ukuran langkah ada. α
cjordan1
Alasan mengapa ini penting sama sekali, yaitu mengapa langkah "baik" diperlukan, adalah bahwa banyak skema optimasi akan menyatu lebih lambat, seperti yang dikatakan Paul, atau mungkin tidak sama sekali. Jadi pencarian garis - yang datang dalam beberapa varietas, Armijo adalah yang paling populer - dapat digunakan untuk memberikan algoritma sifat konvergensi yang lebih kuat.
cjordan1
1
Paul: penjelasan Anda tidak lengkap. Ketimpangan ini saja tidak menjamin penurunan 'cukup'. Bahkan, Anda dapat memiliki alpha = 0, dan masih memenuhi ketidaksetaraan yang Anda tulis. Fitur penting adalah aturan Armijo adalah untuk mengikat ukuran langkah menjauh dari nol, yang dilakukan oleh ketidaksetaraan lain: f (gamma * x_new) -f (x_old)> beta * (gamma * x_new-x_old) ^ T * grad (f (x_old))
f(x)=x2xk=1pk=2αf(xk+αpk)α=1/2β>1/2f(xk+1/2pk)=0>12β=f(xk)+βαf(xk)pkβ
Joris Bierkens
β>1/2β=104β
0

Lima tahun kemudian, pertanyaan ini masih berlaku.

Di sini (halaman 16 dan 17) Anda dapat menemukan penjelasan yang bagus, termasuk Algoritma.

Bojan Hrnkas
sumber