Metode de gradient de optimizare neconstrânsă. Metoda gradientului cu constanta m
În cele din urmă, parametrul m poate fi setat constant pe parcursul tuturor iterațiilor. Cu toate acestea, pentru valori mari ale lui m, procesul de căutare poate diverge. O modalitate bună de a selecta m poate fi determinarea lui la prima iterație din condiția unui extremum în direcția gradientului. În iterațiile ulterioare, m rămâne constant. Acest lucru simplifică și mai mult calculele.
De exemplu, pentru funcția la 
cu proiecții de gradient 
determinată de cea mai abruptă metodă de coborâre. Să luăm constanta parametrului la toate iterațiile.
Calculați coordonatele x (1):
Pentru a calcula coordonatele punctului x (2), găsim proiecțiile gradientului în punctul x (1) : , atunci
etc.
Această secvență converge și ea.
Metoda gradientului pas
Această metodă a fost dezvoltată de ingineri și constă în faptul că pasul pentru una dintre variabile este luat constant, iar pentru alte variabile este selectat în funcție de proporționalitatea gradienților punctelor. Așa este scalată suprafața extremă, pentru că Convergența nu este aceeași pentru toate variabilele. Prin urmare, alegând diferiți pași pentru coordonate, ei încearcă să facă ca rata de convergență să fie aproximativ aceeași pentru toate variabilele.
Să fie date o funcție separabilă și un punct inițial . Să stabilim un pas constant de-a lungul coordonatei x 1, fie Dx 1 = 0,2. Pasul de-a lungul coordonatei x2 se găsește din raportul dintre gradienți și pași.
Metoda de relaxare
Algoritmul metodei constă în găsirea direcției axiale de-a lungul căreia funcția obiectiv scade cel mai puternic (la căutarea minimului). Luați în considerare problema de optimizare neconstrânsă
Pentru a determina direcția axială în punctul inițial de căutare, derivatele , , cu privire la toate variabilele independente sunt determinate din regiune. Direcția axială corespunde celei mai mari derivate în valoare absolută.
Fie direcția axială, i.e. 
.
Dacă semnul derivatei este negativ, funcția scade în direcția axei, dacă este pozitivă, în sens invers:
La un moment dat calculează . Se face un pas în direcția descrescătoare a funcției, se determină, iar dacă criteriul este îmbunătățit, pașii continuă până când se găsește valoarea minimă în direcția selectată. În acest moment, derivatele cu privire la toate variabilele sunt determinate din nou, cu excepția celor de-a lungul cărora se realizează coborârea. Se regăsește din nou direcția axială a celei mai rapide scăderi, de-a lungul căreia se fac pași suplimentari etc.
Această procedură se repetă până când se atinge un punct optim, din care nu mai apare nicio scădere atunci când se deplasează pe orice direcție axială. În practică, criteriul de încheiere a căutării este condiția
care se transformă în condiția exactă ca derivatele să fie egale cu zero în punctul extremum. Desigur, condiția (3.7) poate fi utilizată numai dacă optimul se află în intervalul permis de modificări ale variabilelor independente. Dacă optimul se încadrează la limita regiunii , un criteriu ca (3.7) este nepotrivit și, în schimb, ar trebui să se utilizeze pozitivitatea tuturor derivatelor de-a lungul direcțiilor axiale permise.
Algoritmul de coborâre pentru direcția axială selectată poate fi scris după cum urmează:
(3.8)
unde este valoarea variabilei la fiecare pas de coborâre;
Valoarea lui k+1 pas, care poate varia în funcție de numărul pasului:
– funcția semnului z;
Vectorul punctului în care derivatele au fost calculate ultima dată;
Algoritmul cu semnul „+” (3.8) este acceptat la căutarea pentru max I, iar semnul „-” la căutarea pentru min I. Cu cât este mai mic pasul h., cu atât este mai mare numărul de calcule pe calea către optim. Dar dacă valoarea lui h este prea mare aproape de optim, procesul de căutare poate deveni buclă. Aproape de optim, este necesar ca condiția h Cel mai simplu algoritm pentru modificarea pasului h este următorul. La începutul coborârii, se setează un pas egal cu, de exemplu, 10% din intervalul d; se modifică cu acest pas, coborârea se face în direcția selectată până când condiția pentru cele două calcule ulterioare este îndeplinită Dacă condiția este încălcată la orice pas, direcția de coborâre pe axă este inversată și coborârea continuă din ultimul punct cu dimensiunea pasului înjumătățită. Notarea formală a acestui algoritm este următoarea: Ca urmare a utilizării unei astfel de strategii, E de coborâre va scădea în zona optimului în această direcție, iar căutarea în direcție poate fi oprită atunci când E scade. Apoi se găsește o nouă direcție axială și pasul inițial pentru coborârea ulterioară este de obicei mai mic decât pasul făcut de-a lungul direcției axiale anterioare. Natura mișcării la optim în această metodă este prezentată în Figura 3.4. Figura 3.5 – Traiectoria mișcării la optim în metoda relaxării Îmbunătățirea algoritmului de căutare folosind această metodă poate fi realizată prin aplicarea metodelor de optimizare cu un singur parametru. În acest caz, se poate propune o schemă de rezolvare a problemei: Pasul 1. – direcția axială, Pasul 2. – noua directie axiala; Metoda gradientului Această metodă folosește un gradient de funcție. Funcția gradient într-un punct Figura 3.6 – Gradient de funcție Direcția gradientului este direcția în care funcția crește cel mai rapid (cea mai abruptă „pantă” a suprafeței de răspuns). Direcția opusă acesteia (direcția antigradientului) este direcția celei mai rapide scăderi (direcția celei mai rapide „coborâri” a valorilor). Proiectia gradientului pe planul variabilelor este perpendiculara pe tangenta la linia de nivel, i.e. gradientul este ortogonal cu liniile unui nivel constant al funcției obiectiv (Fig. 3.6). Figura 3.7 – Traiectoria mișcării la optim în metodă gradient Spre deosebire de metoda relaxării, în metoda gradientului se fac pași în direcția celei mai rapide scăderi (creșteri) a funcției. Căutarea optimului se realizează în două etape. În prima etapă, se găsesc valorile derivatelor parțiale față de toate variabilele, care determină direcția gradientului în punctul în cauză. În a doua etapă, se face un pas în direcția gradientului la căutarea maximului sau în direcția opusă - la căutarea minimului. Dacă expresia analitică este necunoscută, atunci direcția gradientului este determinată prin căutarea mișcărilor de testare pe obiect. Lasă punctul de plecare. Este dată valoarea de increment, în timp ce . Determinați incrementul și derivata Derivatele în raport cu alte variabile sunt determinate în mod similar. După găsirea componentelor de gradient, mișcările de probă se opresc și încep pașii de lucru în direcția aleasă. Mai mult, cu cât valoarea absolută a vectorului este mai mare, cu atât dimensiunea pasului este mai mare. Când se execută un pas, valorile tuturor variabilelor independente se modifică simultan. Fiecare dintre ele primește un increment proporțional cu componenta de gradient corespunzătoare sau sub formă vectorială unde este o constantă pozitivă; „+” – când se caută max I; „-” – când se caută min I. Algoritmul de căutare a gradientului la normalizarea gradientului (diviziunea după modul) este utilizat în formular Determină dimensiunea pasului în direcția gradientului. Algoritmul (3.10) are avantajul că atunci când se apropie de optim, lungimea pasului scade automat. Și cu algoritmul (3.12), strategia de schimbare poate fi construită indiferent de valoarea absolută a coeficientului. În metoda gradientului, fiecare este împărțit într-o etapă de lucru, după care derivatele sunt calculate din nou, se determină o nouă direcție a gradientului, iar procesul de căutare continuă (Fig. 3.5). Dacă dimensiunea pasului este aleasă prea mică, atunci deplasarea la optim va dura prea mult din cauza necesității de a calcula în atâtea puncte. Dacă pasul este ales prea mare, se poate produce ciclism în zona optimă. Procesul de căutare continuă până când , , devin aproape de zero sau până când limita zonei de setare variabilă este atinsă. Într-un algoritm cu rafinare automată a pasului, valoarea este rafinată astfel încât schimbarea direcției gradientului în punctele învecinate și Criterii pentru încheierea căutării optimului: Unde Căutarea se încheie atunci când una dintre condițiile (3.14) – (3.17) este îndeplinită. Dezavantajul căutării în gradient (precum și metodele discutate mai sus) este că atunci când se folosește, poate fi detectat doar extremul local al funcției. Pentru a găsi alte extreme locale, este necesar să căutați din alte puncte de plecare. Cursul 6. Metode de gradient pentru rezolvarea problemelor de programare neliniară. Întrebări: 1. Caracteristicile generale ale metodelor. 2. Metoda gradientului. 3. Metoda celei mai abrupte coborâri. 4. Metoda Frank-Fulff. 5. Metoda funcţiilor de penalizare. 1. Caracteristicile generale ale metodelor. Metodele gradientului sunt metode aproximative (iterative) pentru rezolvarea unei probleme de programare neliniară și permit rezolvarea aproape oricărei probleme. Cu toate acestea, în acest caz se determină un extremum local. Prin urmare, este recomandabil să folosiți aceste metode pentru a rezolva probleme de programare convexă în care fiecare extremum local este de asemenea global. Procesul de rezolvare a problemei este că, pornind de la un anumit punct x (inițial), se efectuează o tranziție secvențială în direcția gradF(x), dacă se determină punctul maxim și –gradF(x) (antigradient) , dacă se determină punctul minim, până la punctul , care este soluția problemei. În acest caz, acest punct poate fi fie în interiorul intervalului de valori permise, fie la limita sa. Metodele de gradient pot fi împărțite în două clase (grupe). Prima grupă include metode în care toate punctele studiate aparțin regiunii admisibile. Astfel de metode includ: metoda gradientului, cea mai abruptă coborâre, Frank-Wolfe etc. Al doilea grup include metode în care punctele studiate pot să nu aparțină regiunii admisibile. O astfel de metodă comună este metoda funcțiilor de penalizare. Toate metodele funcției de penalizare diferă unele de altele prin modul în care este determinată „penalizarea”. Conceptul principal utilizat în toate metodele de gradient este conceptul de gradient al unei funcții, ca direcție de creștere cea mai rapidă a funcției. Când se determină o soluție folosind metode de gradient, procesul iterativ continuă până când: Fie grad F(x*) = 0, (soluție exactă); Unde 2. Metoda gradientului. Să ne imaginăm o persoană stând pe panta unei râpe care trebuie să coboare (în jos). Direcția cea mai naturală pare să fie spre cea mai abruptă coborâre, adică. direcția (-grad F(x)). Strategia rezultată, numită metoda gradientului, este o secvență de pași, fiecare dintre acestea conținând două operații: a) determinarea direcției celei mai mari abrupte de coborâre (urcare); b) deplasarea în direcția selectată cu un anumit pas. Alegerea terenului potrivit este esențială. Cu cât pasul este mai mic, cu atât rezultatul este mai precis, dar cu atât mai multe calcule. Diverse modificări ale metodei gradientului constau în utilizarea diferitelor metode de determinare a pasului. Dacă la orice pas valoarea lui F(x) nu a scăzut, aceasta înseamnă că punctul minim a fost „depășit”; în acest caz, este necesar să revenim la punctul anterior și să reduceți pasul, de exemplu, la jumătate . Diagrama soluției. aparținând regiunii valabile 3. Selectați pasul h. x (k+1) = x (k) „-” - dacă min. 5. Definiția lui F(x (k +1)) și: Dacă Cometariu. Dacă grad F(x (k)) = 0, atunci soluția va fi exactă. Exemplu. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2 x 1 + x 2 3. Metoda celei mai abrupte coborâri. Spre deosebire de metoda gradientului, in care gradientul se determina la fiecare pas, in metoda de coborare cu cea mai abrupta panta se gaseste la punctul de plecare si miscarea in directia gasita se continua in pasi egali pana cand valoarea functiei scade (creste). Dacă la orice pas F(x) a crescut (a scăzut), atunci mișcarea în această direcție se oprește, ultimul pas este eliminat complet sau pe jumătate și se calculează o nouă valoare a gradientului și o nouă direcție. Diagrama soluției. 1. Definiție x 0 = (x 1,x 2,…,x n), aparținând regiunii admisibile, și F(x 0), k = 0. 2. Definiția grad F(x 0) sau –gradF(x 0). 3. Selectați pasul h. 4. Determinarea punctului următor folosind formula x (k+1) = x (k) „-” - dacă min. 5. Definiția lui F(x (k +1)) și: Dacă Dacă nu: a) când se caută min: - dacă F(x (k +1)) Dacă F(x (k +1)) >F(x (k)) – treceți la pasul 2; b) la căutarea max: - dacă F(x (k +1)) >F(x (k)) – treceți la pasul 4; Dacă F(x(k+1)) Note: 1. Dacă grad F(x (k)) = 0, atunci soluția va fi exactă. 2. Avantajul celei mai abrupte metode de coborâre este simplitatea ei și reducerea calculelor, deoarece gradul F(x) nu se calculează în toate punctele, care important pentru probleme de amploare. 3. Dezavantajul este că pașii trebuie să fie mici pentru a nu ratați punctul optim. Exemplu. F(x) = 3x 1 – 0.2x 1 2 + x 2 - 0.2x 2 2 x 1 + x 2 x 1 + 2x 2 4. Metoda Frank-Wolfe. Metoda este utilizată pentru a optimiza o funcție obiectiv neliniară sub constrângeri liniare. În vecinătatea punctului studiat, funcția obiectiv neliniară este înlocuită cu o funcție liniară și problema se reduce la soluția secvențială a problemelor de programare liniară. Diagrama soluției. 1. Determinarea lui x 0 = (x 1,x 2,…,x n), aparținând regiunii admisibile, și F(x 0), k = 0. 2. Definiția gradului F(x (k)). 3. Construiți o funcție 4. Determinarea max(min)f(x) sub restricții inițiale. Fie acesta punctul z(k). 5. Determinarea etapei de calcul x (k +1) =x (k) + 6. Determinați F(x (k +1)) și verificați necesitatea unor calcule suplimentare: Dacă Dacă nu, atunci treceți la pasul 2. Exemplu. F(x) = 4x 1 + 10x 2 –x 1 2 –x 2 2 x 1 + x 2 x 2 5. Metoda funcţiilor de penalizare. Să fie necesar să găsim F(x 1 ,x 2 ,…,x n) g i (x 1 , x 2 ,…,x n) Funcțiile F și g i – convexe sau concave. Ideea metodei funcției de penalizare este de a găsi valoarea optimă a unei noi funcții obiectiv Q(x) = F(x) + H(x), care este suma funcției obiective inițiale și a unei funcții H(x). ), determinată de un sistem de restricții și numită funcție de penalizare. Funcțiile de penalizare sunt construite astfel încât să asigure fie o întoarcere rapidă în zona permisă, fie imposibilitatea ieșirii din aceasta. Metoda funcției de penalizare reduce problema extremului condiționat la rezolvarea unei secvențe de probleme extreme necondiționate, ceea ce este mai simplu. Există multe moduri de a construi o funcție de penalizare. Cel mai adesea arată astfel: H(x) = Unde Notă: Mai putin Începeți cu soluții mici Folosind funcția de penalizare, aceștia se deplasează succesiv de la un punct la altul până când obțin o soluție acceptabilă. Diagrama soluției. 1. Determinarea punctului de plecare x 0 = (x 1,x 2,…,x n), F(x 0) și k = 0. 2. Selectați pasul de calcul h. 3. Definiți derivatele parțiale 4. Determinați coordonatele următorului punct folosind formula: x j (k +1) 5. Dacă x (k +1) si daca b) dacă grad F(x (k +1)) = 0, atunci s-a găsit o soluție exactă. Dacă x(k+1) Exemplu. F(x) = – x 1 2 – x 2 2 (x 1 -5) 2 +(x 2 -5) 2 Metode de gradient Metodele de optimizare neconstrânsă cu gradient utilizează numai derivatele prime ale funcției obiectiv și sunt metode de aproximare liniară la fiecare pas, i.e. funcția obiectiv la fiecare pas este înlocuită cu un hiperplan tangent la graficul său în punctul curent. La a k-a etapă a metodelor de gradient, trecerea de la punctul Xk la punctul Xk+1 este descrisă prin relația: unde k este dimensiunea pasului, k este vectorul în direcția Xk+1-Xk. Cele mai abrupte metode de coborâre Această metodă a fost luată în considerare și aplicată pentru prima dată de O. Cauchy în secolul al XVIII-lea. Ideea sa este simplă: gradientul funcției obiectiv f(X) în orice punct este un vector în direcția celei mai mari creșteri a valorii funcției. În consecință, antigradientul va fi îndreptat către cea mai mare scădere a funcției și este direcția de coborâre cea mai abruptă. Antigradientul (și gradientul) este ortogonal cu suprafața de nivel f(X) în punctul X. Dacă introducem direcția în (1.2) atunci aceasta va fi direcția de coborâre cea mai abruptă în punctul Xk. Obținem formula pentru trecerea de la Xk la Xk+1: Antigradientul oferă doar direcția de coborâre, dar nu și mărimea pasului. În general, un pas nu oferă un punct minim, așa că procedura de coborâre trebuie aplicată de mai multe ori. La punctul minim, toate componentele gradientului sunt egale cu zero. Toate metodele de gradient folosesc ideea declarată și diferă unele de altele în detalii tehnice: calculul derivatelor folosind o formulă analitică sau o aproximare cu diferențe finite; dimensiunea pasului poate fi constantă, se poate modifica după unele reguli sau poate fi aleasă după aplicarea metodelor de optimizare unidimensională în direcția antigradient etc. și așa mai departe. Nu vom intra în detalii, pentru că... Metoda cea mai abruptă de coborâre nu este în general recomandată ca o procedură serioasă de optimizare. Unul dintre dezavantajele acestei metode este că converge către orice punct staționar, inclusiv un punct de șa, care nu poate fi o soluție. Dar cel mai important lucru este convergența foarte lentă a celei mai abrupte coborâri în cazul general. Ideea este că coborârea este „cea mai rapidă” în sens local. Dacă hiperspațiul de căutare este puternic alungit („gârpă”), atunci antigradientul este îndreptat aproape ortogonal spre fundul „gârpă”, adică. cea mai bună direcție pentru a atinge minimul. În acest sens, o traducere directă a termenului englezesc „steepest descent”, i.e. coborârea de-a lungul pantei cele mai abrupte este mai în concordanță cu starea de fapt decât termenul „cel mai rapid”, adoptat în literatura de specialitate în limba rusă. O modalitate de ieșire în această situație este utilizarea informațiilor furnizate de derivatele secundare parțiale. O altă cale de ieșire este schimbarea scalelor variabilelor. gradient derivat de aproximare liniară Metoda gradientului conjugat Fletcher-Reeves În metoda gradientului conjugat, este construită o secvență de direcții de căutare, care sunt combinații liniare ale direcției curente de coborâre cea mai abruptă și direcțiilor de căutare anterioare, de exemplu. Mai mult, coeficienții sunt aleși astfel încât să se conjugă direcțiile de căutare. S-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-Reeves 1. În X0 se calculează. 2. La pasul k, folosind o căutare unidimensională în direcție, se găsește minimul f(X), care determină punctul Xk+1. unde este o constantă arbitrară. Avantajul algoritmului Fletcher-Reeves este că nu necesită inversarea matricei și economisește memoria computerului, deoarece nu are nevoie de matricele folosite în metodele newtoniene, dar în același timp este aproape la fel de eficient ca algoritmii cvasi-newtonieni. Deoarece direcțiile de căutare sunt conjugate reciproc, atunci funcția pătratică va fi minimizată în cel mult n pași. În cazul general, se folosește o repornire, care vă permite să obțineți rezultatul. Algoritmul Fletcher-Reeves este sensibil la precizia căutării unidimensionale, așa că trebuie utilizat pentru a elimina orice erori de rotunjire care pot apărea. În plus, algoritmul poate eșua în situațiile în care Hessianul devine prost condiționat. Algoritmul nu are nicio garanție de convergență întotdeauna și peste tot, deși practica arată că algoritmul produce aproape întotdeauna rezultate. metode newtoniene Direcția de căutare corespunzătoare coborârii celei mai abrupte este asociată cu o aproximare liniară a funcției obiectiv. Metodele care utilizează derivate secunde au apărut din aproximarea pătratică a funcției obiectiv, adică, la extinderea funcției într-o serie Taylor, termenii de ordinul trei și superior sunt eliminați. unde este matricea hessiană. Minimul din partea dreaptă (dacă există) se realizează în același loc cu minimul formei pătratice. Să notăm formula pentru a determina direcția de căutare: Minimul este atins la Un algoritm de optimizare în care direcția de căutare este determinată din această relație se numește metoda lui Newton, iar direcția se numește direcție newtoniană. În problemele de găsire a minimului unei funcții pătratice arbitrare cu o matrice pozitivă de derivate secunde, metoda lui Newton oferă o soluție într-o singură iterație, indiferent de alegerea punctului de plecare. Clasificarea metodelor newtoniene Metoda lui Newton în sine constă în aplicarea direcției newtoniene o dată pentru a optimiza o funcție pătratică. Dacă funcția nu este pătratică, atunci următoarea teoremă este adevărată. Teorema 1.4. Dacă matricea hessiană a unei funcții neliniare f de formă generală în punctul minim X* este definită pozitiv, punctul de plecare este ales suficient de aproape de X* și lungimile treptelor sunt alese corect, atunci metoda lui Newton converge către X* cu un pătrat. rată. Metoda lui Newton este considerată o metodă de referință; toate procedurile de optimizare dezvoltate sunt comparate cu ea. Cu toate acestea, metoda lui Newton este eficientă numai pentru o matrice Hessiană pozitivă definită și bine condiționată (determinantul său trebuie să fie semnificativ mai mare decât zero, sau mai precis, raportul dintre cele mai mari și mai mici valori proprii trebuie să fie aproape de unu). Pentru a depăși acest neajuns, se folosesc metode newtoniene modificate, folosind direcțiile newtoniene ori de câte ori este posibil și abaterea de la acestea doar când este necesar. Principiul general al modificărilor metodei lui Newton este următorul: la fiecare iterație, o anumită matrice definită pozitivă „asociată” cu este mai întâi construită și apoi calculată folosind formula Deoarece este definit pozitiv, atunci - va fi în mod necesar direcția de coborâre. Procedura de construcție este organizată astfel încât să coincidă cu matricea hessiană dacă este definită pozitivă. Aceste proceduri se bazează pe anumite descompuneri de matrice. Un alt grup de metode, practic nu inferioare ca viteza metodei lui Newton, se bazează pe aproximarea matricei Hessian folosind diferențe finite, deoarece Nu este necesar să folosiți valori exacte ale derivatelor pentru optimizare. Aceste metode sunt utile atunci când calculul analitic al derivatelor este dificil sau pur și simplu imposibil. Astfel de metode se numesc metode Newton discrete. Cheia eficacității metodelor de tip Newton constă în luarea în considerare a informațiilor despre curbura funcției minimizate, conținute în matricea Hessiană și care să permită construirea unor modele pătratice precise local ale funcției obiectiv. Dar este posibil să colectați și să acumulați informații despre curbura unei funcții pe baza observării schimbării gradientului în timpul iterațiilor de coborâre. Metodele corespunzătoare, bazate pe posibilitatea de a aproxima curbura unei funcții neliniare fără a-și forma în mod explicit matricea hessiană, se numesc metode cvasi-newtoniene. Rețineți că atunci când se construiește o procedură de optimizare de tip newtonian (inclusiv cvasi-newtonian), este necesar să se țină cont de posibilitatea apariției unui punct de șa. În acest caz, vectorul celei mai bune direcții de căutare va fi întotdeauna îndreptat către punctul de șa, în loc să se îndepărteze de acesta în direcția în jos. Metoda Newton-Raphson Această metodă constă în utilizarea în mod repetat a direcției newtoniene la optimizarea funcțiilor care nu sunt pătratice. Formula iterativă de bază pentru optimizarea multidimensională se foloseşte în această metodă la alegerea direcţiei de optimizare din relaţie Lungimea reală a pasului este ascunsă în direcția newtoniană nenormalizată. Deoarece această metodă nu necesită valoarea funcției obiectiv în punctul curent, uneori este numită o metodă de optimizare indirectă sau analitică. Capacitatea sa de a determina minimul unei funcții pătratice într-un singur calcul pare extrem de atractivă la prima vedere. Cu toate acestea, acest „calcul unic” necesită costuri semnificative. În primul rând, este necesar să se calculeze n derivate parțiale de ordinul întâi și n(n+1)/2 - din al doilea. În plus, matricea Hessiană trebuie inversată. Acest lucru necesită aproximativ n3 operații de calcul. Cu același cost, metodele de direcție conjugată sau metodele de gradient conjugat pot dura aproximativ n pași, adică. obține aproape același rezultat. Astfel, iterația metodei Newton-Raphson nu oferă avantaje în cazul unei funcții pătratice. Dacă funcția nu este pătratică, atunci Strategia în sine nu distinge care punct staționar (minim, maxim, punct de șa) se apropie de căutare și nu se fac calcule ale valorilor funcției obiectiv, care ar putea fi utilizate pentru a urmări dacă funcția crește. Aceasta înseamnă că totul depinde de ce punct staționar este punctul de pornire al căutării în zona de atracție. Strategia Newton-Raphson este rareori folosită singură, fără modificări de un fel sau altul. metode Pearson Pearson a propus mai multe metode care aproximează inversul Hessian fără a calcula în mod explicit derivatele secunde, i.e. prin observarea schimbărilor în direcţia antigradientului. În acest caz, se obțin direcții conjugate. Acești algoritmi diferă doar în detalii. Vă prezentăm pe cele care sunt cele mai utilizate în domeniile aplicate. Algoritmul Pearson nr. 2. În acest algoritm, Hessianul invers este aproximat de matricea Hk, calculată la fiecare pas folosind formula O matrice simetrică definită pozitivă arbitrară este aleasă ca matrice inițială H0. Acest algoritm Pearson duce adesea la situații în care matricea Hk devine prost condiționată, și anume, începe să oscileze, oscilând între definit pozitiv și definit nepozitiv, în timp ce determinantul matricei este aproape de zero. Pentru a evita această situație, este necesară redefinirea matricei la fiecare n pași, echivalând-o cu H0. Algoritmul Pearson nr. 3. În acest algoritm, matricea Hk+1 este determinată din formulă Hk+1 = Hk + Traiectoria de coborâre generată de algoritm este similară cu comportamentul algoritmului Davidon-Fletcher-Powell, dar pașii sunt puțin mai scurti. Pearson a propus, de asemenea, o variație a acestui algoritm cu resetarea ciclică a matricei. Algoritm proiectiv Newton-Raphson Pearson a propus ideea unui algoritm în care matricea este calculată din relație H0=R0, unde matricea R0 este aceeași cu matricele inițiale din algoritmii anteriori. Când k este un multiplu al numărului de variabile independente n, matricea Hk este înlocuită cu matricea Rk+1, calculată ca sumă Mărimea Hk(f(Xk+1) - f(Xk)) este proiecția vectorului de creștere a gradientului (f(Xk+1) - f(Xk)), ortogonală cu toți vectorii de creștere a gradientului din pașii anteriori. După fiecare n pași, Rk este o aproximare a Hessianului invers H-1(Xk), deci, de fapt, se efectuează o căutare Newton (aproximativă). Metoda Davidon-Fletcher-Powell Această metodă are alte denumiri – metoda metrică variabilă, metoda cvasi-Newton, deoarece el folosește ambele abordări. Metoda Davidon-Fletcher-Powell (DFP) se bazează pe utilizarea direcțiilor newtoniene, dar nu necesită calculul inversului Hessian la fiecare pas. Direcția de căutare la pasul k este direcția unde Hi este o matrice simetrică definită pozitivă care este actualizată la fiecare pas și în limită devine egală cu Hessianul invers. Matricea de identitate este de obicei aleasă ca matrice inițială H. Procedura DFT iterativă poate fi reprezentată după cum urmează: 3. O căutare unidimensională (de obicei interpolare cubică) de-a lungul direcției determină k, ceea ce minimizează funcția. 4. Baza. 5. Baza. 6. Este determinat. Dacă Vk sau sunt suficient de mici, procedura se termină. 9. Măriți k cu unu și reveniți la pasul 2. Metoda este eficientă în practică dacă eroarea în calculele gradientului este mică și matricea Hk nu devine prost condiționată. Matricea Ak asigură convergența lui Hk la G-1, matricea Bk asigură definiția pozitivă a lui Hk+1 în toate etapele și exclude H0 în limită. În cazul unei funcţii pătratice acestea. Algoritmul DFP folosește direcții conjugate. Astfel, metoda DFT folosește atât ideile abordării newtoniene, cât și proprietățile direcțiilor conjugate, iar la minimizarea funcției pătratice, converge în cel mult n iterații. Dacă funcția optimizată are o formă apropiată de o funcție pătratică, atunci metoda DFT este eficientă datorită bunei sale aproximări G-1 (metoda lui Newton). Dacă funcția obiectiv are o formă generală, atunci metoda DFT este eficientă datorită utilizării direcțiilor conjugate. Metoda de coborâre în gradient. Direcția de coborâre cea mai abruptă corespunde direcției de cea mai mare scădere a funcției. Se știe că direcția de creștere cea mai mare într-o funcție a două variabile u = f(x, y) este caracterizată de gradientul său: unde e1, e2 sunt vectori unitari (orturi) în direcția axelor de coordonate. În consecință, direcția opusă gradientului va indica direcția de cea mai mare scădere a funcției. Sunt numite metode bazate pe alegerea unei căi de optimizare folosind un gradient gradient. Ideea metodei de coborâre a gradientului este următoarea. Selectarea unui punct de plecare Calculăm gradientul funcției luate în considerare în ea. Facem un pas în direcția opusă gradientului: Procesul continuă până când se obține valoarea minimă a funcției obiectiv. Strict vorbind, sfarsitul cautarii va avea loc atunci cand deplasarea din punctul obtinut cu orice pas duce la o crestere a valorii functiei obiectiv. Dacă minimul funcției este atins în interiorul regiunii luate în considerare, atunci în acest moment gradientul este zero, ceea ce poate servi și ca semnal despre sfârșitul procesului de optimizare. Metoda coborârii în gradient are același dezavantaj ca și metoda coborârii în coordonate: în prezența ravenelor la suprafață, convergența metodei este foarte lentă. În metoda descrisă, este necesar să se calculeze gradientul funcției obiectiv f(x) la fiecare pas de optimizare: Formulele pentru derivate parțiale pot fi obținute în mod explicit numai în cazul în care funcția obiectiv este specificată analitic. În caz contrar, aceste derivate sunt calculate folosind diferențierea numerică: Când se utilizează coborârea gradientului în probleme de optimizare, cea mai mare parte a calculului cade de obicei pe calcularea gradientului funcției obiectiv în fiecare punct al traiectoriei de coborâre. Prin urmare, este recomandabil să reduceți numărul de astfel de puncte fără a compromite soluția în sine. Acest lucru se realizează în unele metode care sunt modificări ale coborârii gradientului. Una dintre ele este cea mai abruptă metodă de coborâre. Conform acestei metode, după determinarea în punctul inițial a direcției opuse gradientului funcției obiectiv, se rezolvă o problemă de optimizare unidimensională prin minimizarea funcției pe această direcție. Și anume, funcția este minimizată: Pentru a minimiza Cea mai abruptă metodă de coborâre pentru cazul unei funcții a două variabile z = f(x,y). În primul rând, este ușor de arătat că gradientul funcției este perpendicular pe tangenta la linia de nivel într-un punct dat. În consecință, în metodele cu gradient, coborârea are loc de-a lungul liniei normale spre nivel. În al doilea rând, în punctul în care este atins minimul funcției obiectiv de-a lungul unei direcții, derivata funcției de-a lungul acestei direcții devine zero. Dar derivata funcției este zero în direcția tangentă la linia de nivel. Rezultă că gradientul funcției obiectiv în noul punct este perpendicular pe direcția optimizării unidimensionale la pasul anterior, adică coborârea în două trepte succesive este efectuată în direcții reciproc perpendiculare.
(3.9)
; , Dacă ;
este un vector ale cărui proiecții pe axele de coordonate sunt derivatele parțiale ale funcției în raport cu coordonatele (Fig. 6.5)
.
, (3.10)
, (3.11)
; (3.12)
(3.13)
; (3.16)
; (3.17)
– norma vectoriala.
- doua puncte consecutive, 
- un număr mic care caracterizează acuratețea soluției.
, solutie gasita;
min,
2.x 1 
0, x 2 
0,
= 0,1.
h grad F(x (k)), „+” - dacă max,
, solutie gasita;
max,
7, x 1 
0,
10, x 2 
0.
(min – „-”;max – „+”).
(k) (z (k) –x (k)), unde 
(k) – treaptă, coeficient, 0 
1.
(k) se alege astfel încât valoarea funcției F(x) să fie max (min) în punctul x (k +1). Pentru a face acest lucru, rezolvați ecuația 
și alegeți cea mai mică (mai mare) dintre rădăcini, dar 0 
1.
sau grad F(x (k +1)) = 0, atunci se găsește soluția;
max,
4, x 1 
0,
2, x 2 
0.
max(min),
b i , i = 
, x j 
0, j = 
.
,
- unele Const pozitive.
, cu cât se găsește mai repede soluția, cu atât precizia scade;
și creșteți-le în etapele ulterioare.
Și 
.
.
Zona valabila, verifica:
- a fost găsită o soluție, dacă nu, treceți la pasul 2.
Regiune tolerantă, setați o nouă valoare 
și treceți la pasul 4.
max,
8, x 1 
0, x 2 
0.
Puteți utiliza una dintre metodele de optimizare unidimensională. Vă puteți deplasa pur și simplu în direcția opusă gradientului, făcând nu un pas, ci mai mulți pași până când funcția obiectiv încetează să scadă. La noul punct găsit, se determină din nou direcția de coborâre (folosind gradientul) și se caută un nou punct de minim al funcției obiectiv etc. În această metodă, coborârea are loc în pași mult mai mari, iar gradientul funcției se calculează într-un număr mai mic de puncte. Diferența este că aici direcția optimizării unidimensionale este determinată de gradientul funcției obiectiv, în timp ce coborârea coordonatelor este efectuată la fiecare pas de-a lungul uneia dintre direcțiile de coordonate.
