Metode stāvākais nobrauciens(angļu literatūrā “method of steepest descent”) ir iteratīva skaitliska metode (pirmās kārtas) optimizācijas uzdevumu risināšanai, kas ļauj noteikt mērķa funkcijas ekstrēmu (minimumu vai maksimumu):
ir funkcijas argumenta vērtības (kontrolētie parametri) reālajā domēnā.
Saskaņā ar aplūkojamo metodi mērķa funkcijas ekstrēmu (maksimumu vai minimumu) nosaka funkcijas ātrākā pieauguma (samazinājuma) virzienā, t.i. funkcijas gradienta (pretgradienta) virzienā. Gradienta funkcija punktā ir vektors, kura projekcijas uz koordinātu asīm ir funkcijas daļējie atvasinājumi attiecībā pret koordinātām:
kur i, j,…, n ir vienību vektori, kas ir paralēli koordinātu asīm.
Gradients bāzes punktā 
ir stingri ortogonāls pret virsmu, un tā virziens parāda ātrākā funkcijas pieauguma virzienu, un pretējais virziens (antigradients) attiecīgi parāda funkcijas ātrākās samazināšanās virzienu.
Stāvākā nolaišanās metode ir tālākai attīstībai gradienta nolaišanās metode. IN vispārējs gadījums Funkcijas ekstrēma atrašanas process ir iteratīva procedūra, kas tiek uzrakstīta šādi:
kur "+" zīmi izmanto, lai atrastu funkcijas maksimumu, un "-" zīmi izmanto, lai atrastu funkcijas minimumu;
Vienības virziena vektors, ko nosaka pēc formulas:
- gradienta modulis nosaka funkcijas pieauguma vai samazināšanās ātrumu gradienta vai antigradienta virzienā:
Konstante, kas nosaka soļa lielumu un ir vienāda visiem i-tajiem virzieniem.
Soļa lielumu izvēlas no mērķfunkcijas f(x) minimuma nosacījuma kustības virzienā, t.i., viendimensionālās optimizācijas problēmas risināšanas rezultātā gradienta jeb antigradienta virzienā:
Citiem vārdiem sakot, soļa lielumu nosaka, atrisinot šo vienādojumu:
Tādējādi aprēķina solis ir izvēlēts tāds, lai kustība tiktu veikta, līdz funkcija uzlabojas, tādējādi kādā brīdī sasniedzot ekstremitāti. Šajā brīdī atkal tiek noteikts meklēšanas virziens (izmantojot gradientu) un tiek meklēts jauns mērķa funkcijas optimālais punkts utt. Tādējādi šajā metodē meklēšana notiek lielākos soļos, un funkcijas gradients tiek aprēķināts mazākā punktu skaitā.
Divu mainīgo funkcijas gadījumā šī metode ir šāda ģeometriskā interpretācija: kustības virziens no punkta pieskaras līmeņa līnijai punktā . Nolaišanās trajektorija ir zigzagveida, un blakus esošās zigzaga saites ir ortogonālas viena pret otru. Nosacījumu nolaišanās virzienu vektoru ortogonalitātei blakus punktos raksta ar šādu izteiksmi:
Kustības trajektorija līdz galējam punktam, izmantojot stāvākās nolaišanās metodi, kas parādīta funkcijas f(x) vienāda līmeņa līnijas grafikā
Optimālā risinājuma meklēšana beidzas, kad iteratīvā aprēķina posmā (vairāki kritēriji):
Meklēšanas trajektorija paliek nelielā pašreizējā meklēšanas punkta apkārtnē:
Mērķa funkcijas pieaugums nemainās:
Mērķa funkcijas gradients lokālajā minimālajā punktā kļūst par nulli:
Jāatzīmē, ka gradienta nolaišanās metode, pārvietojoties pa gravu, izrādās ļoti lēna, un, palielinoties mainīgo skaitam mērķa funkcijā, šī metodes uzvedība kļūst tipiska. Grava ir ieplaka, kuras līmeņu līnijas ir aptuveni elipses ar daudzkārt atšķirīgām pusasīm. Gravas klātbūtnē nolaišanās trajektorija izpaužas kā zigzaga līnija ar nelielu soli, kā rezultātā iegūtais nolaišanās ātrums līdz minimumam tiek ievērojami palēnināts. Tas izskaidrojams ar to, ka šo funkciju antigradienta virziens ievērojami novirzās no virziena uz minimālo punktu, kas rada papildu aizkavēšanos aprēķinā. Tā rezultātā algoritms zaudē skaitļošanas efektivitāti.
Caurules funkcija
Gradienta metode kopā ar tās daudzajām modifikācijām ir plaši izplatīta un efektīva metode pētāmo objektu optimālā meklēšana. Gradienta meklēšanas (kā arī iepriekš apskatīto metožu) trūkums ir tāds, ka, to izmantojot, var noteikt tikai funkcijas lokālo ekstrēmu. Lai atrastu citus vietējās galējības jāmeklē no citiem sākuma punktiem. Arī gradientu metožu konverģences ātrums būtiski ir atkarīgs arī no gradientu aprēķinu precizitātes. Precizitātes zudums, kas parasti rodas minimālo punktu tuvumā vai notekcaurules situācijā, parasti var traucēt gradienta nolaišanās procesa konverģenci.
Aprēķina metode
1. darbība: Analītisku izteiksmju definīcija (simboliskā formā) funkcijas gradienta aprēķināšanai
2. darbība: iestatiet sākotnējo tuvinājumu
3. darbība: Tiek noteikta nepieciešamība restartēt algoritmisko procedūru, lai atiestatītu pēdējo meklēšanas virzienu. Restartēšanas rezultātā meklēšana atkal tiek veikta ātrākā nolaišanās virzienā.
Varat arī meklēt nevis labāko punktu gradienta virzienā, bet kādu labāku par pašreizējo.
Visvieglāk īstenojamā no visām vietējām optimizācijas metodēm. Ir diezgan vāji apstākļi konverģence, bet konverģences ātrums ir diezgan zems (lineārs). Solis gradienta metode bieži izmanto kā daļu no citām optimizācijas metodēm, piemēram, Flečera-Rīvesa metodi.
Apraksts [ | ]
Uzlabojumi[ | ]
Gradienta nolaišanās metode, pārvietojoties pa gravu, izrādās ļoti lēna, un, palielinoties mainīgo skaitam mērķa funkcijā, šī metodes uzvedība kļūst tipiska. Lai cīnītos pret šo parādību, tas tiek izmantots, kura būtība ir ļoti vienkārša. Veicot divus gradienta nolaišanās soļus un iegūstot trīs punktus, trešais solis jāsper vektora virzienā, kas savieno pirmo un trešo punktu, gar gravas dibenu.
Funkcijām, kas ir tuvu kvadrātiskām, konjugētā gradienta metode ir efektīva.
Pielietojums mākslīgajos neironu tīklos[ | ]
Gradienta nolaišanās metode ar dažām modifikācijām tiek plaši izmantota perceptronu apmācībai, un mākslīgo neironu tīklu teorijā tā ir pazīstama kā backpropagation metode. Apmācot perceptrona tipa neironu tīklu, ir jāmaina tīkla svēršanas koeficienti, lai samazinātu vidējā kļūda neironu tīkla izejā, kad ievadei tiek piegādāta apmācības ievades datu secība. Formāli, lai veiktu tikai vienu soli, izmantojot gradienta nolaišanās metodi (veikt tikai vienu tīkla parametru izmaiņu), tīkla ievadei ir nepieciešams secīgi iesniegt absolūti visu apmācības datu kopu, aprēķināt kļūdu katram objektam. apmācību datus un aprēķināt nepieciešamo tīkla koeficientu korekciju (bet neveikt šo korekciju), un pēc visu datu iesniegšanas aprēķināt summu katra tīkla koeficienta korekcijā (gradientu summa) un labot koeficientus "viens solis" . Acīmredzot ar lielu apmācības datu kopu algoritms darbosies ārkārtīgi lēni, tāpēc praksē tīkla koeficienti bieži tiek koriģēti pēc katra apmācības elementa, kur gradienta vērtība tiek tuvināta ar izmaksu funkcijas gradientu, kas aprēķināts tikai vienā treniņā. elements. Šo metodi sauc stohastiskā gradienta nolaišanās vai operatīvā gradienta nolaišanās . Stohastiskā gradienta nolaišanās ir stohastiskās tuvināšanas veids. Stohastisko aproksimāciju teorija nodrošina nosacījumus stohastiskā gradienta nolaišanās metodes konverģencei.
Saites [ | ]
- J. Mathews. Stāvākā nolaišanās vai gradienta metodes modulis. (saite nav pieejama)
Literatūra [ | ]
- Akuličs I. L. Matemātiskā programmēšana piemēros un uzdevumos. - M.: Augstskola, 1986. - P. 298-310.
- Džils F., Marejs V., Raits M. Praktiskā optimizācija = Praktiskā optimizācija. - M.: Mir, 1985.
- Koršunovs Ju.M., Koršunovs Ju.M. Kibernētikas matemātiskie pamati. - M.: Energoatomizdat, 1972. gads.
- Maksimovs Ju.A., Filipovskaja E.A. Algoritmi nelineārās programmēšanas uzdevumu risināšanai. - M.: MEPhI, 1982. gads.
- Maksimovs Ju.A. Algoritmi lineārai un diskrētai programmēšanai. - M.: MEPhI, 1980. gads.
- Korns G., Korns T. Matemātikas rokasgrāmata zinātniekiem un inženieriem. - M.: Nauka, 1970. - P. 575-576.
- S. Ju. Gorodetskis, V. A. Grišagins. Nelineāra programmēšana un multiekstremāla optimizācija. - Ņižņijnovgoroda: Ņižņijnovgorodas universitātes izdevniecība, 2007. - 357.-363.lpp.
Noteikumi funkcijas ievadīšanai
IN stāvākā nolaišanās metode par meklēšanas virzienu tiek izvēlēts vektors, kura virziens ir pretējs funkcijas ▽f(x) gradienta vektora virzienam. No matemātiskā analīze zināms, ka vektors grad f(x)=▽f(x) raksturo funkcijas ātrākā pieauguma virzienu (sk. funkcijas gradientu). Tāpēc tiek izsaukts vektors - grad f (X) = -▽f(X). pretgradients un ir tā straujākā samazinājuma virziens. Atkārtošanās sakarībai, ar kuru tiek realizēta stāvākā nolaišanās metode, ir forma X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
kur λ k > 0 ir soļa izmērs. Atkarībā no pakāpiena izmēra izvēles jūs varat iegūt dažādas iespējas gradienta metode. Ja optimizācijas procesā tiek fiksēts soļa lielums λ, tad metodi sauc par gradienta metodi ar diskrētu soli. Optimizācijas procesu pirmajās iterācijās var ievērojami paātrināt, ja λ k ir izvēlēts no nosacījuma λ k =min f(X k + λS k) .
Lai noteiktu λ k, tiek izmantota jebkura viendimensijas optimizācijas metode. Šajā gadījumā metodi sauc par stāvākās nolaišanās metodi. Parasti, lai sasniegtu funkcijas minimumu, parasti ar vienu soli nepietiek, process tiek atkārtots, līdz nākamie aprēķini uzlabo rezultātu.
Ja telpa dažos mainīgajos ir ļoti iegarena, tad veidojas “grava”. Meklēšana var palēnināties un virzīties zigzagā pāri “gravas” apakšai. Dažreiz risinājumu nevar iegūt pieņemamā laika posmā.
Vēl viens metodes trūkums var būt apturēšanas kritērijs ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Piemērs. Sākot no punkta x k =(-2, 3), nosakiet punktu x k +1, izmantojot stāvākās nolaišanās metodi, lai samazinātu funkciju.
Kā meklēšanas virzienu atlasiet gradienta vektoru pašreizējā punktā 
Pārbaudīsim apstāšanās kritēriju. Mums ir 
Aprēķināsim funkcijas vērtību sākuma punktā f(X 1) = 35. Darīsim
soli pa antigradienta virzienu
Aprēķināsim funkcijas vērtību jaunā punktā
f(X 2) = 3 (-2 + 19 λ 1) 2 + (3-8 λ 1) 2 - (-2 + 19 λ 1) (3-8 λ 1) - 4 (-2 + 19 λ 1)
Atradīsim tādu soli, lai mērķa funkcija šajā virzienā sasniegtu minimumu. No nepieciešamā nosacījuma funkcijas ekstrēma pastāvēšanai
f’(X 2) = 6 (-2 + 19λ 1) 19 + 2 (3-8λ 1) (-8) - (73 - 304 λ 1) - 4*19
vai f’(X 2) = 2598 λ 1 – 425 = 0.
Mēs iegūstam soli λ 1 = 0,164
Šīs darbības pabeigšana novedīs pie lietas 
kurā gradienta vērtība 
, funkcijas vērtība f(X 2) = 0,23. Precizitāte netiek sasniegta, no punkta mēs speram soli pa antigradienta virzienu.
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
Mēs iegūstam λ 1 = 0,52 
Anotācija: Šī lekcija plaši aptver tādas daudzparametru optimizācijas metodes kā stāvākā nolaišanās metode un Davidona–Flečera–Pauela metode. Papildus tiek veikta augstāk minēto metožu salīdzinošā analīze, lai noteiktu efektīvāko, identificētas to priekšrocības un trūkumi; un arī aplūko daudzdimensiju optimizācijas problēmas, piemēram, gravu metodi un daudzekstrēmālo metodi.
1. Stāvākā nolaišanās metode
Šīs metodes būtība ir tāda, ka, izmantojot iepriekš minēto koordinātu nolaišanās metode tiek veikta meklēšana no dotā punkta virzienā, kas ir paralēls vienai no asīm, līdz minimālajam punktam šajā virzienā. Pēc tam meklēšanu veic virzienā, kas ir paralēls otrai asij utt. Norādes, protams, ir fiksētas. Šķiet saprātīgi mēģināt modificēt šo metodi tā, lai katrā posmā minimālā punkta meklēšana tiktu veikta "labākajā" virzienā. Nav skaidrs, kurš virziens ir "labākais", taču tas ir zināms gradienta virziens ir funkcijas ātrākā pieauguma virziens. Tāpēc pretējais virziens ir funkcijas ātrākās samazināšanās virziens. Šo īpašumu var attaisnot šādi.
Pieņemsim, ka mēs virzāmies no punkta x uz nākamo punktu x + hd, kur d ir noteikts virziens un h ir noteikta garuma solis. Līdz ar to kustība tiek veikta no punkta (x 1, x 2, ..., x n) uz punktu (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Kur
Funkciju vērtību izmaiņas nosaka attiecības
| (1.3) |
Līdz pirmās kārtas zx i , daļējos atvasinājumus aprēķina punktā x . Kā jāizvēlas virzieni d i, kas apmierina (1.2) vienādojumu, lai iegūtu lielāko funkcijas df izmaiņu vērtību? Šeit rodas maksimizācijas problēma ar ierobežojumu. Pielietosim Lagranža reizinātāju metodi, ar kuras palīdzību nosakām funkciju
Vērtība df atbilst ierobežojuma (1.2) sasniedz maksimumu, kad funkcija
Sasniedz maksimumu. Tā atvasinājums
Tāpēc
 |
(1.6) |
Tad di ~ df/dx i un virziens d ir paralēls virzienam V/(x) punktā x.
Tādējādi lielākais vietējais pieaugums funkcija noteiktam mazam solim h notiek, ja d ir Vf(x) vai g(x) virziens. Tāpēc stāvākās nolaišanās virziens ir virziens
Vienkāršākā formā vienādojumu (1.3) var uzrakstīt šādi:
Kur ir leņķis starp vektoriem Vf(x) un dx. Dotajai dx vērtībai mēs samazinām df, izvēloties, ka dx virziens sakrīt ar virzienu -Vf(x) .
komentēt. Gradienta virziens perpendikulāri jebkuram nemainīga līmeņa līnijas punktam, jo šajā taisnē funkcija ir nemainīga. Tādējādi, ja (d 1, d 2, ..., d n) ir mazs solis pa līmeņa līniju, tad
Un tāpēc
 |
(1.8) |
