Ikhtisar metode gradien dalam masalah optimisasi matematis

Kata Pengantar

Artikel ini akan fokus pada metode untuk memecahkan masalah optimasi matematis berdasarkan penggunaan gradien fungsi. Tujuan utamanya adalah untuk mengumpulkan dalam artikel semua ide paling penting yang terkait dengan metode ini dan berbagai modifikasinya.





UPD Dalam komentar mereka menulis bahwa pada beberapa browser dan formula aplikasi seluler tidak ditampilkan. Sayangnya, saya tidak tahu bagaimana menghadapinya. Saya hanya bisa mengatakan bahwa saya menggunakan makro "inline" dan "display" dari editor Habrava. Jika Anda tiba-tiba tahu cara memperbaikinya - silakan tulis di komentar.

Catatan dari penulis

Pada saat penulisan, saya membela disertasi, tugas yang mengharuskan saya untuk memiliki pemahaman yang mendalam tentang metode teoritis pada dasarnya optimasi matematika. Namun demikian, mata saya (dari orang lain) masih kabur dari rumus panjang yang menakutkan, jadi saya menghabiskan banyak waktu untuk mengisolasi ide-ide kunci yang akan menandai variasi metode gradien yang berbeda. Tujuan pribadi saya adalah menulis artikel yang berisi jumlah minimum informasi yang diperlukan untuk pemahaman topik yang kurang lebih terperinci. Tetapi bersiaplah, bagaimanapun juga, seseorang tidak dapat melakukannya tanpa formula.

Pernyataan masalah

Sebelum menjelaskan metode, Anda harus terlebih dahulu menggambarkan masalahnya, yaitu: "Diberikan banyak $$$\ mathcal {K}$ dan fungsi $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ perlu menemukan titik $$$x ^ * \ dalam \ mathcal {K}$ sedemikian rupa $$$f (x) \ geq f (x ^ *)$ untuk semua $$$x \ in \ mathcal {K}$ ", Yang biasanya ditulis seperti ini

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}.$$

Secara teori , biasanya diasumsikan demikian $$$f$ Merupakan fungsi yang dapat dibedakan dan cembung, dan $$$\ mathcal {K}$ - set cembung (dan bahkan lebih baik, jika sama sekali $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), ini memungkinkan kami untuk memberikan jaminan keberhasilan penerapan gradient descent. Dalam praktiknya, gradient descent berhasil diterapkan bahkan ketika tugas tidak memiliki salah satu properti di atas (contoh nanti dalam artikel).

Sedikit matematika

Misalkan untuk saat ini kita hanya perlu mencari fungsi minimum satu dimensi

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}.$$

Kembali pada abad ke-17, Pierre Fermat datang dengan kriteria yang memungkinkan untuk menyelesaikan masalah optimasi sederhana, yaitu, jika $$$x ^ *$ - titik minimum $$$f ^ *$ lalu

$$

$$f '(x ^ *) = 0$$

dimana $$$f '$ - turunan $$$f$ . Kriteria ini didasarkan pada pendekatan linier.

$$

$$f (x) \ kira-kira f (x ^ *) + f '(x ^ *) (x-x ^ *).$$

Lebih dekat $$$x$ untuk $$$x ^ *$ , semakin akurat perkiraan ini. Di sisi kanan adalah ekspresi itu, kapan $$$f '(x ^ *) \ neq 0$ mungkin lebih suka $$$f (x ^ *)$ less adalah esensi utama dari kriteria. Dalam kasus multidimensi, serupa dari pendekatan linier $$$f (x) \ approx f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (selanjutnya $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - produk skalar standar, bentuk penulisan ini disebabkan oleh fakta bahwa produk skalar sama dengan produk matriks dari vektor baris oleh vektor kolom), kriteria diperoleh

$$

$$\ nabla f (x ^ *) = 0.$$

Nilai $$$\ nabla f (x ^ *)$ - gradien fungsi $$$f$ pada intinya $$$x ^ *$ . Juga, kesetaraan gradien ke nol berarti kesetaraan semua turunan parsial menjadi nol, oleh karena itu, dalam kasus multidimensi, orang dapat memperoleh kriteria ini hanya dengan menerapkan kriteria satu dimensi untuk setiap variabel secara terpisah.

Perlu dicatat bahwa kondisi ini diperlukan, tetapi tidak cukup, contoh paling sederhana adalah 0 untuk $$$f (x) = x ^ 2$ dan $$$f (x) = x ^ 3$


Kriteria ini cukup dalam kasus fungsi cembung, sebagian besar karena hal ini dimungkinkan untuk mendapatkan begitu banyak hasil untuk fungsi cembung.

Fungsi kuadratik

Fungsi kuadratik dalam $$$\ mathbb {R} ^ n$ Merupakan fungsi dari bentuk

$$

$$f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$$

Untuk menghemat ruang (dan lebih sedikit repot dengan indeks), fungsi ini biasanya ditulis dalam bentuk matriks:

$$

$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c,$$

dimana $$$x = (x_1, \ ldots, x_n) ^ T$ , $$$b = (b_1, \ ldots, b_n) ^ T$ , $$$A$ Adalah matriks di mana di persimpangan $$$i$ string dan $$$j$ kolom adalah nilainya
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$A$ ternyata simetris - ini penting). Selanjutnya ketika menyebutkan fungsi kuadrat, saya akan memiliki fungsi di atas.

Mengapa saya berbicara tentang ini? Faktanya adalah bahwa fungsi kuadrat penting dalam optimasi karena dua alasan:

1. Mereka juga terjadi dalam praktek, misalnya, ketika membangun regresi linear-kuadrat terkecil
2. Gradien fungsi kuadrat adalah fungsi linier, khususnya untuk fungsi di atas
   

   $$

   $$\ frac {\ partial} {\ partial x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i,$$
   
   Atau dalam bentuk matriks
   

   $$

   $$\ nabla f (x) = Ax-b,$$
   
   Demikian sistemnya $$$\ nabla f (x) = 0$ - sistem linear. Tidak ada sistem yang lebih sederhana daripada linear. Pikiran yang saya coba sampaikan adalah optimalisasi fungsi kuadrat - kelas paling sederhana dari masalah optimasi . Di sisi lain, fakta itu $$$\ nabla f (x ^ *) = 0$ - kondisi minimum yang diperlukan memungkinkan untuk menyelesaikan sistem linear melalui masalah optimisasi. Beberapa saat kemudian saya akan mencoba meyakinkan Anda bahwa ini masuk akal.
   

Properti Gradien Berguna

Nah, kita tampaknya telah menemukan bahwa jika suatu fungsi dapat dibedakan (memiliki turunan terhadap semua variabel), maka pada titik minimum gradien harus sama dengan nol. Tetapi apakah gradien membawa informasi yang berguna ketika tidak nol?

Mari kita coba memecahkan masalah yang lebih sederhana: intinya diberikan $$$x$ menemukan titik $$$\ bar {x}$ sedemikian rupa $$$f (\ bar {x}) <f (x)$ . Mari kita ambil satu poin di sebelah $$$x$ lagi menggunakan pendekatan linier $$$f (\ bar {x}) \ kira-kira f (x) + \ nabla f (x) ^ T (\ bar {x} -x)$ . Jika kamu ambil $$$\ bar {x} = x- \ alpha \ nabla f (x)$ , $$$\ alpha> 0$ lalu kita dapatkan

$$

$$f (\ bar {x}) \ approx f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x).$$

Begitu pula jika $$$\ alpha <0$ lalu $$$f (\ bar {x})$ akan lebih $$$f (x)$ (selanjutnya $$$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~$ ) Sekali lagi, karena kami menggunakan perkiraan, pertimbangan ini hanya berlaku untuk kecil $$$\ alpha$ . Untuk meringkas di atas, jika $$$\ nabla f (x) \ neq 0$ , maka gradien menunjukkan arah peningkatan fungsi lokal terbesar .

Berikut adalah dua contoh untuk fungsi dua dimensi. Gambar-gambar semacam ini sering dapat dilihat dalam demonstrasi gradient descent. Garis berwarna adalah garis level yang disebut, ini adalah satu set titik di mana fungsi mengambil nilai tetap, dalam kasus saya ini adalah lingkaran dan elips. Saya menandai garis biru level dengan nilai yang lebih rendah, merah - dengan yang lebih tinggi.



Perhatikan bahwa untuk permukaan ditentukan oleh persamaan bentuk $$$f (x) = c$ , $$$\ nabla f (x)$ menetapkan normal (pada orang umum - tegak lurus) ke permukaan ini. Perhatikan juga bahwa meskipun gradien menunjukkan arah peningkatan terbesar pada fungsi, tidak ada jaminan bahwa dalam arah yang berlawanan dengan gradien, Anda dapat menemukan minimum (misalnya, gambar kiri).

Keturunan gradien

Hanya ada langkah kecil yang tersisa untuk metode penurunan gradien dasar: kami belajar dari titik tersebut $$$x$ mendapatkan poin $$$\ bar {x}$ dengan nilai fungsi yang lebih rendah $$$f$ . Apa yang mencegah kita mengulangi ini beberapa kali? Sebenarnya, ini adalah gradient descent: kita membangun urutannya

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k).$$

Nilai $$$\ alpha_k$ disebut ukuran langkah (dalam pembelajaran mesin - kecepatan belajar ). Beberapa kata tentang pilihan $$$\ alpha_k$ : jika $$$\ alpha_k$ - sangat kecil, urutannya berubah secara perlahan, yang membuat algoritma tidak terlalu efisien; jika $$$\ alpha_k$ sangat besar, maka pendekatan linier menjadi buruk, dan bahkan mungkin salah. Dalam praktiknya, ukuran langkah sering dipilih secara empiris, dalam teori, gradien Lipschitz biasanya diasumsikan, yaitu, jika

$$

$$\ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | x-y \ |$$

untuk semua $$$x, y$ lalu $$$\ alpha_k <\ frac {2} {L}$ jaminan berkurang $$$f (x_k)$ .

Analisis untuk fungsi kuadratik

Jika $$$A$ Adalah matriks yang dapat dibalik simetris, $$$Axe ^ * = b$ kemudian untuk fungsi kuadratik $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ titik $$$x ^ *$ adalah titik minimum ( UPD . asalkan minimum ini ada sama sekali - $$$f$ tidak mendekati $$$- \ infty$ nilai hanya jika $$$A$ positif pasti), dan untuk metode gradient descent kita dapat memperoleh yang berikut ini

$$

$$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$$

$$

$$(x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_k A) (x_k-x ^ *),$$

dimana $$$I$ Apakah matriks identitas, mis. $$$Ix = x$ untuk semua $$$x$ . Jika $$$\ alpha_k \ equiv \ alpha$ itu akan berubah

$$

$$\ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |.$$

Ekspresi di sebelah kiri adalah jarak dari perkiraan yang diperoleh dalam langkah $$$k$ gradient descent ke titik minimum, di sebelah kanan - ekspresi dari form $$$\ lambda ^ k \ beta$ yang konvergen ke nol jika $$$| \ lambda | <1$ (kondisi yang saya tulis $$$\ alpha$ dalam paragraf sebelumnya, inilah yang menjamin). Estimasi dasar ini memastikan bahwa gradient descent menyatu.

Modifikasi Keturunan Gradien

Sekarang saya ingin berbicara sedikit tentang modifikasi gradient descent yang umum digunakan, terutama yang disebut

Metode gradien inersia atau dipercepat

Semua metode dari kelas ini dinyatakan sebagai berikut

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}).$$

Istilah terakhir mencirikan "inersia" yang sama ini, algoritma pada setiap langkah mencoba untuk bergerak melawan gradien, tetapi pada saat yang sama ia bergerak sebagian oleh inersia dalam arah yang sama seperti pada iterasi sebelumnya. Metode tersebut memiliki dua sifat penting:

1. Mereka praktis tidak menyulitkan gradient descent dalam rencana komputasi.
2. Dengan seleksi yang cermat $$$\ alpha_k, \ beta_k$ metode seperti itu adalah urutan besarnya lebih cepat dari penurunan gradien biasa bahkan dengan langkah yang dipilih secara optimal.

Salah satu metode pertama muncul di pertengahan abad ke-20 dan disebut metode bola berat , yang menyampaikan sifat inersia metode: dalam metode ini $$$\ alpha_k, \ beta_k$ independen dari $$$k$ dan dipilih dengan cermat tergantung pada fungsi tujuan. Perlu dicatat $$$\ alpha_k$ mungkin apa pun kecuali $$$\ beta_k$ - Biasanya hanya sedikit kurang dari satu .

Metode bola berat adalah metode inersia paling sederhana, tetapi bukan yang pertama. Dalam hal ini, menurut saya, metode pertama sangat penting untuk memahami esensi dari metode ini.

Metode Chebyshev

Ya, ya, metode pertama jenis ini ditemukan oleh Chebyshev untuk menyelesaikan sistem persamaan linear. Pada beberapa titik dalam analisis gradient descent, persamaan berikut diperoleh

$$

$$x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots =$$

$$

$$(I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *),$$

dimana $$$P_k$ Apakah beberapa derajat jumlahnya banyak $$$k$ . Mengapa tidak mencoba mengambil $$$\ alpha_k$ jadi itu $$$P_k (A) (x_0-x ^ *)$ apakah itu lebih kecil? Satu simpul polinomial universal yang menyimpang paling sedikit dari nol adalah polinomial Chebyshev. Metode Chebyshev pada dasarnya terdiri dalam memilih parameter keturunan sehingga $$$P_k$ adalah polinomial Chebyshev. Sebenarnya ada satu masalah kecil: untuk keturunan gradien normal, ini sama sekali tidak mungkin. Namun, untuk metode inersia, ini dimungkinkan. Hal ini terutama disebabkan oleh fakta bahwa polinomial Chebyshev memuaskan relasi pengulangan orde kedua

$$

$$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x),$$

oleh karena itu, mereka tidak dapat dibangun untuk gradient descent, yang menghitung nilai baru dari hanya satu nilai sebelumnya, dan untuk inersia itu menjadi mungkin karena kenyataan bahwa dua nilai sebelumnya digunakan. Ternyata kompleksitas perhitungannya $$$\ alpha_k, \ beta_k$ tidak bergantung pada $$$k$ atau ukuran ruang $$$n$ .

Metode Gradien Konjugasi

Fakta lain yang sangat menarik dan penting (konsekuensi dari teorema Hamilton-Cayley): untuk setiap matriks persegi $$$A$ ukurannya $$$n \ kali n$ ada polinomial $$$P$ gelar tidak lebih $$$n$ untuk itu $$$P (A) = 0$ . Mengapa ini menarik? Ini semua tentang kesetaraan yang sama

$$

$$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *).$$

Jika kita bisa memilih ukuran langkah dalam gradient descent sedemikian rupa untuk mendapatkan polinomial zeroing ini, maka gradient descent akan konvergen untuk angka iterasi tetap yang tidak lebih besar dari dimensi $$$A$ . Seperti yang sudah kita ketahui, kita tidak bisa melakukan ini untuk gradient descent. Untungnya, untuk metode inersia, kita bisa. Deskripsi dan pembenaran metode ini cukup teknis, saya akan membatasi diri pada esensi: pada setiap iterasi, parameter dipilih yang memberikan polinomial terbaik, yang dapat dibangun dengan mempertimbangkan semua pengukuran yang dilakukan sebelum langkah pengukuran gradien saat ini . Pada saat bersamaan

1. Satu iterasi penurunan gradien (tanpa memperhitungkan perhitungan parameter akun) berisi satu perkalian matriks dengan vektor dan 2-3 penambahan vektor
2. Perhitungan parameter juga membutuhkan 1-2 perkalian matriks dengan vektor, 2-3 perkalian vektor skalar dengan vektor, dan beberapa penambahan vektor.

Yang paling sulit dalam hal perhitungan adalah perkalian Matriks dengan vektor, biasanya ini dilakukan dalam waktu $$$\ mathcal {O} (n ^ 2)$ Namun, untuk implementasi khusus, ini dapat dilakukan di $$$\ mathcal {O} (m)$ dimana $$$m$ - jumlah elemen bukan nol di $$$A$ . Mengingat konvergensi metode gradien konjugat, tidak lebih dari $$$n$ iterasi mendapatkan kompleksitas algoritma secara keseluruhan $$$\ mathcal {O} (nm)$ , yang dalam semua kasus tidak lebih buruk $$$\ mathcal {O} (n ^ 3)$ untuk metode Gauss atau Cholesky, tetapi jauh lebih baik jika $$$m << n ^ 2$ itu tidak begitu langka.

Metode gradien konjugasi juga berfungsi dengan baik jika $$$f$ bukan fungsi kuadrat, tetapi tidak menyatu dalam jumlah langkah yang terbatas dan sering membutuhkan modifikasi tambahan kecil

Metode Nesterov

Untuk komunitas optimisasi matematis dan pembelajaran mesin, nama "Nesterov" telah lama menjadi nama rumah tangga. Di tahun 80-an abad terakhir, Yu.E. Nesterov datang dengan versi yang menarik dari metode inersia, yang memiliki bentuk

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}),$$

itu tidak menyiratkan perhitungan yang rumit $$$\ alpha_k, \ beta_k$ seperti dalam metode gradien konjugat, secara umum, perilaku metode ini mirip dengan metode bola berat, tetapi konvergensinya biasanya jauh lebih dapat diandalkan baik secara teori maupun dalam praktik.

Penurunan gradien stokastik

Satu-satunya perbedaan formal dari gradient descent adalah penggunaan fungsi alih-alih gradien $$$g (x, \ theta)$ sedemikian rupa $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ theta$ - harapan acak $$$\ theta$ ), sehingga keturunan gradien stokastik memiliki bentuk

$$

$$x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k).$$

$$$\ theta_k$ - Ini adalah beberapa parameter acak yang tidak kita pengaruhi, tetapi pada saat yang sama rata-rata kita melawan gradien. Sebagai contoh, perhatikan fungsinya

$$

$$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2, ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j)$$

dan

$$

$$g (x, i) = x-y_i.$$

Jika $$$i$ mengambil nilai $$$1, \ ldots, m$ sama rata-rata hanya rata-rata $$$g$ Merupakan gradien $$$f$ . Contoh ini juga menunjukkan hal berikut: kompleksitas menghitung gradien dalam $$$m$ kali lebih banyak dari kompleksitas komputasi $$$g$ . Ini memungkinkan penurunan gradien stokastik dilakukan pada saat yang sama di $$$m$ kali lebih banyak iterasi. Terlepas dari kenyataan bahwa penurunan gradien stokastik biasanya menyatu lebih lambat dari biasanya, karena peningkatan besar dalam jumlah iterasi, dimungkinkan untuk meningkatkan tingkat konvergensi per satuan waktu. Sejauh yang saya tahu, saat ini penurunan gradien stokastik adalah metode dasar untuk melatih sebagian besar jaringan saraf, diimplementasikan di semua perpustakaan ML utama: tensorflow, obor, caffe, CNTK, dll.

Perlu dicatat bahwa ide-ide metode inersia digunakan untuk penurunan gradien stokastik dan dalam praktik sering memberikan peningkatan, dalam teori, biasanya diasumsikan bahwa laju konvergensi asimptotik tidak berubah karena fakta bahwa kesalahan utama dalam penurunan gradien stokastik disebabkan oleh dispersi. $$$g$ .

Keturunan sub-gradien

Variasi ini memungkinkan Anda untuk bekerja dengan fungsi yang tidak dapat dibedakan, saya akan menjelaskannya secara lebih rinci. Kita lagi-lagi harus mengingat pendekatan linier - faktanya adalah bahwa ada karakteristik sederhana dari konveksitas melalui gradien, fungsi terdiferensiasi $$$f$ cembung jika dan hanya jika $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ untuk semua $$$x, y$ . Ternyata fungsi cembung tidak harus dapat dibedakan, tetapi untuk setiap titik $$$x$ tentu saja ada vektor seperti itu $$$g$ itu $$$f (y) \ geq f (x) + g ^ T (y-x)$ untuk semua $$$y$ . Vektor seperti itu $$$g$ biasa disebut subgradien $$$f$ pada intinya $$$x$ , himpunan semua subgradien ke poin $$$x$ disebut subdifferential $$$x$ dan menunjukkan $$$\ partial f (x)$ (terlepas dari penunjukannya - tidak ada hubungannya dengan turunan parsial). Dalam kasus satu dimensi $$$g$ Merupakan angka, dan properti di atas berarti grafik $$$f$ terletak di atas garis yang melewati $$$(x, f (x))$ dan memiliki kemiringan $$$g$ (lihat gambar di bawah). Saya perhatikan bahwa mungkin ada beberapa subgradien untuk satu poin, bahkan jumlah yang tak terbatas.



Biasanya tidak terlalu sulit untuk menghitung setidaknya satu subgradien untuk suatu titik, keturunan subgradien pada dasarnya menggunakan subgradien alih-alih gradien. Ternyata ini sudah cukup, dalam teori, tingkat konvergensi menurun, namun, misalnya, dalam jaringan saraf fungsi yang tidak dapat dibedakan. $$$ReLU (x) = \ maks (0, x)$ mereka suka menggunakannya hanya karena pelatihan lebih cepat dengan itu (ini, omong-omong, contoh fungsi non-cembung non-dibedakan di mana (sub) gradien keturunan berhasil diterapkan. Fungsi itu sendiri $$$Relu$ jaringan saraf cembung tapi berlapis-lapis berisi $$$Relu$ , tidak cembung dan tidak dapat dibedakan). Sebagai contoh, untuk suatu fungsi $$$f (x) = | x |$ subdifferential dihitung dengan sangat sederhana

$$

$$\ partial f (x) = \ begin {cases} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0. \ end {cases}$$

Mungkin hal penting terakhir yang perlu diketahui adalah bahwa keturunan sub-gradien tidak bertemu pada ukuran langkah yang konstan . Ini paling mudah dilihat untuk fungsi di atas. $$$f (x) = | x |$ . Bahkan tidak adanya turunan pada satu titik mematahkan konvergensi:

1. Katakanlah kita mulai dari titik $$$x_0$ .
2. Langkah penurunan sub-gradien:
   

   $$

   $$x_ {k + 1} = \ begin {cases} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0. \ end {cases}$$
3. Jika $$$x_0> 0$ maka beberapa langkah pertama kita akan mengurangi satu, jika $$$x_0 <0$ lalu tambahkan. Dengan satu atau lain cara, kita akan menemukan diri kita dalam interval $$$[0, 1)$ dari mana kita sampai $$$[- 1, 0)$ , dan kemudian kita akan melompat di antara dua titik interval ini.

Secara teori, untuk keturunan sub-gradien, disarankan untuk mengambil urutan langkah-langkah

$$

$$\ alpha_k = \ frac {1} {(k + 1) ^ c}.$$

Dimana $$$c$ biasanya $$$1$ atau $$$\ frac {1} {2}$ . Dalam latihan, saya sering melihat langkah-langkah sukses $$$\ alpha_k = e ^ {- ck}$ , meskipun untuk langkah-langkah tersebut secara umum tidak akan ada konvergensi.

Metode proksimal

Sayangnya, saya tidak tahu terjemahan yang bagus untuk “proximal” dalam konteks optimasi, itu sebabnya saya hanya akan memanggil metode ini. Metode proksimal muncul sebagai generalisasi metode gradien proyektif. Idenya sangat sederhana: jika ada fungsi $$$f$ direpresentasikan sebagai jumlah $$$f (x) = \ varphi (x) + h (x)$ dimana $$$\ varphi$ Merupakan fungsi cembung yang dapat dibedakan, dan $$$h (x)$ - cembung, di mana ada operator proksimal khusus $$$prox_h (x)$ (dalam artikel ini saya akan membatasi diri hanya untuk contoh, saya tidak akan menjelaskan secara umum), maka sifat konvergensi dari gradient descent untuk $$$\ varphi$ tetap dan untuk gradient descent untuk $$$f$ jika setelah setiap iterasi berlaku operator proksimal ini untuk titik saat ini $$$x_k$ , dengan kata lain, bentuk umum dari metode proksimal terlihat seperti ini:

$$

$$x_ {k + 1} = prox _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k))$$

Saya pikir sejauh ini benar-benar tidak dapat dipahami mengapa ini mungkin diperlukan, terutama mengingat bahwa saya tidak menjelaskan apa itu operator proksimal. Berikut ini dua contoh:

1. $$$h (x)$ - Fungsi indikator dari set cembung $$$\ mathcal {K}$ itu adalah
   

   $$

   $$h (x) = \ begin {cases} 0, & x \ in \ mathcal {K}, \\ + infty, & x \ notin \ mathcal {K}. \\ \ end {cases}$$
   
   Dalam hal ini $$$prox _ {\ alpha_kh} (x)$ Adalah proyeksi ke set $$$\ mathcal {K}$ , yaitu, "paling dekat dengan $$$x$ titik setel $$$\ mathcal {K}$ ". Jadi, kita membatasi gradient descent hanya pada set $$$\ mathcal {K}$ , yang memungkinkan kami untuk menyelesaikan masalah dengan pembatasan. Sayangnya, menghitung proyeksi dalam kasus umum dapat menjadi lebih sulit, jadi metode ini biasanya digunakan jika batasannya sederhana, misalnya, yang disebut kendala kotak: untuk setiap koordinat
   

   $$

   $$l_i \ leq x_i \ leq r_i$$
   
   
2. $$$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ - $$$\ ell_1$ -regulasi. Mereka suka menambahkan istilah ini ke masalah optimisasi dalam pembelajaran mesin untuk menghindari pelatihan ulang. Regulasi seperti ini juga cenderung membatalkan komponen yang paling tidak signifikan. Untuk fungsi seperti itu, operator proksimal memiliki bentuk (ekspresi untuk koordinat tunggal dijelaskan di bawah):
   

   $$

   $$[prox _ {\ alpha h} (x)] _ i = \ begin {cases} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, & x_i <- \ alpha, \\ 0, & x_i \ dalam [- \ alpha, \ alpha], \ end {cases}$$
   
   yang cukup mudah untuk dihitung.

Kesimpulan

Ini mengakhiri variasi utama dari metode gradien yang saya kenal. Mungkin pada akhirnya saya akan mencatat bahwa semua modifikasi ini (kecuali mungkin metode gradien konjugasi) dapat dengan mudah berinteraksi satu sama lain. Saya sengaja tidak memasukkan metode Newton dan metode kuasi-Newton (BFGS dan lainnya) dalam daftar ini: meskipun mereka menggunakan gradien, mereka adalah metode yang lebih kompleks dan memerlukan perhitungan tambahan spesifik, yang biasanya lebih mahal secara komputasi daripada menghitung gradien. Namun demikian, jika teks ini diminati, saya akan dengan senang hati melakukan peninjauan serupa pada mereka.

Literatur yang digunakan / direkomendasikan

Boyd. S, Vandenberghe L. Optimasi Cembung
Shewchuk JR Pengantar Metode Gradient Konjugat Tanpa Rasa Sakit yang Menyedihkan
Teori Optimasi Cembung Bertsekas DP

Nesterov Yu. E. Metode optimasi cembung
Gasnikov A.V. Keturunan gradien universal