Metoda gradientului. Cea mai simplă metodă de gradient
După cum am observat deja, sarcina de optimizare este sarcina de a găsi astfel de valori ale factorilor. h. 1 = h. 1* , h. 2 = h. 2* , …, h. K. = h. K. * în care funcția de răspuns ( w.) atinge valoarea extremă w. \u003d Ext (optim).
Cunoscut diverse metode soluții la problema de optimizare. Una dintre cele mai utilizate este metoda gradientului, numită și Boxing Wilson și metoda de ascensiune abruptă.
Luați în considerare esența metodei de gradient pe exemplul unei funcții de răspuns cu două factori y \u003d.f (x. 1 , H. 2 ). În fig. 4.3 În spațiul factorial, sunt descrise curbele de valori egale ale funcției de răspuns (curbe de nivel). Punct cu coordonatele h. 1 *, h. 2 * corespunde valorii extreme a funcției de răspuns w. Ext.
Dacă alegem orice punct de factor ca sursă ( h. 1 0 , h. 2 0), cea mai scurtă cale spre partea superioară a funcției de răspuns din acest punct este calea, printr-o curbă, tangentă la care la fiecare punct coincide cu curba normală la nivelul, adică. Aceasta este calea în direcția gradientului funcției de răspuns.
Gradientul funcției continue neechivoce y \u003d.f.(x. 1 , H. 2) - Acesta este un vector determinat în direcția gradientului cu coordonatele:
unde i,j. - vectori singuri în direcția axelor de coordonate h. 1 I. h. 2. Derivați privați și caracterizați direcția vectorului.
De când ne-am cunoscut un tip de dependență y \u003d.f.(x. 1 , H. 2), nu putem găsi derivați privați și nu determinăm direcția adevărată a gradientului.
Conform metodei de gradient dintr-o parte din spațiul factorului, este selectat punctul inițial (niveluri inițiale) h. 1 0 , h. Douăzeci de ani. În ceea ce privește aceste niveluri inițiale, este construit un plan experimental simetric cu două niveluri. Mai mult, intervalul de variație este ales atât de mic încât modelul liniar se dovedește a fi adecvat. Se știe că orice curbă pe un complot suficient de mic poate fi aproximată de un model liniar.
După construirea unui plan simetric pe două niveluri, este rezolvată o sarcină de interpolare, adică. Modelul liniar este construit:
Și adecvarea este verificată.
Dacă un model liniar a fost adecvat pentru intervalul de variație selectat, atunci direcția gradientului poate fi determinată:
Astfel, direcția gradientului funcției de răspuns este determinată de valorile coeficienților de regresie. Aceasta înseamnă că vom trece în direcția gradientului, dacă din punctul cu coordonatele ( ) Ne întoarcem la punctul cu coordonatele:
unde m -un număr pozitiv care determină pasul în direcția gradientului.
În măsura în care h. 1 0 \u003d 0 și h. 2 0 \u003d 0, atunci 
.
După determinarea direcției gradientului () și alegerea pasului m., efectuați experiență la nivel inițial H. 1 0 , h. 2 0 .
Apoi faceți un pas în direcția gradientului, adică Realizăm experiență în punctul cu coordonatele. Dacă valoarea funcției de răspuns a crescut în comparație cu valoarea sa la nivelul inițial, luăm un alt pas în direcția gradientului, adică. Realizăm experiență la punctul cu coordonatele:
Mișcarea gradientului continuă până când funcția de răspuns începe să scadă. În fig. 4.3 Mișcarea pe un gradient corespunde unei emergente directe din punct ( h. 1 0 , h. douăzeci). Se abate treptat de la direcția adevărată a gradientului prezentat de linia de accident vascular cerebral, datorită neliniarității funcției de răspuns.
De îndată ce funcția de răspuns, valoarea funcției de răspuns a scăzut, mișcarea de gradient se oprește, luați experiență cu valoarea maximă a funcției de răspuns pentru noul nivel inițial, alcătuiesc un nou plan simetric pe două niveluri și rezolvați din nou interpolarea sarcină.
Buing un nou model liniar 
, efectuați analiza de regresie. Dacă, în același timp, verificarea semnificației factorilor arată că cel puțin un coefic
cel mai violent, ceea ce înseamnă, zona extremum a funcției de răspuns (zona optimă) nu a fost încă atinsă. Noua direcție a gradientului este determinată și începe mișcarea la zona optimă.
Clarificarea direcției gradientului și a mișcării de-a lungul gradientului continuă până când procesul de rezolvare a următoarei probleme de interpolare nu va arăta valabilitatea factorilor pe care toți factorii nu sunt nesemnificativi, adică. Tot . Aceasta înseamnă că zona optimă este realizată. Această soluție la sarcina de optimizare este oprită și luați experiență cu valoarea maximă a funcției de răspuns pentru optimă.
ÎN general Secvența de acțiuni necesare pentru rezolvarea problemei de optimizare prin metoda gradientului poate fi reprezentată ca o diagramă bloc (figura 4.4).
1) Nivelurile sursei de factori ( h. J. 0) Ar trebui să fie selectat posibil mai aproape de punctul optim, dacă există câteva informații prealabile despre poziția sa;
2) Intervale de variație (δ h. J.) Este necesar să se aleagă astfel încât modelul liniar să se dovedească cu siguranță să fie adecvat. Limita de sub δ. h. J. În acest caz, valoarea minimă a intervalului de variație, în care funcția de răspuns rămâne semnificativă;
3) Valoarea pasului ( t.) Atunci când se deplasează de-a lungul gradientului, alegeți astfel încât cea mai mare dintre lucrări nu depășesc diferența în nivelurile superioare și inferioare ale factorilor din forma normalizată
.
Prin urmare,. Cu un sens mai mic t. Diferența în funcția de răspuns la nivel inițial și la punctul cu coordonatele poate fi nesemnificativă. Cu o valoare mai mare a pasului, este periculoasă să alunece funcția de răspuns optimă.
Curs 6.
Metode de gradient Rezolvarea problemelor de programare neliniară.
Întrebări:1. caracteristici generale Metode.
2. Metoda de gradient.
3. Metoda marelui birou.
4. Metoda de îndeplinire Frank.
5. Funcții de penalizare.
1. Caracteristicile generale ale metodelor.
Metodele de gradient sunt aproximative (iterative) metode de rezolvare a problemei programării neliniare și vă permit să rezolvați aproape orice sarcină. Cu toate acestea, extremumul local este determinat. Prin urmare, este recomandabil să se aplice aceste metode pentru a rezolva sarcinile de programare convexe în care fiecare extremum local este atât global. Procesul de rezolvare a problemei este că, începând cu un anumit punct x (inițial), o tranziție secvențială este efectuată în direcția GRADF (X), dacă este determinat punctul maxim și -GRADF (X) (antigigadient), dacă Punctul minim este definit în punctul care decide problema. În același timp, acest punct poate fi în zona valorilor admise și la granița sa.
Metodele de gradient pot fi împărțite în două clase (grupuri). Primul grup include metode în care toate punctele studiate aparțin zonei admise. Astfel de metode includ: metoda gradientului, coborârea de bază, Frank-Wulf și alții. Al doilea grup include metode în care punctele studiate nu pot aparține zonei admise. Comună de astfel de metode este metoda de funcții de penalizare. Toate metodele de caracteristici de penalizare diferă una de cealaltă prin metoda de determinare a "amenzii".
Principalul concept utilizat în toate metodele de gradient este conceptul unui gradient al funcției, ca instrucțiuni de definiție a funcției.
La determinarea soluției de metode de gradient, procesul iterativ continuă până la:
Fie grad f (x *) \u003d 0, (soluție precisă);
unde 
- Două puncte succesive, 
- Numărul mic care caracterizează acuratețea soluției.
2. Metoda de gradient.
Imaginați-vă că un om stând pe panta râului, care trebuie să coboare (în partea de jos). Cel mai natural, se pare, direcția spre cea mai mare abruptură a coborârii, adică. (-Grad f (x)). Strategia primită în același timp, numită metoda de gradienteste o secvență de pași, fiecare dintre care conține două operații:
a) determinarea direcției celei mai mari abrupturi a coborârii (ridicare);
b) Deplasați-vă în direcția selectată pentru un pas.
Alegerea corectă a pasului este esențială. Pasul mai puțin, cu atât rezultatul mai precis, dar mai mult computing. Diferite modificări ale metodei de gradient și constau în utilizarea diferitelor modalități de determinare a pasului. Dacă, în orice pas, valoarea f (x) nu a scăzut, înseamnă că punctul minim "alunecat", caz în care este necesar să se reîntoarcă la punctul anterior și să reducă pasul, de exemplu, de două ori.
Schema de soluții.
aparținând regiunii admise
3. Selectați pasul H.
x (k + 1) \u003d x (k) 
"-" - dacă min.
5. Determinarea F (x (K +1)) și:
În cazul în care un 
Decizia găsită;
Cometariu.Dacă grad f (x (k)) \u003d 0, atunci soluția va fi corectă.
Exemplu.F (x) \u003d -6x 1 + 2x 1 2 - 2x 1 x 2 + 2x 2 2 
min.
x 1 + x 2 
2, x 1 
0, x 2 
0,
= 0,1.
3. Metoda marelui birou.
Spre deosebire de metoda de gradient, în care gradientul este determinat la fiecare etapă, în metoda gradientului se găsește la punctul de plecare și mișcarea din direcția găsită continuă aceiași pași până când valoarea funcției scade (crește). Dacă în orice pas f (x) a crescut (scăzut), atunci mișcarea din această direcție se oprește, ultima etapă este îndepărtată complet sau jumătate și se calculează noua valoare a gradientului și noua direcție.
Schema de soluții.
1. Determinarea x 0 \u003d (x 1, x 2, ..., x N),
aparținând zonei admise
și f (x 0), k \u003d 0.
2. Determinarea grad F (x 0) sau -Gradf (x 0).
3. Selectați pasul H.
4. Determinarea următorului punct prin formula
x (k + 1) \u003d x (k) 
h grad f (x (k)), "+" - dacă max,
"-" - dacă min.
5. Determinarea F (x (K +1)) și:
În cazul în care un 
Decizia găsită;
Dacă nu:
a) Când căutați min: - dacă F (x (K +1)) Dacă F (x (K +1))\u003e F (x (k)) - tranziția la alineatul (2); b) la căutarea max: - dacă (x (k +1))\u003e f (x (k)) - tranziția la clauza 4; Dacă f (x (k +1)) Observații:1. Dacă grad f (x (k)) \u003d 0, atunci soluția va fi corectă. 2. Avantajul metodei de coborâre formală este simplitatea și reducerea calculelor, deoarece gradul F (x) nu este calculat la toate punctele este important pentru sarcinile dimensiunii mari. 3. Dezavantajul este că pașii ar trebui să fie mici pentru a nu treceți la punctul optim. Exemplu.F (x) \u003d 3x 1 - 0,2x 1 2 + x 2 - 0,2x 2 2 x 1 + x 2 x 1 + 2x 2 4. Metoda Frank-Wulf. Metoda este utilizată pentru a optimiza neliniarul funcția țintă cu constrângeri liniare. În vecinătatea punctului de testare, o funcție țintă neliniară este înlocuită cu o funcție liniară, iar sarcina este redusă la o soluție secvențială de sarcini de programare liniară. Schema de soluții. 1. Determinarea x 0 \u003d (x 1, x 2, ..., x n) aparținând regiunii admise și F (x 0), k \u003d 0. 2. Definiție Grad F (x (k)). 3. Construiți o funcție 4. Definiția max (min) f (x) cu restricții sursă. Lăsați-o să fie punctul z (k). 5. Determinarea etapei de calcule x (k +1) \u003d x (k) + 6. DETERMINAREA F (x (K +1)) și verificați necesitatea unei computere suplimentare: În cazul în care un Dacă nu, atunci trecerea la alineatul (2). Exemplu.F (x) \u003d 4x 1 + 10x2 -x 1 2 -x2 2 x 1 + x 2 x 2. 5. Funcții de penalizare. Lăsați-o să fie necesară găsirea F (X 1, X2, ..., X N) g i (x 1, x 2, ..., x n) Funcțiile f și g sunt convexe sau concave. Ideea unei metode de funcții de penalizare este de a căuta valoarea optimă a noii funcții țintă Q (x) \u003d f (x) + h (x), care este suma funcției țintă inițială și unele funcții h (x), determinată de sistemul de restricții și numit funcția de pedeapsă. Funcțiile penale se construiesc în așa fel încât să ofere fie o revenire rapidă în zona admisă, fie imposibilitatea de ieșire din ea. Metoda de funcții de penalizare reduce sarcina pentru un extrem de extrem de condiționat pentru a rezolva problema problemelor de pe extremul necondiționat, care este mai ușor. Există multe modalități de a construi o funcție de penalizare. Cel mai adesea are forma: H (x) \u003d unde Notă: Decât mai puțin Începeți o soluție de la mic Folosind funcția de penalizare, treceți în mod constant de la un punct la altul până când se recepționează soluția acceptabilă. Schema de soluții. 1. Definiția punctului de pornire x 0 \u003d (x 1, x 2, ..., x N), f (x 0) și k \u003d 0. 2. Alegeți un pas al calculelor h. 3. Determinați instrumentele derivate private 4. Determinați coordonatele următorului punct cu formula: x J (K +1) 5. Dacă X (K +1) ce-ar fi dacă b) Dacă grad f (x (k +1)) \u003d 0, soluția exactă a fost găsită. Dacă X (K +1) Exemplu.F (x) \u003d - x 1 2 - x 2 2 (x 1 -5) 2 + (x 2 -5) 2 Metode de gradient Metodele de gradient de optimizare necondiționată utilizează numai primii derivați ai funcției țintă și sunt metode de aproximare liniară la fiecare etapă, adică Funcția țintă la fiecare etapă este înlocuită cu hiperplane tangențială la programul său la punctul curent. La etapa K-M a metodelor de gradient, trecerea de la punctul XK până la punctul XK + 1 este descrisă de relația: În cazul în care K este valoarea pasului, K este un vector în direcția XK + 1-XK. Metode de coborâre formală Pentru prima dată, o astfel de metodă revizuită și aplicată O. Cauchy în secolul al XVIII-lea. Ideea lui este simplă: gradientul funcției țintă f (x) în orice punct există un vector în direcția celei mai mari valori de creștere a funcției. În consecință, anti-Agadimentul va fi direcționat către cea mai mare scădere a funcției și este direcția mare de coborâre. Antigigraditul (și gradientul) suprafeței suprafeței ortogonale F (x) la punctul X. Dacă în (1.2) introduceți direcția aceasta va fi direcția mare de coborâre la punctul XK. Obținem formula de tranziție de la XK la XK + 1: Antigigraditul dă doar direcția de coborâre, dar nu magnitudinea pasului. În general, un pas nu dă un punct minim, astfel încât procedura de coborâre ar trebui aplicată de mai multe ori. La punctul minim, toate componentele gradientului sunt zero. Toate metodele de gradient utilizează ideea subliniată și diferă una de cealaltă prin detalii tehnice: calcularea derivaților conform formulei analitice sau a aproximării diferenței de curs; Valoarea pasului poate fi permanentă, schimbarea conform oricărei reguli sau ieșiți după aplicarea metodelor de optimizare unidimensională în direcția antigigurilor etc. etc. Nu ne vom opri în detaliu, pentru că Metoda marelui birou nu este recomandată, de obicei, ca o procedură de optimizare serioasă. Unul dintre dezavantajele acestei metode este că converge la orice punct staționar, inclusiv șa, care nu poate fi o soluție. Dar cel mai important lucru este convergența foarte lentă a coborârii formale în cazul general. Faptul este că coborârea este "mare" în sensul local. Dacă hipperspațiul de căutare este puternic alungit ("râu"), anti-Agadient este îndreptat aproape ortogonal DNU "RASP", adică. Cea mai bună direcție pentru a obține un minim. În acest sens, traducerea directă a termenului englez "Primul descendent", adică. Coborârea celei mai răi pante mai mult corespunde situației afacerilor decât termenului "nucleu", adoptat în literatura specială vorbitoare de limbă rusă. O ieșire în această situație este utilizarea informațiilor furnizate de al doilea derivat privat. O altă ieșire este de a schimba amploarea variabilelor. gradient derivat de aproximare liniar Metoda de conjugat Gradient Fletcher Rivis În metoda unui gradient conjugat, o secvență de direcții de căutare, care sunt combinații liniare, direcția actuală a gradului de coborâre și, direcțiile de căutare anterioare, adică. mai mult, coeficienții sunt aleși astfel încât să facă conjugatul direcțiilor de căutare. A dovedit că Și acesta este un rezultat foarte valoros care vă permite să construiți un algoritm de optimizare rapidă și eficientă. Algoritmul Fletcher Rivis. 1. Se calculează x0. 2. Pe pasul K-OH cu ajutorul unei căutări unic dimensionale în direcția există un f (x) minim, care determină punctul XK + 1. unde este o constantă arbitrară. Avantajul algoritmului Fletcher Rivis este că nu necesită o recurs a matricei și nu economisește memoria calculatorului, deoarece nu are nevoie de matrice utilizate în metodele Newtoniene, dar în același timp aproape la fel de eficace ca și algoritmii cvasi-Newtonian. pentru că Direcțiile de căutare sunt conjuga reciproc, funcția patrată va fi minimizată de nici o pașii n. În general, se utilizează repornirea, care vă permite să obțineți rezultatul. Algoritmul Fletcher Rivis este sensibil la acuratețea căutării unic dimensionale, astfel încât atunci când o utilizați, trebuie să eliminați orice erori de rotunjire care pot apărea. În plus, algoritmul poate refuza situațiile în care hessianul devine prost condiționat. Garanțiile de convergență întotdeauna și oriunde nu există un algoritm, deși practica arată că aproape întotdeauna algoritmul dă rezultatul. Metode Newtoniene Direcția de căutare corespunzătoare prezenței unei coborârii este asociată cu o armonizare liniară a funcției țintă. Metodele care utilizează al doilea derivate au apărut dintr-o armonizare patratic a funcției țintă, adică atunci când se descompune funcția într-o serie de Taylor, membrii ordinelor a treia și mai mari sunt aruncate. unde - Matrix Hesse. Cel puțin partea dreaptă (dacă există) se realizează în același loc, unde și minimul unei forme patratice. Scriem formula pentru a determina direcția de căutare: Minimul este realizat ca Algoritmul de optimizare în care direcția de căutare este determinată din această relație, se numește metoda Newton, iar direcția este o direcție newtoniană. În sarcinile de a căuta un minim de o funcție patratic arbitrară, cu o matrice pozitivă a celui de-al doilea derivați, metoda Newton oferă o soluție pentru o iterație, indiferent de selectarea punctului de plecare. Clasificarea metodelor Newtoniene De fapt, metoda lui Newton constă într-o singură aplicație a direcției Newtoniene pentru a optimiza funcția patratic. Dacă funcția nu este patrată, atunci teorema următoare este corectă. Teorema 1.4. Dacă matricea hesse a funcției neliniare f de formă partajată la un punct X * este definită pozitiv, punctul de pornire este selectat suficient de aproape de X * și lungimea etapelor este aleasă corect, metoda Newton converge la x * cu o viteză patrată. Newton este considerat o referință, comparați toate procedurile de optimizare dezvoltate cu acesta. Cu toate acestea, metoda Newton este operațională numai cu o matrice pozitivă definită și bine condiționată de Hesse (determinantul dintre acesta trebuie să fie semnificativ mai mare decât zero, sau mai degrabă raportul dintre cele mai mari și mai mici numere naturale ar trebui să fie aproape de unul). Pentru a elimina acest dezavantaj, modificat metodele Newton care utilizează indicațiile Newtoniene cât mai mult posibil și le evită numai atunci când este necesar. Principiul general al modificărilor metodei Newton este după cum urmează: La fiecare iterație, unele "asociate" sunt mai întâi construite cu o matrice definită pozitiv și apoi calculată prin formula Deoarece este definită pozitiv, va fi cu siguranță direcția de coborâre. Procedura de construcție este organizată astfel încât să coincide cu matricea Hesse dacă este definită pozitiv. Aceste proceduri se bazează pe o anumită expansiune a matricei. Un alt grup de metode, practic nu inferior vitezei lui Newton, se bazează pe armonizarea matricei Hesse folosind diferențele finale, deoarece Nu neapărat optimizarea valorilor exacte ale derivatelor. Aceste metode sunt utile atunci când calculul analitic al derivaților este dificil sau pur și simplu imposibil. Astfel de metode se numesc metode discrete ale lui Newton. Cheia pentru eficacitatea metodelor de tip Newtonian este de a ține cont de curbura funcției minimizate conținute în matricea Hesse și permițând să construiască un model patratic precis local al funcției țintă. Dar, la urma urmei, este posibil ca informațiile despre curbură să se colecteze și să se acumuleze pe baza monitorizării schimbării gradientului în timpul iterații ale coborârii. Metodele corespunzătoare bazate pe posibilitatea de aproximare a curburii unei funcții neliniare fără o formare explicită a matricei sale Hesse se numesc metode cvasi-newtoniene. Trebuie remarcat faptul că atunci când construim o procedură de optimizare a tipului Newtonian (inclusiv cvasi-newtonian), este necesar să se țină seama de posibilitatea apariției punctului de șa. În acest caz, vectorul celei mai bune direcții de căutare va fi tot timpul trimis la punctul de șa, în loc să se îngrijească de ea în direcția "în jos". Metoda Newton Rafson. Această metodă constă în utilizarea repetată a direcției Newtoniene atunci când optimizează funcțiile non-quadratice. Principala formulă iterativă a optimizării multidimensionale utilizate în această metodă atunci când alegeți o direcție de optimizare din raport Lungimea reală a piciorului este ascunsă într-o direcție newtoniană anormalizată. Deoarece această metodă nu necesită valoarea funcției țintă la punctul curent, se numește uneori o metodă indirectă sau analitică de optimizare. Abilitatea sa de a determina minimul unei funcții patrate pentru o calculare pare la prima vedere numai atractivă. Cu toate acestea, acest "un calcul" necesită costuri considerabile. În primul rând, este necesar să se calculeze derivații privați din prima comandă și n (n + 1) / 2 - secundă. În plus, matricea HESSSE trebuie inversată. Acest lucru necesită o comandă a operațiunilor de calcul N3. Cu aceleași costuri, metodele de direcții sau metodele de conjugare ale unui gradient conjugat pot face ordinea n pași, adică. Atinge aproape același rezultat. Astfel, iterația metodei Newton Rafson nu oferă avantajul în cazul unei funcții patrate. Dacă funcția nu este patrată, atunci Prin ea însăși, strategia nu face distincția cu care se apropie punctul staționar (minim, maxim, șa) și calculul valorilor funcției țintă, care ar putea fi urmărite dacă funcția nu a putut crește. Aceasta înseamnă că totul depinde de zona punctului staționar, punctul de plecare al căutării este dovedit. Strategia lui Newton-Rafson este rar utilizată în sine fără a modifica unul sau altul. Metodele Pearson. Pearson a propus mai multe metode cu armonizarea hessianului invers, fără a calcula în mod explicit al doilea derivat, adică. Prin observarea schimbărilor în direcția anti-profit. În acest caz, sunt obținute instrucțiunile conjugate. Acești algoritmi diferă numai în detaliu. Le oferim celor care au devenit distribuția mai largă în zonele aplicate. Algoritmul Pearson numărul 2. În acest algoritm, hessianul invers este aproximat de matricea HK \u200b\u200bcalculată la fiecare pas cu formula O matrice simetrică definită pozitiv este selectată ca o matrice inițială H0. Acest algoritm de Pearson duce adesea la situații în care matricea HK \u200b\u200bdevine prost condiționată, și anume, începe să oscileze, ezită între definiția pozitivă și nu este definită pozitiv, în timp ce determinantul matricei este aproape de zero. Pentru a evita această situație, este necesar ca fiecare parte să reporniți matricea, echivalând-o la H0. Pearson numărul 3 algoritm. În acest algoritm, matricea HK \u200b\u200b+ 1 este determinată din formula HK + 1 \u003d HK + Traiectoria coborârii generate de algoritm este similară cu comportamentul algoritmului lui Davidon-Fletcher Powell, dar treptele sunt puțin mai scurte. Pearson a propus, de asemenea, o varietate de acest algoritm cu o repornire ciclică a matricei. Algoritmul proiectiv Newton Rafson Pearson a oferit ideea algoritmului în care matricea este calculată din raport H0 \u003d R0, unde matricea R0 este aceeași cu matricele inițiale din algoritmii anteriori. Când K este o îndoită a numărului de variabile independente n, matricea HK \u200b\u200beste înlocuită cu matricea RK + 1 calculată ca sumă Valoarea HK \u200b\u200b(F (xk + 1) - F (xk)) este o proiecție a vectorului de creștere a gradientului (F (xk + 1) -F (xk)), ortogonal față de toți vectorii creșterii gradientului în pașii anteriori. După fiecare parte N, RK este o aproximare a Hessian H-1 inversă (XK), astfel încât în \u200b\u200besență se efectuează (aproximativ) căutarea lui Newton. Metoda Davidon-Fletcher Powela Această metodă are, de asemenea, alte nume - metoda de metrică variabilă, metoda cvasinuton, deoarece Folosește ambele abordări. Metoda Davidon-Fletcher-Power (DFP) se bazează pe utilizarea direcțiilor de Newtoniană, dar nu necesită calculul hessianului invers la fiecare pas. Direcția de căutare în pasul K este o direcție În cazul în care HI este o matrice simetrică definită pozitiv, care este actualizată la fiecare pas și în limită devine egală cu hessianul opus. Ca o matrice inițială h, una este de obicei aleasă. Procedura de DFP iterativă poate fi reprezentată după cum urmează: 3. Căutarea unidimensională (de obicei interpolarea cubică) de-a lungul direcției este determinată de K, minimizarea funcției. 4. Reminează. 5. Reminează. 6. determinat și. Dacă VK sau suficient de mic, procedura este finalizată. 9. Măriți k pe unitate și reveniți la pasul 2. Metoda este eficientă în practică, dacă eroarea de calcul al gradientului este mică, iar matricea HK \u200b\u200bnu devine prost condiționată. Matricea AK asigură convergența HK la G-1, matricea BK asigură o definitie pozitivă a HK + 1 în toate etapele și în limita elimină H0. În cazul unei funcții patrate acestea. Algoritmul DFP utilizează instrucțiuni conjugate. Astfel, metoda DFP utilizează atât ideile abordării Newtoniene, cât și proprietățile indicațiilor conjugate și în timpul minimizării funcției patrate convergează nu mai mult de n iterații. Dacă funcția optimizată are o vedere aproape de o funcție patrată, metoda DFP este eficientă datorită aproximării bune a G-1 (metoda Newton). Dacă funcția țintă are o vedere generală, metoda DFP este eficientă prin utilizarea instrucțiunilor conjugate. Metoda de gradient și soiurile sale aparțin celor mai frecvente metode de găsire a funcțiilor extremum ale mai multor variabile. Ideea metodei de gradient este aceea că în procesul de căutare a extremumului (pentru o certitudine maximă) se deplasează de fiecare dată în direcția cea mai mare creștere a funcției țintă. Metoda Gradient implică calcularea primelor derivați ai funcției țintă prin argumentele sale. Aceasta, precum și cele anterioare, aparține metodelor aproximative și ne permite să nu atingem punctul optim, dar abordă-l doar pentru un număr finit de pași. Smochin. 4.11. Smochin. 4.12. (caz bidimensional) Mai întâi, alegeți punctul de plecare dacă în cazul unidimensional (a se vedea punctul 4.2.6) din acesta este posibil să se deplaseze la stânga sau la dreapta (vezi figura 4.9), apoi un caz multidimensional, numărul de direcții posibile de mișcare este infinit de mare. În fig. 4.11, ilustrând cazul a două variabile, săgeți provenind din punctul de plecare DAR, Sunt afișate diferite direcții posibile. În acest caz, mișcarea în funcție de unele dintre ele oferă o creștere a valorii funcției țintă în raport cu punctul DAR (de exemplu, direcții 1-3),
Iar în alte zone duce la scăderea acesteia (direcții 5-8).
Având în vedere că poziția punctului optim este necunoscută, este considerată cea mai bună direcție în care funcția țintă crește mai repede. Această direcție este numită gradient Funcții. Rețineți că, la fiecare punct al planului de coordonate, direcția gradientului este perpendiculară pe tangentul liniei de nivel cu același punct. În analiza matematică, se dovedește că componentele funcției vectorului gradientului w. =/(*, x 2. ..., x n) sunt instrumentele sale derivate private pe argumente, adică. & Iad / (x 1, x 2 ,.= (Du / dcu, dc 2, ..., du / dh n). (4.20) Astfel, atunci când se caută o metodă maximă de gradient pe prima iterație, componentele gradientului conform formulelor (4.20) sunt calculate pentru punctul inițial și fac o etapă de lucru în direcția găsită, adică Tranziția la un nou punct -0) U "cu coordonate: 1§Gas1 / (x (0)), sau în formă vectorială unde X - Un parametru permanent sau variabil care determină lungimea etapei de lucru,? І\u003e 0. Pe cea de-a doua iterație calculează din nou vectorul de gradient este deja pentru un nou punct. După aceea, prin analog glichic Formula merge la punctul X ^ >
etc. (Fig. 4.12). Pentru arbitrare la-iterații au. Dacă se găsește maximul și minimul funcției țintă, atunci pe fiecare iterație este un pas în direcția opusă direcției gradientului. Se numește direcția antigigractorului. În loc de formula (4.22) în acest caz va fi Există multe soiuri ale metodei gradientului, care diferă în alegerea pașilor de lucru. Puteți, de exemplu, treceți la fiecare punct ulterior la o valoare permanentă. X și apoi lungimea pașilor de lucru este distanța dintre punctele adiacente x ^ lor 1 "- se dovedește a fi un modul proporțional al vectorului de gradient. Puteți, dimpotrivă, pe fiecare iterație să alegeți X. Astfel încât durata etapei de lucru rămâne constantă. Exemplu. Este necesar să găsiți o funcție maximă y \u003d 110-2 (LH, -4) 2 -3 (* 2 -5) 2. Desigur, folosind condiția necesară pentru extremum, primim imediat soluția dorită: x] - 4; x 2. \u003d 5. Cu toate acestea, pe acest exemplu simplu, este convenabil să se demonstreze algoritmul metodei gradientului. Calculați gradientul funcției țintă: grad. y \u003d (du / dh-, du / dh 2) \u003d (4 (4 - *,); 6 (5 - x 2)) și alegeți punctul de plecare L * "\u003d (x) °\u003e \u003d 0; 4 °\u003e \u003d 0). Valoarea funcției țintă pentru acest punct, cât de ușor este de a calcula, egal În [x ^ J \u003d 3. Puneți X. \u003d const \u003d 0,1. Magnitudinea gradientului la punct ZS (0) este Grad Y | X ^ J \u003d (16; 30). Apoi, în prima iterație, obținem conform formulelor (4.21) coordonatele punctului x 1) \u003d 0 + 0,1 16 \u003d 1,6; x ^ \u003d 0 + 0,1 30 \u003d 3. În (x (1)) \u003d 110-2 (1,6-4) 2-3 (3-5) 2 \u003d 86,48. După cum se poate vedea, este semnificativ mai mult decât valoarea anterioară. În cea de-a doua iterație, avem conform formulelor (4.22): Metodele de gradient pentru găsirea funcției țintă optimă se bazează pe utilizarea a două proprietăți principale ale gradientului funcției. 1. Gradientul funcției este un vector care la fiecare punct al zonei de definire a funcției Proiecția gradientului Metodele de gradient includ: metoda de relaxare, gradient, coborârea prestabilită și un număr de alții. Luați în considerare unele dintre metodele de gradient. În această metodă, coborârea se face în direcția celei mai stricte schimbări a funcției țintă, care, în mod natural, accelerează procesul de găsire a optimului. Căutarea optimă se face în două etape. În prima etapă există valori ale derivatelor private cu privire la toate variabilele independente care determină direcția gradientului în punctul în cauză. În a doua etapă, se efectuează un pas în direcția în direcția opusă gradientului (atunci când se caută un minim al funcției țintă). La efectuarea unui pas, valorile tuturor variabilelor independente se schimbă simultan. Fiecare dintre ele primește creșterea proporțională cu componenta corespunzătoare a gradientului de-a lungul acestei axe. Formula algoritmului poate fi: În acest caz, pasul
O altă înregistrare de formulare a algoritmului are forma: În acest algoritm, se utilizează vectorul de gradient normalizat, indicând doar direcția definiției funcției țintă, dar nu indică viteza de schimbare în această direcție. În strategia de schimbare a pasului unde
Natura căutării optime în metoda gradientului este prezentată în fig. 2.1. Timpul căutării poate fi găsit în fiecare etapă a raportului. unde Smochin. 2.1. Natura mișcării la optimă în metoda de gradient cu un număr mare de pași Dezavantajul metodei de gradient este că atunci când îl utilizați, este posibil să se detecteze doar minimul local al funcției țintă. Pentru a găsi alte caracteristici minime locale, este necesar să căutați din alte puncte inițiale. Un alt dezavantaj al acestei metode este o cantitate semnificativă de computere, deoarece La fiecare pas, valorile tuturor derivatelor private ale funcției optimizate pe toate variabilele independente sunt determinate. La aplicarea metodei de gradient la fiecare pas, este necesar să se determine valorile funcției optimizate a derivatelor private pe toate variabilele independente. Dacă numărul de variabile independente este semnificativ, atunci volumul calculelor crește semnificativ și timpul optim de căutare este în creștere. Schimbarea volumului de calcul poate fi realizată utilizând metoda coborârii preconceite. Esența metodei este după cum urmează. După ce un gradient al funcției optimizate se găsește la punctul de plecare și, prin urmare, a determinat direcția scăderii mesageriei la punctul specificat, etapa de coborâre este făcută în această direcție (figura 2.2). Dacă valoarea funcției ca rezultat a acestei etape a scăzut, o altă etapă este efectuată în aceeași direcție și astfel încât se găsește cel puțin în această direcție, după care gradientul este calculat și noua direcție a scăderii mai mari a Funcția țintă este determinată. Smochin. 2.2. Natura mișcării la optimă în metoda gradientului (∙∙∙∙) și metoda de gradient (∙∙∙∙) În comparație cu metoda gradientului, metoda de coborâre a prezentatorului se dovedește a fi mai profitabilă datorită reducerii computerelor. O caracteristică importantă a modului de coborâre formală este că atunci când se utilizează fiecare nouă direcție de mișcare la optimul ortogonal anterior. Acest lucru se explică prin faptul că mișcarea într-o singură direcție este efectuată până când direcția de mișcare ia consiliere la orice linie permanentă de nivel. Ca criteriu de căutare, aceeași condiție poate fi utilizată ca în metoda de mai sus. În plus, puteți lua, de asemenea, condiția căutării formei de relații unde Împărțirea căutării pentru sfârșitul căutării este justificată în cazurile în care funcția optimizată are un minim clar exprimat. Smochin. 2.3. Pentru a determina sfârșitul căutării în metoda marelui Ca strategie de schimbare, metodele prezentate mai sus (2.7) pot fi utilizate ca strategie.
max,
7, x 1 
0,
10, x 2 
0.
(Min - "-" max- "+").
(k) (z (k) -x (k)), unde 
(k) - pas, coeficient, 0 
1.
(k) Este selectat astfel încât valoarea funcției F (X) a fost max (min) la punctul X (K +1). Pentru a face acest lucru, rezolvați ecuația 
și alegeți cel mai mic (cel mai mare) rădăcini, dar 0 
1.
sau grad F (x (k +1)) \u003d 0, apoi se găsește soluția;
max,
4, x 1 
0,
2, x 2 
0.
max (min),
b I, I \u003d 
, X j. 
0, J \u003d 
.
,
- Un const pozitiv.
Cu cât soluția este mai rapidă, precizia este redusă;
și să le măriți în pașii ulteriori.
și 
.
.
Verificarea unei regiuni admise:
- Soluția se găsește dacă nu - trecerea la alineatul (2).
Zona admisibilă Setați un nou sens 
și mergeți la clauza 4.
max,
8, x 1 
0, x 2 
0.
direcționate de Normal la suprafața nivelului petrecut prin acest punct.
pe axa coordonatelor este egală cu o funcție derivată privată 
În funcție de variabilele corespunzătoare, adică
. (2.4)Metoda de gradient
,
. (2.5)
cu o valoare constantă a parametrului, se schimbă automat cu o modificare a valorii gradientului și când se apropie optimul este redus.
,
. (2.6)
În acest caz, se utilizează gradienți 
și 
diferă în direcția. Schimbarea pasului de căutare se face în conformitate cu regula:
(2.7)
- unghiul de rotație a gradientului este o expresie definită cu pas
,
, 
- Limitele admise ale unghiului de rotație a gradientului.
,
- o eroare de calcul dată.
Metoda de coborâre formală
,
și 
- Coordonatele punctelor inițiale și finale ale ultimului segment al coborârii. Același criteriu poate fi utilizat împreună cu controlul valorilor funcției țintă la punctele 
și 
.