Kaedah keturunan paling curam(dalam kesusasteraan Inggeris "kaedah keturunan paling curam") ialah kaedah berangka berulang (perintah pertama) untuk menyelesaikan masalah pengoptimuman, yang membolehkan anda menentukan ekstrem (minimum atau maksimum) fungsi objektif:
ialah nilai argumen fungsi (parameter terkawal) pada domain sebenar.
Selaras dengan kaedah yang sedang dipertimbangkan, ekstrem (maksimum atau minimum) fungsi objektif ditentukan dalam arah peningkatan (penurunan) fungsi terpantas, i.e. dalam arah kecerunan (anti-gradient) fungsi. Fungsi kecerunan pada satu titik ialah vektor yang unjurannya pada paksi koordinat ialah terbitan separa bagi fungsi berkenaan dengan koordinat:
dengan i, j,…, n ialah vektor unit selari dengan paksi koordinat.
Kecerunan pada titik asas 
adalah ortogonal ke permukaan, dan arahnya menunjukkan arah peningkatan terpantas dalam fungsi, dan arah bertentangan (antigradient), masing-masing, menunjukkan arah penurunan terpantas fungsi.
Kaedah turun yang paling curam ialah perkembangan selanjutnya kaedah penurunan kecerunan. DALAM kes am Proses mencari extremum fungsi ialah prosedur berulang, yang ditulis seperti berikut:
di mana tanda "+" digunakan untuk mencari maksimum fungsi, dan tanda "-" digunakan untuk mencari minimum fungsi;
Vektor arah unit, yang ditentukan oleh formula:
- modul kecerunan menentukan kadar peningkatan atau penurunan fungsi ke arah kecerunan atau anti-kecerunan:
Pemalar yang menentukan saiz langkah dan adalah sama untuk semua arah ke-i.
Saiz langkah dipilih daripada keadaan minimum fungsi objektif f(x) dalam arah pergerakan, iaitu, sebagai hasil daripada menyelesaikan masalah pengoptimuman satu dimensi dalam arah kecerunan atau antikecerunan:
Dengan kata lain, saiz langkah ditentukan dengan menyelesaikan persamaan ini:
Oleh itu, langkah pengiraan dipilih supaya pergerakan dijalankan sehingga fungsi bertambah baik, sekali gus mencapai ekstrem pada satu ketika. Pada ketika ini, arah carian ditentukan sekali lagi (menggunakan kecerunan) dan titik optimum baharu bagi fungsi objektif dicari, dsb. Oleh itu, dalam kaedah ini, carian berlaku dalam langkah yang lebih besar, dan kecerunan fungsi dikira pada bilangan mata yang lebih kecil.
Dalam kes fungsi dua pembolehubah kaedah ini mempunyai tafsiran geometri berikut: arah pergerakan dari satu titik menyentuh garis aras pada titik . Lintasan penurunan adalah zigzag, dengan pautan zigzag bersebelahan ortogon antara satu sama lain. Syarat untuk keortogonan vektor arah keturunan pada titik jiran ditulis dengan ungkapan berikut:
Trajektori pergerakan ke titik ekstrem menggunakan kaedah penurunan paling curam, ditunjukkan pada graf garis tahap yang sama bagi fungsi f(x)
Pencarian untuk penyelesaian optimum berakhir apabila pada langkah pengiraan berulang (beberapa kriteria):
Trajektori carian kekal dalam kejiranan kecil titik carian semasa:
Kenaikan fungsi objektif tidak berubah:
Kecerunan fungsi objektif pada titik minimum tempatan menjadi sifar:
Perlu diingatkan bahawa kaedah penurunan kecerunan ternyata sangat perlahan apabila bergerak di sepanjang jurang, dan apabila bilangan pembolehubah dalam fungsi objektif meningkat, tingkah laku kaedah ini menjadi tipikal. Jurang ialah lekukan, garis aras yang kira-kira mempunyai bentuk elips dengan separa paksi berbeza berkali-kali ganda. Di hadapan jurang, trajektori penurunan mengambil bentuk garis zigzag dengan langkah kecil, akibatnya kelajuan menurun yang terhasil ke tahap minimum sangat diperlahankan. Ini dijelaskan oleh fakta bahawa arah antigradien fungsi-fungsi ini menyimpang dengan ketara dari arah ke titik minimum, yang membawa kepada kelewatan tambahan dalam pengiraan. Akibatnya, algoritma kehilangan kecekapan pengiraan.
Fungsi Gully
Kaedah kecerunan, bersama-sama dengan banyak pengubahsuaiannya, adalah meluas dan kaedah yang berkesan mencari objek yang dikaji secara optimum. Kelemahan carian kecerunan (serta kaedah yang dibincangkan di atas) ialah apabila menggunakannya, hanya ekstrem tempatan fungsi boleh dikesan. Untuk mencari orang lain ekstrem tempatan adalah perlu untuk mencari dari titik permulaan yang lain. Selain itu, kelajuan penumpuan kaedah kecerunan juga sangat bergantung pada ketepatan pengiraan kecerunan. Kehilangan ketepatan, yang biasanya berlaku di sekitar titik minimum atau dalam keadaan jurang, secara amnya boleh mengganggu penumpuan proses penurunan kecerunan.
Kaedah pengiraan
Langkah 1: Takrif ungkapan analitikal (dalam bentuk simbolik) untuk mengira kecerunan fungsi
Langkah 2: Tetapkan anggaran awal
Langkah 3: Keperluan untuk memulakan semula prosedur algoritma untuk menetapkan semula arah carian terakhir ditentukan. Hasil daripada permulaan semula, carian dijalankan semula ke arah penurunan terpantas.
Anda juga boleh mencari bukan untuk titik terbaik dalam arah kecerunan, tetapi untuk beberapa titik yang lebih baik daripada titik semasa.
Yang paling mudah untuk dilaksanakan daripada semua kaedah pengoptimuman tempatan. Mempunyai cukup keadaan lemah penumpuan, tetapi kadar penumpuan agak rendah (linear). Langkah kaedah kecerunan sering digunakan sebagai sebahagian daripada kaedah pengoptimuman lain, seperti kaedah Fletcher–Reeves.
Penerangan [ | ]
Penambahbaikan[ | ]
Kaedah penurunan kecerunan ternyata sangat perlahan apabila bergerak di sepanjang jurang, dan apabila bilangan pembolehubah dalam fungsi objektif bertambah, tingkah laku kaedah ini menjadi tipikal. Untuk memerangi fenomena ini, ia digunakan, intipatinya sangat mudah. Setelah membuat dua langkah penurunan kecerunan dan memperoleh tiga mata, langkah ketiga harus diambil ke arah vektor yang menghubungkan titik pertama dan ketiga, di sepanjang bahagian bawah jurang.
Untuk fungsi yang hampir dengan kuadratik, kaedah kecerunan konjugat adalah berkesan.
Aplikasi dalam rangkaian saraf tiruan[ | ]
Kaedah penurunan kecerunan, dengan beberapa pengubahsuaian, digunakan secara meluas untuk latihan perceptron dan dikenali dalam teori rangkaian saraf tiruan sebagai kaedah perambatan belakang. Apabila melatih rangkaian neural jenis perceptron, adalah perlu untuk menukar pekali pemberat rangkaian untuk meminimumkan ralat purata pada output rangkaian saraf apabila urutan data input latihan dibekalkan kepada input. Secara rasmi, untuk mengambil hanya satu langkah menggunakan kaedah turunan kecerunan (buat hanya satu perubahan dalam parameter rangkaian), adalah perlu untuk menyerahkan secara berurutan keseluruhan set data latihan ke input rangkaian, mengira ralat untuk setiap objek data latihan dan mengira pembetulan yang diperlukan bagi pekali rangkaian (tetapi tidak melakukan pembetulan ini), dan selepas menyerahkan semua data, hitung jumlah dalam pembetulan setiap pekali rangkaian (jumlah kecerunan) dan betulkan pekali "satu langkah" . Jelas sekali, dengan set data latihan yang besar, algoritma akan berfungsi dengan sangat perlahan, jadi dalam amalan, pekali rangkaian sering diselaraskan selepas setiap elemen latihan, di mana nilai kecerunan dianggarkan oleh kecerunan fungsi kos, dikira pada hanya satu latihan unsur. Kaedah ini dipanggil penurunan kecerunan stokastik atau penurunan kecerunan operasi . Penurunan kecerunan stokastik ialah satu bentuk penghampiran stokastik. Teori penghampiran stokastik menyediakan syarat untuk penumpuan kaedah penurunan kecerunan stokastik.
Pautan [ | ]
- J. Mathews. Modul untuk Kaedah Keturunan atau Kecerunan Tercuram. (pautan tidak tersedia)
kesusasteraan [ | ]
- Akulich I. L. Pengaturcaraan matematik dalam contoh dan masalah. - M.: Sekolah Tinggi, 1986. - P. 298-310.
- Gill F., Murray W., Wright M. Pengoptimuman praktikal = Pengoptimuman Praktikal. - M.: Mir, 1985.
- Korshunov Yu M., Korshunov M. Asas matematik sibernetik. - M.: Energoatomizdat, 1972.
- Maksimov Yu A., Fillipovskaya E. A. Algoritma untuk menyelesaikan masalah pengaturcaraan tak linear. - M.: MEPhI, 1982.
- Maksimov Yu. Algoritma untuk pengaturcaraan linear dan diskret. - M.: MEPhI, 1980.
- Korn G., Korn T. Buku panduan matematik untuk saintis dan jurutera. - M.: Nauka, 1970. - P. 575-576.
- S. Yu. Gorodetsky, V. A. Grishagin. Pengaturcaraan bukan linear dan pengoptimuman multiextremal. - Nizhny Novgorod: Rumah Penerbitan Universiti Nizhny Novgorod, 2007. - ms 357-363.
Peraturan untuk memasukkan fungsi
DALAM kaedah turun paling curam vektor yang arahnya bertentangan dengan arah vektor kecerunan fungsi ▽f(x) dipilih sebagai arah carian. daripada analisis matematik diketahui bahawa grad vektor f(x)=▽f(x) mencirikan arah peningkatan terpantas dalam fungsi (lihat kecerunan fungsi). Oleh itu, vektor - grad f (X) = -▽f(X) dipanggil anti kecerunan dan merupakan arah penurunan terpantasnya. Hubungan berulang yang kaedah turun paling curam dilaksanakan mempunyai bentuk X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
di mana λ k >0 ialah saiz langkah. Bergantung pada pilihan saiz langkah, anda boleh dapatkan pelbagai pilihan kaedah kecerunan. Jika semasa proses pengoptimuman saiz langkah λ ditetapkan, maka kaedah itu dipanggil kaedah kecerunan dengan langkah diskret. Proses pengoptimuman dalam lelaran pertama boleh dipercepatkan dengan ketara jika λ k dipilih daripada keadaan λ k =min f(X k + λS k) .
Untuk menentukan λ k, sebarang kaedah pengoptimuman satu dimensi digunakan. Dalam kes ini, kaedah itu dipanggil kaedah penurunan paling curam. Sebagai peraturan, dalam kes umum, satu langkah tidak mencukupi untuk mencapai minimum fungsi; proses itu diulang sehingga pengiraan seterusnya meningkatkan hasilnya.
Sekiranya ruang sangat memanjang dalam beberapa pembolehubah, maka "jurang" terbentuk. Pencarian mungkin perlahan dan berzigzag merentasi bahagian bawah "garam". Kadangkala penyelesaian tidak boleh diperolehi dalam jangka masa yang boleh diterima.
Satu lagi kelemahan kaedah ini mungkin kriteria berhenti ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Contoh. Bermula dari titik x k =(-2, 3), tentukan titik x k +1 menggunakan kaedah penurunan paling curam untuk meminimumkan fungsi.
Sebagai arah carian, pilih vektor kecerunan pada titik semasa 
Mari kita semak kriteria berhenti. Kami ada 
Mari kita hitung nilai fungsi pada titik awal f(X 1) = 35. Mari kita lakukan
melangkah mengikut arah antigradien
Mari kita hitung nilai fungsi pada titik baharu
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Mari kita cari satu langkah supaya fungsi objektif mencapai minimum sepanjang arah ini. Daripada syarat yang diperlukan untuk kewujudan ekstrem fungsi
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
atau f’(X 2) = 2598 λ 1 – 425 = 0.
Kami mendapat langkah λ 1 = 0.164
Melengkapkan langkah ini akan membawa kepada intipati 
di mana nilai kecerunan 
, nilai fungsi f(X 2) = 0.23. Ketepatan tidak dicapai, dari titik kita mengambil langkah di sepanjang arah antigradient.
f(X 2) = 3(1.116 – 1.008λ 1) 2 + (1.688-2.26λ 1) 2 - (1.116 – 1.008λ 1)(1.688-2.26λ 1) - 4(1.116 – 1.0)
f’(X 2) = 11.76 – 6.12λ 1 = 0
Kami mendapat λ 1 = 0.52 
Anotasi: Kuliah ini merangkumi secara meluas kaedah pengoptimuman berbilang parameter seperti kaedah turunan paling curam dan kaedah Davidon–Fletcher–Powell. Di samping itu, analisis perbandingan kaedah di atas dijalankan untuk menentukan yang paling berkesan, kelebihan dan kekurangannya dikenal pasti; dan juga mempertimbangkan masalah pengoptimuman berbilang dimensi, seperti kaedah jurang dan kaedah berbilang ekstrem.
1. Kaedah turunan paling curam
Intipati kaedah ini ialah menggunakan yang disebutkan sebelumnya kaedah penurunan koordinat carian dijalankan dari titik tertentu dalam arah yang selari dengan salah satu paksi ke titik minimum dalam arah ini. Pencarian kemudiannya dilakukan dalam arah yang selari dengan paksi lain, dan seterusnya. Arahannya, sudah tentu, tetap. Nampaknya munasabah untuk cuba mengubah suai kaedah ini supaya pada setiap peringkat pencarian untuk titik minimum dijalankan mengikut arah "terbaik". Tidak jelas arah mana yang "terbaik", tetapi diketahui bahawa arah kecerunan ialah arah peningkatan terpantas dalam fungsi. Oleh itu, arah yang bertentangan ialah arah penurunan terpantas fungsi. Harta ini boleh dibenarkan seperti berikut.
Mari kita andaikan bahawa kita sedang bergerak dari titik x ke titik seterusnya x + hd, di mana d ialah arah tertentu dan h ialah langkah dengan panjang tertentu. Akibatnya, pergerakan dibuat dari titik (x 1, x 2, ..., x n) ke titik (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Di mana
Perubahan dalam nilai fungsi ditentukan oleh hubungan
| (1.3) |
Sehingga tertib pertama zx i , dengan derivatif separa dikira pada titik x . Bagaimanakah arah d i harus dipilih yang memenuhi persamaan (1.2) untuk mendapatkan nilai terbesar bagi perubahan dalam fungsi df? Di sinilah masalah memaksimumkan dengan kekangan timbul. Marilah kita menggunakan kaedah pengganda Lagrange, dengan bantuannya kita menentukan fungsi
Nilai df memuaskan kekangan (1.2) mencapai maksimum apabila fungsi
Mencapai maksimum. Derivatifnya
Oleh itu,
 |
(1.6) |
Kemudian di ~ df/dx i dan arah d adalah selari dengan arah V/(x) pada titik x.
Oleh itu, peningkatan tempatan terbesar fungsi untuk langkah kecil tertentu h berlaku apabila d ialah arah Vf(x) atau g(x) . Oleh itu, arah penurunan yang paling curam adalah arah
Dalam bentuk yang lebih mudah, persamaan (1.3) boleh ditulis seperti berikut:
Di manakah sudut antara vektor Vf(x) dan dx. Untuk nilai dx tertentu, kita meminimumkan df dengan memilih bahawa arah dx bertepatan dengan arah -Vf(x) .
Komen. Arah kecerunan berserenjang dengan mana-mana titik pada garis aras malar, kerana sepanjang garis ini fungsinya adalah malar. Oleh itu, jika (d 1, d 2, ..., d n) ialah langkah kecil di sepanjang garis aras, maka
Dan oleh itu
 |
(1.8) |
