Prehľad gradientových metód v úlohách matematickej optimalizácie. gradientové metódy

gradientové metódy

Gradientové neobmedzené optimalizačné metódy využívajú len prvé derivácie cieľovej funkcie a sú lineárnymi aproximačnými metódami v každom kroku, t.j. účelová funkcia v každom kroku je nahradená dotykovou nadrovinou k jej grafu v aktuálnom bode.

V k-tom štádiu gradientových metód je prechod z bodu Xk do bodu Xk+1 opísaný vzťahom:

kde k je veľkosť kroku, k je vektor v smere Xk+1-Xk.

Spôsoby najstrmšieho zostupu

Prvýkrát o takejto metóde uvažoval a aplikoval ju O. Cauchy v 18. storočí. Jeho myšlienka je jednoduchá: gradient účelovej funkcie f(X) v ľubovoľnom bode je vektor v smere najväčšieho nárastu hodnoty funkcie. Preto bude antigradient smerovať k najväčšiemu poklesu funkcie a je to smer najstrmšieho zostupu. Antigradient (a gradient) je kolmý na rovinu f(X) v bode X. Ak v (1.2) zavedieme smer

potom to bude smer najstrmšieho klesania v bode Xk.

Dostaneme prechodový vzorec z Xk na Xk+1:

Antigradient udáva iba smer zostupu, nie veľkosť kroku. Vo všeobecnosti jeden krok nedáva minimálny bod, takže postup zostupu sa musí použiť niekoľkokrát. V minimálnom bode sú všetky zložky gradientu rovné nule.

Všetky gradientové metódy využívajú vyššie uvedenú myšlienku a líšia sa od seba technickými detailmi: výpočet derivácií analytickým vzorcom alebo aproximáciou konečných rozdielov; veľkosť kroku môže byť konštantná, meniť sa podľa nejakých pravidiel, alebo byť zvolená po aplikácii jednorozmerných optimalizačných metód v smere antigradientu atď. a tak ďalej.

Nebudeme sa podrobne zaoberať, pretože. metóda najstrmšieho zostupu sa vo všeobecnosti neodporúča ako seriózna optimalizačná procedúra.

Jednou z nevýhod tejto metódy je, že konverguje k akémukoľvek stacionárnemu bodu, vrátane sedlového bodu, čo nemôže byť riešením.

Najdôležitejšia vec je však veľmi pomalá konvergencia najstrmšieho klesania vo všeobecnosti. Ide o to, že zostup je „najrýchlejší“ v miestnom ponímaní. Ak je vyhľadávací hyperpriestor silne pretiahnutý („roklina“), tak antigradient smeruje takmer ortogonálne na dno „rokliny“, t.j. najlepší smer na dosiahnutie minima. V tomto zmysle priamy preklad anglického výrazu „strmest descent“, t.j. klesanie po najstrmšom svahu viac zodpovedá stavu vecí ako termín „najrýchlejší“ prijatý v ruskojazyčnej odbornej literatúre. Jedným východiskom z tejto situácie je použitie informácií, ktoré poskytujú druhé parciálne deriváty. Ďalším východiskom je zmena mierok premenných.

lineárny aproximačný derivačný gradient

Fletcher-Reevesova metóda konjugovaného gradientu

Metóda konjugovaného gradientu vytvára sekvenciu smerov vyhľadávania, ktoré sú lineárnymi kombináciami aktuálneho smeru najstrmšieho zostupu a predchádzajúcich smerov vyhľadávania, t.j.

a koeficienty sú zvolené tak, aby smery vyhľadávania boli konjugované. Dokázal to

a to je veľmi cenný výsledok, ktorý vám umožňuje vytvoriť rýchly a efektívny optimalizačný algoritmus.

Fletcher-Reevesov algoritmus

1. V X0 sa počíta.

2. V k-tom kroku sa jednorozmerným vyhľadávaním v smere nájde minimum f(X), ktoré určí bod Xk+1.

• 3. Vypočítajte f(Xk+1) a.
• 4. Smer sa určí z pomeru:

• 5. Po (n+1)-tej iterácii (t.j. s k=n) sa vykoná reštart: predpokladá sa X0=Xn+1 a vykoná sa prechod na krok 1.
• 6. Algoritmus sa zastaví, keď

kde je ľubovoľná konštanta.

Výhodou Fletcher-Reevesovho algoritmu je, že nevyžaduje maticovú inverziu a šetrí pamäť počítača, keďže nepotrebuje matice používané v newtonovských metódach, ale zároveň je takmer rovnako efektívny ako kvázi-newtonovské algoritmy. Pretože smery vyhľadávania sú vzájomne konjugované, potom bude kvadratická funkcia minimalizovaná v maximálne n krokoch. Vo všeobecnom prípade sa používa reštart, ktorý vám umožní získať výsledok.

Algoritmus Fletcher-Reeves je citlivý na presnosť jednorozmerného vyhľadávania, takže akékoľvek chyby zaokrúhľovania, ktoré sa môžu vyskytnúť, musia byť pri jeho používaní opravené. Algoritmus môže tiež zlyhať v situáciách, keď sa Hessian stane zle podmieneným. Algoritmus nemá žiadnu záruku konvergencie vždy a všade, hoci prax ukazuje, že algoritmus takmer vždy dáva výsledok.

Newtonovské metódy

Smer hľadania zodpovedajúci najstrmšiemu zostupu je spojený s lineárnou aproximáciou cieľovej funkcie. Metódy využívajúce druhé derivácie vznikli z kvadratickej aproximácie cieľovej funkcie, t.j. pri rozširovaní funkcie v Taylorovom rade sa vypúšťajú členy tretieho a vyššieho rádu.

kde je Hessiánska matica.

Minimum pravej strany (ak existuje) sa dosiahne na rovnakom mieste ako minimum kvadratickej formy. Napíšeme vzorec na určenie smeru hľadania:

Minimum sa dosiahne pri

Optimalizačný algoritmus, v ktorom je smer vyhľadávania určený z tohto vzťahu, sa nazýva Newtonova metóda a smer je Newtonov smer.

V problémoch hľadania minima ľubovoľnej kvadratickej funkcie s kladnou maticou druhých derivácií dáva Newtonova metóda riešenie v jednej iterácii bez ohľadu na výber východiskového bodu.

Klasifikácia newtonovských metód

V skutočnosti Newtonova metóda spočíva v jedinej aplikácii Newtonovho smeru na optimalizáciu kvadratickej funkcie. Ak funkcia nie je kvadratická, potom platí nasledujúca veta.

Veta 1.4. Ak je Hessova matica všeobecnej nelineárnej funkcie f v minimálnom bode X* kladne definitná, počiatočný bod je zvolený dostatočne blízko k X* a dĺžky krokov sú zvolené správne, potom Newtonova metóda konverguje k X* s kvadratická rýchlosť.

Newtonova metóda sa považuje za referenčnú a porovnávajú sa s ňou všetky vyvinuté optimalizačné postupy. Newtonova metóda však pracuje iba s pozitívne definitívnou a dobre podmienenou Hessovou maticou (jej determinant musí byť podstatne väčší ako nula, presnejšie, pomer najväčších a najmenších vlastných hodnôt by sa mal blížiť k jednej). Na odstránenie tohto nedostatku sa používajú modifikované newtonovské metódy využívajúce v rámci možností newtonovské smery a odchyľujúce sa od nich len v prípade potreby.

Všeobecný princíp modifikácií Newtonovej metódy je nasledovný: pri každej iterácii sa najprv zostrojí nejaká pozitívne definitná matica „súvisiaca“ s a potom sa vypočíta podľa vzorca

Vzhľadom k tomu, že je pozitívny definitívne, potom - bude nevyhnutne smer zostupu. Konštrukčný postup je organizovaný tak, že sa zhoduje s Hessovou maticou, ak je pozitívne definitívna. Tieto postupy sú postavené na základe niektorých maticových expanzií.

Ďalšia skupina metód, ktoré sú takmer také rýchle ako Newtonova metóda, je založená na aproximácii Hessovej matice pomocou konečných rozdielov, pretože na optimalizáciu nie je potrebné používať presné hodnoty derivátov. Tieto metódy sú užitočné, keď je analytický výpočet derivátov zložitý alebo jednoducho nemožný. Takéto metódy sa nazývajú diskrétne Newtonove metódy.

Kľúčom k efektivite metód newtonského typu je zohľadnenie informácií o minimalizovanom zakrivení funkcie, ktoré sú obsiahnuté v Hessovej matici a umožňujú zostaviť lokálne presné kvadratické modely cieľovej funkcie. Je však možné zbierať a zhromažďovať informácie o zakrivení funkcie na základe pozorovania zmeny gradientu počas iterácií zostupu.

Zodpovedajúce metódy založené na možnosti aproximácie zakrivenia nelineárnej funkcie bez explicitného vytvorenia jej Hessovej matice sa nazývajú kvázi-newtonské metódy.

Všimnite si, že pri konštrukcii optimalizačného postupu newtonovského typu (vrátane kvázi-newtonského) je potrebné počítať s možnosťou výskytu sedlového bodu. V tomto prípade bude vektor najlepšieho smeru hľadania vždy smerovať k sedlovému bodu, namiesto toho, aby sa od neho vzďaľoval smerom „dole“.

Newton-Raphsonova metóda

Táto metóda spočíva v opakovanom použití Newtonovho smeru pri optimalizácii funkcií, ktoré nie sú kvadratické.

Základný iteračný vzorec pre viacrozmernú optimalizáciu

sa v tejto metóde používa pri výbere smeru optimalizácie zo vzťahu

Skutočná dĺžka kroku je skrytá v nenormalizovanom Newtonovom smere.

Keďže táto metóda nevyžaduje hodnotu cieľovej funkcie v aktuálnom bode, niekedy sa nazýva nepriama alebo analytická optimalizačná metóda. Jeho schopnosť určiť minimum kvadratickej funkcie v jednom výpočte vyzerá na prvý pohľad mimoriadne atraktívne. Tento „jediný výpočet“ je však nákladný. V prvom rade je potrebné vypočítať n parciálnych derivácií prvého rádu a n(n+1)/2 - druhého. Okrem toho musí byť Hessova matica invertovaná. To už vyžaduje približne n3 výpočtových operácií. Pri rovnakých nákladoch môžu metódy konjugovaného smeru alebo metódy konjugovaného gradientu trvať približne n krokov, t.j. dosiahnuť takmer rovnaký výsledok. Iterácia Newton-Raphsonovej metódy teda neposkytuje výhody v prípade kvadratickej funkcie.

Ak funkcia nie je kvadratická, potom

• - počiatočný smer už vo všeobecnosti neudáva skutočný minimálny bod, čo znamená, že iterácie sa musia opakovať opakovane;
• - krok jednotkovej dĺžky môže viesť k bodu s horšou hodnotou účelovej funkcie a hľadanie môže udávať nesprávny smer, ak napríklad Hessian nie je pozitívne definitívna;
• - hesián sa môže zle podmieniť, čím sa znemožní jeho prevrátenie, t.j. určenie smeru pre ďalšiu iteráciu.

Stratégia sama o sebe nerozlišuje, ku ktorému stacionárnemu bodu (minimum, maximu, sedlovému bodu) sa hľadanie blíži a nerobí sa ani výpočet hodnôt objektívnej funkcie, podľa ktorých by bolo možné sledovať, či funkcia rastie. Všetko teda závisí od toho, ktorý stacionárny bod v zóne príťažlivosti je východiskovým bodom hľadania. Stratégia Newton-Raphson sa zriedka používa samostatne bez toho či onakého druhu.

Pearsonove metódy

Pearson navrhol niekoľko metód na aproximáciu inverzného Hessianu bez explicitného výpočtu druhých derivácií, t.j. pozorovaním zmien v smere antigradientu. V tomto prípade sa získajú konjugované smery. Tieto algoritmy sa líšia iba v detailoch. Tu sú tie, ktoré sa najviac používajú v aplikovaných oblastiach.

Pearsonov algoritmus č. 2.

V tomto algoritme je inverzný Hessián aproximovaný maticou Hk vypočítanou v každom kroku pomocou vzorca

Ako počiatočná matica H0 je zvolená ľubovoľná pozitívne definitná symetrická matica.

Tento Pearsonov algoritmus často vedie k situáciám, keď sa matica Hk stane zle podmienená, konkrétne začne oscilovať, osciluje medzi kladne definitívnou a nepozitívnou definitívnou, pričom determinant matice je takmer nulový. Aby sa predišlo tejto situácii, je potrebné znovu nastaviť maticu každých n krokov, čím sa rovná H0.

Pearsonov algoritmus č. 3.

V tomto algoritme je matica Hk+1 určená zo vzorca

Hk+1 = Hk+

Cesta zostupu generovaná algoritmom je podobná správaniu algoritmu Davidon-Fletcher-Powell, ale kroky sú o niečo kratšie. Pearson tiež navrhol variant tohto algoritmu s cyklickým preskupovaním matice.

Projektívny Newton-Raphsonov algoritmus

Pearson navrhol myšlienku algoritmu, v ktorom je matica vypočítaná zo vzťahu

H0=R0, kde matica R0 je rovnaká ako počiatočné matice v predchádzajúcich algoritmoch.

Keď k je násobok počtu nezávislých premenných n, matica Hk sa nahradí maticou Rk+1 vypočítanou ako súčet

Hodnota Hk(f(Xk+1) - f(Xk)) je projekcia vektora gradientu prírastku (f(Xk+1)-f(Xk)), ortogonálna ku všetkým vektorom prírastku gradientu v predchádzajúcich krokoch. Po každých n krokoch je Rk aproximáciou inverznej Hessovej H-1(Xk), takže sa v podstate vykoná (približne) Newtonovo vyhľadávanie.

Davidon-Fletcher-Powell metóda

Táto metóda má iné názvy – metóda variabilnej metriky, kvázi-Newtonova metóda, pretože používa oba tieto prístupy.

Metóda Davidon-Fletcher-Powell (DFP) je založená na použití Newtonovských smerov, ale nevyžaduje výpočet inverzného Hessiana v každom kroku.

Smer vyhľadávania v kroku k je smer

kde Hi je kladne definitívna symetrická matica, ktorá sa aktualizuje v každom kroku a v limite sa rovná inverznej Hessovej. Matica identity sa zvyčajne vyberá ako počiatočná matica H. Iteratívny postup DFT možno znázorniť takto:

• 1. V kroku k je bod Xk a pozitívne definitná matica Hk.
• 2. Zvoľte ako nový smer vyhľadávania

3. Jednorozmerné vyhľadávanie (zvyčajne kubickou interpoláciou) v smere určuje k minimalizujúce funkciu.

4. Spolieha sa.

5. Spolieha sa.

6. Určené a. Ak sú Vk alebo dostatočne malé, postup sa ukončí.

• 7. Nastavte Uk = f(Xk+1) - f(Xk).
• 8. Matica Hk sa aktualizuje podľa vzorca

9. Zvýšte k o jednu a vráťte sa na krok 2.

Metóda je v praxi účinná, ak je chyba výpočtu gradientu malá a matica Hk nie je zle podmienená.

Matica Ak zabezpečuje konvergenciu Hk ku G-1, matica Bk zaisťuje kladnú definitívnosť Hk+1 vo všetkých štádiách a vylučuje H0 v limite.

V prípade kvadratickej funkcie

tie. algoritmus DFP používa združené smery.

Metóda DFT teda využíva myšlienky newtonovského prístupu aj vlastnosti konjugovaných smerov a pri minimalizácii kvadratickej funkcie konverguje najviac v n iteráciách. Ak má optimalizovaná funkcia tvar blízky kvadratickej funkcii, potom je metóda DFP efektívna vďaka dobrej aproximácii G-1 (Newtonova metóda). Ak má účelová funkcia všeobecnú formu, potom je metóda DFP účinná vďaka použitiu konjugovaných smerov.

Metódy gradientovej optimalizácie

Problémy optimalizácie s nelineárnymi alebo ťažko vypočítateľnými vzťahmi, ktoré určujú optimalizačné kritérium a obmedzenia, sú predmetom nelineárneho programovania. Riešenia problémov nelineárneho programovania možno spravidla nájsť len numerickými metódami s využitím výpočtovej techniky. Spomedzi nich sa najčastejšie používajú gradientové metódy (metódy relaxácie, gradient, najstrmší klesanie a stúpanie), negradientové deterministické metódy vyhľadávania (metódy skenovania, simplex a pod.) a metódy náhodného vyhľadávania. Všetky tieto metódy sa používajú pri numerickom stanovení optima a sú široko pokryté v odbornej literatúre.

Vo všeobecnom prípade hodnota optimalizačného kritéria R možno vnímať ako funkciu R(x b xx..., x n), definované v n-rozmernom priestore. Keďže neexistuje žiadne vizuálne grafické znázornenie n-rozmerného priestoru, použijeme prípad dvojrozmerného priestoru.

Ak R(l x 2) v regióne nepretržite D, potom okolo optimálneho bodu M°(xi°, x z°) v tejto rovine je možné nakresliť uzavretú čiaru, pozdĺž ktorej je hodnota R= konšt. Existuje veľa takýchto čiar, nazývaných čiary rovnakej úrovne, ktoré možno nakresliť okolo optimálneho bodu (v závislosti od kroku

Medzi metódami používanými na riešenie problémov nelineárneho programovania zaujímajú významné miesto metódy hľadania riešení založené na analýze derivácie vzhľadom na smer optimalizovanej funkcie. Ak v každom bode priestoru skalárna funkcia viacerých premenných nadobudne presne definované hodnoty, tak v tomto prípade máme do činenia so skalárnym poľom (teplotné pole, tlakové pole, hustotné pole atď.). Obdobným spôsobom sa definuje vektorové pole (pole síl, rýchlostí atď.). Izotermy, izobary, izochróny atď. - to všetko sú čiary (plochy) rovnakých úrovní, rovnakých hodnôt funkcie (teplota, tlak, objem atď.). Pretože sa hodnota funkcie mení z bodu do bodu v priestore, je potrebné určiť rýchlosť zmeny funkcie v priestore, to znamená deriváciu v smere.

Koncept gradientu je široko používaný v inžinierskych výpočtoch na nájdenie extrémov nelineárnych funkcií. Gradientové metódy sú numerické metódy typu vyhľadávania. Sú univerzálne a obzvlášť účinné v prípadoch hľadania extrémov nelineárnych funkcií s obmedzeniami, ako aj vtedy, keď je analytická funkcia úplne neznáma. Podstatou týchto metód je určiť hodnoty premenných, ktoré poskytujú extrém cieľovej funkcie, pohybom pozdĺž gradientu (pri hľadaní max) alebo v opačnom smere (min). Rôzne gradientové metódy sa navzájom líšia v spôsobe, akým sa určuje pohyb smerom k optimu. Pointa je, že ak sú čiary na rovnakej úrovni R(xu x i) graficky charakterizujte závislosť R(x\jc?), potom je možné hľadať optimálny bod rôznymi spôsobmi. Napríklad nakreslite mriežku na rovine x\, xr s uvedením hodnôt R pri uzloch mriežky (obr. 2.13).

Potom si môžete vybrať z uzlových hodnôt extrému. Táto cesta nie je racionálna, je spojená s veľkým počtom výpočtov a presnosť je nízka, pretože závisí od kroku a optimum sa môže nachádzať medzi uzlami.

Numerické metódy

Matematické modely obsahujú vzťahy zostavené na základe teoretickej analýzy skúmaných procesov alebo získané ako výsledok spracovateľských experimentov (tabuľky údajov, grafy). V každom prípade matematický model iba približne popisuje skutočný proces. Preto je najdôležitejšia otázka presnosti, primeranosti modelu. Potreba aproximácií vzniká už pri samotnom riešení rovníc. Až donedávna nebolo možné analyticky riešiť modely obsahujúce nelineárne alebo parciálne diferenciálne rovnice. To isté platí pre početné triedy nezmršťovacích integrálov. Rozvoj metód numerickej analýzy však umožnil výrazne rozšíriť hranice možností analýzy matematických modelov, najmä s využitím počítačov.

Numerické metódy sa používajú na aproximáciu funkcií, na riešenie diferenciálnych rovníc a ich sústav, na integráciu a diferenciáciu, na výpočet číselných výrazov.

Funkciu je možné definovať analyticky, tabuľkovo, graficky. Pri výskume je častým problémom aproximácia funkcie analytickým výrazom, ktorý spĺňa uvedené podmienky. Tým sú splnené štyri úlohy:

Výber uzlových bodov, vykonávanie experimentov na určitých hodnotách (úrovniach) nezávislých premenných (ak je krok zmeny faktora zvolený nesprávne, buď „preskočíme“ charakteristický znak skúmaného procesu, alebo predĺžime postup a zvýšiť zložitosť hľadania vzorov);

Výber aproximačných funkcií vo forme polynómov, empirických vzorcov v závislosti od obsahu konkrétneho problému (treba sa snažiť o maximálne zjednodušenie aproximačných funkcií);

Výber a použitie kritérií dobrej zhody, na základe ktorých sa zisťujú parametre aproximačných funkcií;

Splnenie požiadaviek danej presnosti na výber aproximačnej funkcie.

V problémoch aproximácie funkcií polynómami sa používajú tri triedy

Lineárna kombinácia mocninových funkcií (Taylorove rady, Lagrangeove, Newtonove polynómy atď.);

Kombinácia funkcií cos nx, w nich(séria Fourier);

Polynóm tvorený funkciami exp(-a, d).

Pri hľadaní aproximačnej funkcie sa používajú rôzne kritériá zhody s experimentálnymi údajmi.

Pri optimalizácii gradientovou metódou sa hľadá optimum skúmaného objektu v smere najrýchlejšieho nárastu (poklesu) výstupnej premennej, t.j. v smere sklonu. Ale predtým, ako urobíte krok v smere gradientu, musíte ho vypočítať. Gradient je možné vypočítať buď z dostupného modelu

simulačný dynamický gradientový polynóm

kde je čiastočná derivácia vzhľadom na i-tý faktor;

i, j, k - jednotkové vektory v smere súradnicových osí faktorového priestoru, alebo podľa výsledkov n pokusných pohybov v smere súradnicových osí.

Ak má matematický model štatistického procesu tvar lineárneho polynómu, ktorého regresné koeficienty b i sú parciálnymi deriváciami expanzie funkcie y = f(X) v Taylorovom rade v mocninách x i, potom optimum je hľadá sa v smere gradientu s určitým krokom h i:

pkfv n (Ch) \u003d a 1 p 1 + a 2 p 2 + ... + a t p t

Smer sa koriguje po každom kroku.

Gradientová metóda spolu s jej početnými modifikáciami je bežnou a efektívnou metódou na nájdenie optima skúmaných objektov. Zvážte jednu z modifikácií gradientovej metódy - metódu strmého výstupu.

Metóda strmého výstupu alebo inak Box-Wilsonova metóda spája výhody troch metód - Gaussovej-Seidelovej metódy, gradientovej metódy a metódy úplných (alebo zlomkových) faktoriálnych experimentov, ako prostriedku na získanie lineárneho matematického modelu. . Úlohou metódy strmého stúpania je vykonávať krokovanie v smere najrýchlejšieho zvyšovania (alebo znižovania) výstupnej premennej, teda pozdĺž grady (X). Na rozdiel od gradientovej metódy sa smer koriguje nie po každom ďalšom kroku, ale keď sa v určitom bode v danom smere dosiahne čiastočný extrém účelovej funkcie, ako sa to robí v Gauss-Seidelovej metóde. V bode čiastočného extrému sa nastaví nový faktoriálny experiment, určí sa matematický model a opäť sa uskutoční strmý výstup. V procese smerovania k optimu touto metódou sa pravidelne vykonáva štatistická analýza medzivýsledkov vyhľadávania. Vyhľadávanie sa ukončí, keď sa kvadratické efekty v regresnej rovnici stanú významnými. To znamená, že bola dosiahnutá optimálna oblasť.

Opíšme si princíp použitia gradientových metód na príklade funkcie dvoch premenných

podlieha dvom dodatočným podmienkam:

Tento princíp (bez zmeny) možno aplikovať na ľubovoľný počet premenných, ako aj na dodatočné podmienky. Uvažujme rovinu x 1 , x 2 (obr. 1). Podľa vzorca (8) každý bod zodpovedá určitej hodnote F. Na obr.1 sú priamky F = const patriace do tejto roviny reprezentované uzavretými krivkami obklopujúcimi bod M * , kde F je minimálne. Nech v počiatočnom okamihu hodnoty x 1 a x 2 zodpovedajú bodu M 0 . Cyklus výpočtu začína sériou skúšobných krokov. Po prvé, x 1 dostane malý prírastok; v tomto čase je hodnota x 2 nezmenená. Potom sa určí výsledný prírastok hodnoty F, ktorý možno považovať za úmerný hodnote parciálnej derivácie

(ak je hodnota vždy rovnaká).

Definícia parciálnych derivácií (10) a (11) znamená, že sa nájde vektor so súradnicami a, ktorý sa nazýva gradient F a je označený takto:

Je známe, že smer tohto vektora sa zhoduje so smerom najstrmšieho nárastu hodnoty F. Opačným smerom je „najstrmší zostup“, inými slovami, najstrmší pokles hodnoty F.

Po nájdení zložiek gradientu sa skúšobné pohyby zastavia a pracovné kroky sa uskutočnia v smere opačnom ako je smer gradientu, pričom veľkosť kroku je tým väčšia, čím väčšia je absolútna hodnota vektora grad F. podmienky sa realizujú, ak sú hodnoty pracovných krokov a sú úmerné predtým získaným hodnotám parciálnych derivácií:

kde b je kladná konštanta.

Po každom pracovnom kroku sa odhadne prírastok F. Ak sa ukáže, že je záporný, potom je pohyb správnym smerom a musíte sa pohybovať v rovnakom smere M 0 M 1 ďalej. Ak to v bode M 1 ukazuje výsledok merania, potom sa pracovné pohyby zastavia a začne sa nová séria skúšobných pohybov. V tomto prípade sa gradient gradF určí v novom bode M1, potom pracovný pohyb pokračuje v novom zistenom smere najstrmšieho klesania, t.j. pozdĺž priamky M1M2 atď. Táto metóda sa nazýva metóda najstrmšieho zostupu/najstrmšieho výstupu.

Keď je systém blízko minima, čo je indikované malou hodnotou množstva

existuje prechod na „opatrnejšiu“ metódu vyhľadávania, takzvanú gradientnú metódu. Od metódy najstrmšieho klesania sa líši v tom, že po určení gradientu gradF sa urobí iba jeden pracovný krok a potom sa séria skúšobných pohybov opäť začína v novom bode. Táto metóda hľadania poskytuje presnejšie stanovenie minima v porovnaní s metódou najstrmšieho zostupu, zatiaľ čo táto metóda vám umožňuje rýchlo sa priblížiť k minimu. Ak pri vyhľadávaní bod M dosiahne hranicu prípustnej oblasti a aspoň jedna z hodnôt M 1 , M 2 zmení znamienko, zmení sa metóda a bod M sa začne pohybovať po hranici oblasti.

Účinnosť metódy strmého stúpania závisí od výberu škály premenných a typu povrchu odozvy. Povrch s guľovitými kontúrami zaisťuje rýchle sťahovanie do optima.

Nevýhody metódy strmého stúpania zahŕňajú:

1. Obmedzenie extrapolácie. Pri pohybe po gradiente sa spoliehame na extrapoláciu parciálnych derivácií účelovej funkcie vzhľadom na zodpovedajúce premenné. Tvar odozvovej plochy sa však môže zmeniť a je potrebné zmeniť smer hľadania. Inými slovami, pohyb po rovine nemôže byť nepretržitý.

2. Ťažkosti pri hľadaní globálneho optima. Metóda je použiteľná na hľadanie iba lokálnych optimov.

Vektor gradientu smeruje k najrýchlejšiemu nárastu funkcie v danom bode. Vektor opačný k gradientu -grad(/(x)) sa nazýva antigradient a smeruje v smere najrýchlejšieho poklesu funkcie. V minimálnom bode je gradient funkcie nulový. Metódy prvého rádu, nazývané aj gradientové metódy, sú založené na vlastnostiach gradientu. Ak nie sú žiadne ďalšie informácie, potom z počiatočného bodu x (0 > je lepšie ísť do bodu x (1) , ležiaceho v smere antigradientu - najrýchlejší pokles funkcie. Voľba ako smer zostupu antigradient -grad (/(x (^)) v bode x (do získame iteračný proces formulára

V súradnicovej forme je tento proces napísaný takto:

Ako kritérium na zastavenie iteračného procesu je možné použiť buď podmienku (10.2) alebo splnenie podmienky pre malosť gradientu.

Možné je aj kombinované kritérium, spočívajúce v súčasnom splnení uvedených podmienok.

Gradientové metódy sa navzájom líšia spôsobom výberu veľkosti kroku. A V metóde konštantného kroku sa pre všetky iterácie vyberie určitá hodnota konštantného kroku. Dosť malý krok a^ zabezpečuje zníženie funkcie, t.j. naplnenie nerovnosti

To však môže viesť k potrebe vykonať dostatočne veľký počet iterácií na dosiahnutie minimálneho bodu. Na druhej strane príliš veľký krok môže spôsobiť rast funkcie alebo viesť k výkyvom okolo minimálneho bodu. Na výber veľkosti kroku sú potrebné ďalšie informácie, takže metódy s konštantným krokom sa v praxi používajú len zriedka.

Spoľahlivejšie a ekonomickejšie (z hľadiska počtu iterácií) sú gradientové metódy s premenlivým krokom, kedy sa v závislosti od získanej aproximácie nejakým spôsobom mení veľkosť kroku. Ako príklad takejto metódy zvážte metódu najstrmšieho zostupu. Pri tejto metóde sa pri každej iterácii volí hodnota kroku n* z podmienky minima funkcie /(x) v smere zostupu, t.j.

Tento stav znamená, že pohyb po antigradiente nastáva dovtedy, kým hodnota funkcie f(x) klesá. Preto je pri každej iterácii potrebné vyriešiť problém jednorozmernej minimalizácie vzhľadom na π funkcie φ(λ) =/(x(/r) - - agrad^x^))). Algoritmus metódy najstrmšieho zostupu je nasledujúci.

• 1. Nastavíme súradnice počiatočného bodu x^°, presnosť približného riešenia r. k = 0.
• 2. V bode x (/z) vypočítame hodnotu gradientu grad(/(x (^)).
• 3. Určite veľkosť kroku a^ jednorozmernou minimalizáciou vzhľadom na i funkcie cp(i).
• 4. Definujeme novú aproximáciu k minimálnemu bodu x (* +1 > podľa vzorca (10.4).
• 5. Skontrolujte podmienky na zastavenie iteračného procesu. Ak sú spokojní, výpočty sa zastavia. V opačnom prípade kladieme kk+ 1 a prejdite na položku 2.

Pri metóde najstrmšieho klesania sa smer pohybu z bodu x (*) dotkne čiary úrovne v bode x (* +1) . Trajektória zostupu je cik-cak a susedné cik-cak spojnice sú navzájom ortogonálne. Naozaj, krok a^ sa vyberá minimalizáciou A funkcie ( A). Nevyhnutná podmienka

minimum funkcie - = 0. Výpočet derivácie

komplexnej funkcie, získame podmienku ortogonality pre vektory smeru zostupu v susedných bodoch:

Problém minimalizácie funkcie φ(n) možno zredukovať na problém výpočtu koreňa funkcie jednej premennej g(a) =

Gradientové metódy konvergujú k minimu rýchlosťou geometrickej progresie pre hladké konvexné funkcie. Takéto funkcie majú najväčšie a najmenšie vlastné hodnoty matice druhých derivácií (Hesseho matice)

málo sa od seba líšia, t.j. matica H(x) je dobre podmienená. V praxi však majú minimalizované funkcie často zle podmienené matice druhých derivácií. Hodnoty takýchto funkcií v niektorých smeroch sa menia oveľa rýchlejšie ako v iných smeroch. Rýchlosť konvergencie gradientových metód tiež výrazne závisí od presnosti gradientových výpočtov. Strata presnosti, ktorá sa zvyčajne vyskytuje v blízkosti minimálnych bodov, môže vo všeobecnosti narušiť konvergenciu procesu gradientového zostupu. Preto sa gradientové metódy často používajú v kombinácii s inými, efektívnejšími metódami v počiatočnom štádiu riešenia problému. V tomto prípade je bod x(0) ďaleko od minimálneho bodu a kroky v smere antigradientu umožňujú dosiahnuť výrazný pokles funkcie.

Neexistujú žiadne obmedzenia v probléme neobmedzenej optimalizácie.

Pripomeňme, že gradient viacrozmernej funkcie je vektor, ktorý je analyticky vyjadrený geometrickým súčtom parciálnych derivácií

Gradient skalárnych funkcií F(X) v určitom bode smeruje k najrýchlejšiemu nárastu funkcie a je kolmá na čiaru úrovne (plochy konštantnej hodnoty F(X), prechod cez bod X k). Vektor opačný ku gradientu  antigradient  smeruje v smere najrýchlejšieho poklesu funkcie F(X). V extrémnom bode grad F(X)= 0.

V gradientových metódach je pohyb bodu pri hľadaní minima účelovej funkcie opísaný iteračným vzorcom

Kde  k  parameter step on k iteráciu pozdĺž antigradientu. Pri lezeckých metódach (hľadanie maxima) sa musíte pohybovať po stúpaní.

Rôzne varianty gradientových metód sa od seba líšia spôsobom výberu parametra kroku, ako aj zohľadnením smeru pohybu v predchádzajúcom kroku. Zvážte nasledujúce možnosti pre metódy gradientu: s konštantným krokom, s parametrom premenlivého kroku (rozdelenie kroku), metóda najstrmšieho zostupu a metóda konjugovaného gradientu.

Metóda s parametrom konštantného kroku. V tejto metóde je parameter step konštantný pri každej iterácii. Vzniká otázka: ako prakticky zvoliť hodnotu parametra kroku? Dostatočne malý parameter kroku môže viesť k neprijateľne veľkému počtu iterácií potrebných na dosiahnutie minimálneho bodu. Na druhej strane, parameter kroku, ktorý je príliš veľký, môže viesť k prekročeniu minimálneho bodu a k oscilačnému výpočtovému procesu okolo tohto bodu. Tieto okolnosti sú nevýhodou metódy. Pretože nie je možné vopred uhádnuť prijateľnú hodnotu parametra kroku  k, potom je potrebné použiť metódu gradientu s variabilným parametrom kroku.

Keď sa približuje k optimu, veľkosť gradientu vektora klesá a má tendenciu k nule, keď  k = dĺžka konštantného kroku sa postupne znižuje. V blízkosti optima má dĺžka vektora gradientu tendenciu k nule. Dĺžka vektora alebo norma v n-rozmerný euklidovský priestor je určený vzorcom

, Kde n- počet premenných.

Možnosti na zastavenie hľadania optima:

Z praktického hľadiska je vhodnejšie použiť 3. kritérium zastavenia (keďže hodnoty parametrov návrhu sú zaujímavé), avšak na určenie blízkosti extrémneho bodu sa musíte zamerať na 2. kritérium. Na zastavenie výpočtového procesu možno použiť niekoľko kritérií.

Zvážte príklad. Nájdite minimum účelovej funkcie F(X) = (X 1  2) 2 + (X 2  4) 2 . Presné riešenie problému X*= (2,0; 4,0). Výrazy pre parciálne derivácie

,
.

Vyberte krok  k = 0,1. Poďme hľadať od začiatku X 1 = . Riešenie je prezentované vo forme tabuľky.

Gradientová metóda s krokovým rozdelením parametrov. V tomto prípade sa pri optimalizačnom procese parameter kroku  k znižuje, ak sa po ďalšom kroku zvýši cieľová funkcia (pri hľadaní minima). V tomto prípade sa dĺžka kroku často rozdelí (rozdelí) na polovicu a krok sa opakuje od predchádzajúceho bodu. To poskytuje presnejší prístup k extrémnemu bodu.

Najstrmší spôsob zostupu. Metódy s premenlivými krokmi sú ekonomickejšie z hľadiska počtu iterácií. Ak je optimálna dĺžka kroku  k v smere antigradientu riešením problému jednorozmernej minimalizácie, potom sa táto metóda nazýva metóda najstrmšieho zostupu. V tejto metóde sa pri každej iterácii rieši problém jednorozmernej minimalizácie:

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

.

Pri tejto metóde pokračuje pohyb v smere antigradientu, kým sa nedosiahne minimum objektívnej funkcie (kým sa nezníži hodnota objektívnej funkcie). Pomocou príkladu zvážte, ako možno účelovú funkciu analyticky zapísať v každom kroku v závislosti od neznámeho parametra

Príklad. min F(X 1 , X 2 ) = 2X 1 2 + 4X 2 3 – 3. Potom  F(X)= [ 4X 1 ; 12X 2 2 ]. Nechajte bod X k = , teda  F(X)= [ 8; 12], F(X k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Je potrebné nájsť , ktoré poskytuje minimum tejto funkcie.

Algoritmus najstrmšieho zostupu (na nájdenie minima)

počiatočný krok. Nech  je zastavovacia konštanta. Vyberte počiatočný bod X 1 , dať k = 1 a prejdite na hlavný krok.

Základný krok. Ak || gradF(X)||< , potom ukončite vyhľadávanie, inak určite  F(X k ) a nájsť  k  optimálne riešenie problému minimalizácie F(X k   k S k ) pri  k  0. Dajte X k +1 = X k   k S k, priradiť k =

k + 1 a zopakujte hlavný krok.

Ak chcete nájsť minimum funkcie jednej premennej v metóde najstrmšieho zostupu, môžete použiť metódy unimodálnej optimalizácie. Z veľkej skupiny metód uvažujme o metóde dichotómie (bisekcie) a zlatého rezu. Podstatou unimodálnych optimalizačných metód je zúženie intervalu neistoty umiestnenia extrému.

Dichotomická metóda (bisekcia)Počiatočný krok. Zvoľte konštantu rozlíšiteľnosti  a konečnú dĺžku intervalu neistoty l. Hodnota  by mala byť čo najmenšia, ale mala by umožniť rozlíšenie hodnôt funkcie F( ) A F( ) . Nechaj [ a 1 , b 1 ]  počiatočný interval neistoty. Dajte k =

Hlavná fáza pozostáva z konečného počtu iterácií rovnakého typu.

k-tá iterácia.

Krok 1. Ak b k  a k  l, potom sa výpočet skončí. Riešenie X * = (a k + b k )/2. Inak

,
.

Krok 2 Ak F( k ) < F( k ), dať a k +1 = a k ; b k +1 =  k. Inak a k +1 =  k A b k +1 = b k. Priradiť k = k + 1 a prejdite na krok 1.

Metóda zlatého rezu. Efektívnejšia metóda ako metóda dichotómie. Umožňuje získať danú hodnotu intervalu neistoty v menšom počte opakovaní a vyžaduje menej výpočtov cieľovej funkcie. Pri tejto metóde sa nový deliaci bod intervalu neistoty vypočíta raz. Nový bod je umiestnený v určitej vzdialenosti

 = 0,618034 od konca intervalu.

Algoritmus zlatého pomeru

Počiatočný krok. Vyberte prijateľnú konečnú dĺžku intervalu neistoty l > 0. Nechaj [ a 1 , b 1 ]  počiatočný interval neistoty. Dajte  1 = a 1 +(1   )(b 1  a 1 ) A  1 = a 1 +  (b 1  a 1 ) , Kde  = 0,618 . Vypočítajte F( 1 ) A F( 1 ) , dať k = 1 a prejdite na hlavný krok.

Krok 1. Ak b k  a k  l, potom výpočty skončia X * = (a k + b k )/ 2. V opačnom prípade, ak F( k ) > F( k ) , potom prejdite na krok 2; Ak F( k )  F( k ) , prejdite na krok 3.

Krok 2 Dajte a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Vypočítajte F( k +1 ), prejdite na krok 4.

Krok 3 Dajte a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Vypočítajte F( k +1 ).

Krok 4 Priradiť k = k + 1, prejdite na krok 1.

Pri prvej iterácii sú potrebné dve hodnotenia funkcií, pri všetkých nasledujúcich iteráciách iba jedno.

Metóda konjugovaného gradientu (Fletcher-Reeves). Pri tejto metóde je voľba smeru pohybu na k+ 1 krok zohľadňuje zmenu smeru zapnutia k krok. Vektor smeru zostupu je lineárnou kombináciou smeru proti prechodu a predchádzajúceho smeru vyhľadávania. V tomto prípade pri minimalizácii funkcií rokliny (s úzkymi dlhými korytami) nie je hľadanie kolmo na roklinu, ale pozdĺž nej, čo umožňuje rýchlo dosiahnuť minimum. Pri hľadaní extrému metódou konjugovaného gradientu sú súradnice bodu vypočítané výrazom X k +1 = X k   V k +1 , Kde V k +1 je vektor vypočítaný nasledujúcim výrazom:

.

Prvá iterácia sa zvyčajne spolieha V = 0 a vykoná sa antigradientové vyhľadávanie, ako pri metóde najstrmšieho zostupu. Potom sa smer pohybu odchyľuje od smeru antigradientu tým viac, čím výraznejšie sa zmenila dĺžka vektora gradientu pri poslednej iterácii. Po n kroky na opravu činnosti algoritmu urobia obvyklý krok pozdĺž antigradientu.

Algoritmus metódy konjugovaného gradientu

Krok 1. Zadajte počiatočný bod X 0 , presnosť  , rozmer n.

Krok 2 Dajte k = 1.

Krok 3 Vložte vektor V k = 0.

Krok 4 Vypočítajte grad F(X k ).

Krok 5 Vypočítajte vektor V k +1.

Krok 6 Vykonajte 1D vyhľadávanie vektorov V k +1.

Krok 7 Ak k < n, dať k = k + 1 a prejdite na krok 4, inak prejdite na krok 8.

Krok 8 Ak je dĺžka vektora V menej ako , ukončite vyhľadávanie, inak prejdite na krok 2.

Metóda konjugovaného smeru je jednou z najúčinnejších pri riešení problémov minimalizácie. Metóda v spojení s jednorozmerným vyhľadávaním sa v praxi často využíva v CAD. Je však potrebné poznamenať, že je citlivý na chyby, ktoré sa vyskytnú počas procesu výpočtu.

Nevýhody gradientových metód

Pri problémoch s veľkým počtom premenných je ťažké alebo nemožné získať deriváty vo forme analytických funkcií.

Pri výpočte derivácií pomocou diferenčných schém výsledná chyba, najmä v blízkosti extrému, obmedzuje možnosti takejto aproximácie.