Cea mai abruptă metodă de coborâre este o metodă de gradient cu trepte variabile. La fiecare iterație, valoarea pasului k este aleasă din condiția minimului funcției f(x) pe direcția de coborâre, i.e.
Această condiție înseamnă că mișcarea de-a lungul antigradientului are loc atâta timp cât valoarea funcției f (x) scade. Din punct de vedere matematic, la fiecare iterație, este necesar să se rezolve problema minimizării unidimensionale în raport cu funcția
()=f(x(k)-f(x(k)))
Folosim metoda secțiunii de aur pentru aceasta.
Algoritmul celei mai abrupte metode de coborâre este următorul.
Sunt date coordonatele punctului de plecare x (0).
În punctul x (k) , k = 0, 1, 2, ... se calculează valoarea gradientului f (x (k)).
Mărimea pasului k este determinată de minimizarea unidimensională în raport cu funcția
()=f(x(k)-f(x(k))).
Coordonatele punctului x (k) sunt determinate:
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Condiția pentru oprirea procesului iterativ este verificată:
||f(x(k+1))|| .
Dacă este satisfăcut, calculele se opresc. În caz contrar, se realizează trecerea la pasul 1. Interpretarea geometrică a metodei celei mai abrupte de coborâre este prezentată în fig. unu.
Orez. 2.1. Schema bloc a celei mai abrupte metode de coborâre.
Implementarea metodei în program:
Cea mai abruptă metodă de coborâre.
Orez. 2.2. Implementarea celei mai abrupte metode de coborâre.
Concluzie: În cazul nostru, metoda converge în 7 iterații. Punctul A7 (0,6641; -1,3313) este un punct extremum. Metoda direcțiilor conjugate. Pentru funcțiile pătratice, puteți crea o metodă de gradient, în care timpul de convergență va fi finit și egal cu numărul de variabile n.
Numim o direcție și conjugăm cu privire la o matrice Hess definită pozitivă H dacă:
Atunci, adică. Prin urmare, cu unitatea H, direcția conjugată înseamnă perpendiculara lor. În cazul general, H este netrivial. În cazul general, conjugarea este aplicarea matricei Hess la un vector - înseamnă rotația acestui vector cu un anumit unghi, extinderea sau compresia acestuia.
Și acum un vector este ortogonal cu un vector, adică conjugarea nu este ortogonalitatea vectorilor, ci ortogonalitatea unui vectorat.i.i rotit.
Orez. 2.3. Schema bloc a metodei direcțiilor conjugate.
Implementarea metodei în program: Metoda direcțiilor conjugate.
Orez. 2.4. Implementarea metodei direcțiilor conjugate.
Orez. 2.5. Graficul metodei direcțiilor conjugate.
Concluzie: Punctul A3 (0,6666; -1,3333) a fost găsit în 3 iterații și este punctul extremum.
3. Analiza metodelor de determinare a valorii minime, maxime a funcției în prezența restricțiilor
Amintiți-vă că problema generală a optimizării condiționate arată astfel
f(x) ® min, x О W,
unde W este o submulțime proprie a lui R m . O subclasă de probleme cu constrângeri de tip egalitate se distinge prin faptul că mulțimea este dată de constrângeri de forma
f i (x) = 0, unde f i: R m ®R (i = 1, …, k).
AstfelW = (x О R m: f i (x) = 0, i = 1, …, k).
Ne va fi convenabil să scriem indicele „0” pentru funcția f. Astfel, problema de optimizare cu constrângeri de tip egalitate este scrisă ca
f 0 (x) ® min, (3,1)
f i (x) = 0, i = 1, …, k. (3,2)
Dacă notăm acum cu f o funcție pe R m cu valori în R k , a cărei notație de coordonate are forma f(x) = (f 1 (x), …, f k (x)), atunci (3.1)–( 3.2) se poate scrie și sub formă
f 0 (x) ® min, f(x) = Q.
Din punct de vedere geometric, problema constrângerilor de tip egalitate este problema găsirii punctului cel mai de jos al graficului funcției f 0 peste varietatea (vezi Fig. 3.1).
Punctele care satisfac toate restricțiile (adică punctele mulțimii ) sunt de obicei numite admisibile. Un punct admisibil x* se numește minim condiționat al funcției f 0 sub constrângerile f i (x) = 0, i = 1, ..., k (sau o soluție a problemei (3.1)–(3.2)), dacă pentru toate punctele admisibile x f 0 (x *) f 0 (x). (3,3)
Dacă (3.3) este satisfăcută numai pentru x admisibil situat în vreo vecinătate V x * a punctului x*, atunci se vorbește de un minim condiționat local. Conceptele de minime locale și globale stricte condiționate sunt definite într-un mod natural.
Formularea problemei
Lasă funcția f(x) R n
Necesar f(x) X = Rn
Strategia de căutare
x k
} , k = 0,1,...,
astfel încât 
, k = 0,1,...
. puncte de succesiune ( x k
) se calculează conform regulii
unde este punctul x 0 este setat de utilizator; dimensiunea pasului t k definit pentru fiecare valoare k din starea
Problema (3) poate fi rezolvată folosind condiția minimă necesară urmată de verificarea condiției minime suficiente. Acest mod poate fi folosit fie pentru o funcție destul de simplă de minimizat, fie pentru o aproximare preliminară a unei funcții destul de complexe 
polinom P(tk)
(de obicei de gradul al doilea sau al treilea), iar apoi condiția este înlocuită cu condiția , iar condiția cu condiția 
Construirea unei secvențe ( x k )
se termină la punct x k
, pentru care , unde ε
este un număr mic pozitiv dat, sau k ≥ M
, Unde M
- numărul limitator de iterații, sau cu două îndepliniri simultane a două inegalități 
, 
Unde ε 2
este un mic număr pozitiv. Întrebarea este dacă un punct x k
să fie considerată ca aproximarea găsită a punctului minim local dorit X *
, se rezolvă prin cercetări suplimentare.
Interpretarea geometrică a metodei pt n=2 în fig. patru.
Metoda coborării coordonate
Formularea problemei
Lasă funcția f(x) , mărginit de jos pe platou R n și având derivate parțiale continue în toate punctele sale.
f(x) pe setul de soluţii admisibile X = Rn , adică găsi un punct astfel încât
Strategia de căutare
Strategia de rezolvare a problemei constă în construirea unei secvențe de puncte ( x k
} , k = 0,1,...,
astfel încât , k = 0,1,...
. puncte de succesiune ( x k
) se calculează pe cicluri conform regulii
(4)
Unde j - numărul ciclului de calcul; j = 0,1,2,...; k - numărul de iterație în interiorul buclei, k = 0,1,...,n - 1; e k +1, k = 0,l,...,n - 1 - vector unitar, (k+1) -a cărei proiecție este egală cu 1; punct x 00 stabilite de utilizator, dimensiunea pasului t k selectat din condiție
sau 
.
Dacă condiția selectată la curent t k
nu se execută, pasul este înjumătățit și punctul 
este recalculat. Este ușor de observat că, pentru un j fix, într-o iterație cu numărul k
doar proiecția unui punct se modifică x jk
, care are numărul k + 1
, iar pe parcursul întregului ciclu cu numărul j
, adică incepand cu k = 0
și sfârșitul k=n-1
, toate n proiecțiile punctului se modifică x j0
. După acest punct x jn
atribuit un număr x j + 1,0
, și este luat ca punct de plecare pentru calcule în j + 1
ciclu. Calculul se termină la punct x jk
atunci când cel puțin unul dintre cele trei criterii de încheiere a numărării este îndeplinit: 
, sau , sau dubla îndeplinire a inegalităţilor .
Punctele obținute în urma calculelor pot fi scrise ca elemente ale șirului (xl), Unde l=n*j+k - numărul de serie al punctului,
Interpretarea geometrică a metodei pentru n = 2 este prezentată în fig. 5.
4. Metoda Frank-Wolfe .
Să fie necesar să se găsească valoarea maximă a funcției concave
În condiții
O trăsătură caracteristică a acestei probleme este că sistemul său de constrângeri conține doar inegalități liniare. Această caracteristică stă la baza înlocuirii funcției obiectiv neliniare cu una liniară în vecinătatea punctului studiat, datorită căreia soluția problemei inițiale se reduce la o soluție secvențială a problemelor de programare liniară.
Procesul de găsire a unei soluții la problemă începe cu determinarea unui punct care aparține zonei de soluții admisibile pentru
270
dachas. Să fie acesta ideea X(k)
atunci în acest moment se calculează gradientul funcției (57).
Și construiți o funcție liniară
Atunci valoarea maximă a acestei funcții se găsește sub constrângerile (58) și (59). Lasă soluția acestei probleme să fie determinată de punct Z(k)
. Apoi coordonatele punctului X(k+1)
:
Unde λ k - un număr, numit pas de calcul și încheiat între zero și unu (0<λ k < 1). Это число λ k luați în mod arbitrar sau determinați
astfel încât valoarea funcţiei în punct X (k + 1) f(X (k + 1)) în funcție de λ k , a fost maximul. Pentru a face acest lucru, trebuie să găsiți o soluție pentru ecuație și să alegeți cea mai mică rădăcină a acesteia. Dacă valoarea sa este mai mare decât unu, atunci λ k=1 . După determinarea numărului λ k afla coordonatele unui punct X(k+1) calculați valoarea funcției obiectiv din ea și aflați necesitatea trecerii la un nou punct X(k+2) . Dacă există o astfel de nevoie, atunci calculați la punctul X(k+1) gradient al funcției obiectiv, mergeți la problema de programare liniară corespunzătoare și găsiți soluția acesteia. Determinați coordonatele punctului și X(k+2) și investigați necesitatea unor calcule suplimentare. După un număr finit de pași, soluția problemei inițiale se obține cu precizia necesară.
Deci, procesul de găsire a unei soluții la problema (57) - (59) prin metoda Frank-Wolfe include următorii pași:
1. Determinați soluția inițială fezabilă a problemei.
2. Aflați gradientul funcției (57) în punctul soluției fezabile.
3. Construiți funcția (60) și găsiți valoarea sa maximă în condițiile (58) și (59).
4. Determinați pasul de calcul.
5. Utilizând formulele (61), se găsesc componentele unei noi soluții fezabile.
6. Verificați necesitatea trecerii la următoarea soluție acceptabilă. Dacă este necesar, treceți la etapa 2, altfel se găsește o soluție acceptabilă la problema inițială.
Metoda funcțiilor de penalizare.
Luați în considerare problema determinării valorii maxime a unei funcții concave
f (x 1, x 2, .... x n) in conditii g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Unde g i (x 1, x 2, .... x n) sunt funcții convexe.
În loc să rezolvați direct această problemă, găsiți valoarea maximă a funcției F (x 1, x 2, ...., x n) \u003d f (x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) care este suma funcției obiective a problemei și a unei anumite funcții
H(x 1, x 2, ...., x n), determinată de sistemul de constrângeri și numită functia de penalizare. Funcția de penalizare poate fi construită în diferite moduri. Cu toate acestea, cel mai adesea ia forma
DAR a i > 0
- unele numere constante reprezentând coeficienţi de greutate.
Folosind o funcție de penalizare, se trece succesiv de la un punct la altul până când se obține o soluție acceptabilă. În acest caz, coordonatele punctului următor sunt găsite prin formulă
Din ultima relație rezultă că, dacă punctul anterior se află în zona soluțiilor fezabile ale problemei inițiale, atunci al doilea termen dintre paranteze drepte este egal cu zero și trecerea la următorul punct este determinată numai de gradientul de functia obiectiv. Dacă punctul indicat nu aparține regiunii soluțiilor fezabile, atunci datorită acestui termen, la iterațiile ulterioare, se realizează o întoarcere în regiunea soluțiilor fezabile.
solutii. Totuși, cu atât mai puțin un i
, cu cât se găsește mai rapid o soluție acceptabilă, dar acuratețea determinării acesteia scade. Prin urmare, procesul iterativ este de obicei început la valori relativ mici un i
și, continuând-o, aceste valori cresc treptat.
Deci, procesul de găsire a unei soluții la problema programării convexe prin metoda funcției de penalizare include următorii pași:
1. Determinați soluția inițială fezabilă.
2. Selectați pasul de calcul.
3. Pentru toate variabilele se găsesc derivate parțiale ale funcției obiectiv și funcții care determină aria soluțiilor admisibile ale problemei.
4. Prin formula (72) găsiți coordonatele punctului care definește o posibilă nouă soluție a problemei.
5. Verificați dacă coordonatele punctului găsit satisfac sistemul de constrângeri al problemei. Dacă nu, atunci treceți la pasul următor. Dacă coordonatele punctului găsit determină o soluție fezabilă a problemei, atunci se examinează necesitatea de a trece la următoarea soluție fezabilă. Dacă este necesar, treceți la etapa 2, altfel se găsește o soluție acceptabilă la problema inițială.
6. Setați greutăți și treceți la pasul 4.
Metoda Arrow-Hurwitz.
Când am găsit o soluție la problemele de programare neliniară folosind metoda funcției de penalizare, am ales valorile un i , în mod arbitrar, ceea ce a dus la fluctuații semnificative ale distanței punctelor determinate din regiunea soluțiilor fezabile. Acest dezavantaj este eliminat prin rezolvarea problemei prin metoda Arrow-Hurwitz, conform căreia la pasul următor al numărului a i (k) calculate după formula
Ca valori inițiale a i (0) ia numere arbitrare nenegative.
EXEMPLU DE SOLUȚIE
Exemplul 1.
Găsiți minimul local al unei funcții
Definirea punctului x k
1 set .
2. Pune k = 0 .
treizeci . Calcula
40 . Calcula 
. Să trecem la pasul 5.
cincizeci . Să verificăm starea 
. Să trecem la pasul 6.
60 . Hai să setăm t 0 \u003d 0,5 .
70. Calcula
80. Să comparăm 
. Avem 
. Concluzie: condiție pentru k = 0
nu este efectuată. Hai să setăm t0 = 0,25
, trecem la repetarea pașilor 7, 8.
701 . Să calculăm.
801 . Să comparăm f (x 1) și f (x 0) . Concluzie: f(x1)< f (x 0) . Să trecem la pasul 9.
90. Calcula
Concluzie: credem k=1 și treceți la pasul 3.
3 1 . Calcula
4 1 . Calcula 
. Să trecem la pasul 5.
5 1 . Să verificăm starea k ≥ M: k = 1< 10 = M . Să trecem la pasul 6.
6 1 . Hai să setăm t 1 \u003d 0,25.
7 1 . Calcula
8 1 . Să comparăm f (x 2) cu f (x 1) . Concluzie: f (x 2)< f (х 1). Să trecem la pasul 9.
9 1 . Calcula
Concluzie: credem k = 2 și treceți la pasul 3.
3 2 . Calcula
4 2 . Să calculăm. Să trecem la pasul 5.
5 2 . Să verificăm starea k ≥ M : k = 2< 10 = М , treceți la pasul 6.
6 2 . Hai să setăm t2 =0,25 .
7 2 . Calcula
8 2 . Să comparăm f (x 3) și f (x 2) . Concluzie: f (x 3)< f (х 2) .Mergeți la pasul 9.
9 2 . Calcula 
Concluzie: credem k = 3 și treceți la pasul 3.
3 3 . Calcula
4 3 . Să calculăm. Să trecem la pasul 5.
5 3 . Să verificăm starea k ≥ M : k = 3<10 = М , treceți la pasul 6.
6 3 . Hai să setăm t 3 \u003d 0,25.
7 3 . Calcula
8 3 . Să comparăm f (x 4) și f (x 3) : f (x 4)< f (х 3) .
9 3 . Calcula 
Condițiile sunt îndeplinite la k = 2,3 . Calcul
terminat. Punct găsit
Pe fig. Cele 3 puncte obținute sunt legate printr-o linie punctată.
II. Analiza punctelor x 4 .
Funcţie 
este de două ori diferențiabilă, așa că verificăm condițiile suficiente pentru minimul în punct x 4
. Pentru a face acest lucru, analizăm matricea Hessiană.
Matricea este constantă și este definită pozitivă (adică . H > 0
), deoarece ambele sale minore unghiulare și sunt pozitive. De aici și ideea 
este aproximarea găsită a punctului minim local și valoarea 
este aproximarea găsită a valorii f(x*)=0
. Rețineți că condiția H > 0
, este simultan o condiție pentru convexitatea strictă a funcției 
. Prin urmare, se găsesc aproximări ale punctului minim global f(x)
iar valoarea sa cea mai mică pe R2
. ■
Exemplul 2
Găsiți minimul local al unei funcții
I. Determinarea unui punct x k, în care cel puțin unul dintre criteriile de reziliere este îndeplinit.
1 set .
Găsiți gradientul unei funcții într-un punct arbitrar
2. Pune k = 0 .
treizeci . Calcula
40 . Calcula . Să trecem la pasul 5.
cincizeci . Să verificăm starea 
. Să trecem la pasul 6.
6°. Următorul punct se găsește prin formulă
Să substituim expresiile obținute pentru coordonatele din
Găsiți minimul funcției f(t0) pe t0 folosind condițiile necesare pentru un extremum necondiționat:
De aici t0 = 0,24
. pentru că 
, valoarea pasului găsit oferă minimul funcției f(t0)
pe t0
.
Să definim 
70. Sa gasim
8°. Calcula
Concluzie: credem k = 1 și treceți la pasul 3.
3 1 . Calcula
4 1 . Calcula 
5 1 . Să verificăm starea k ≥ 1: k = 1< 10 = М.
6 1 . Să definim
7 1 . Sa gasim 
:
8 1 . Calcula
Noi credem k = 2 și treceți la pasul 3.
3 2 . Calcula
4 2 . Calcula
5 2 . Să verificăm starea k ≥ M: k = 2< 10 = M .
6 2 . Să definim
7 2 . Sa gasim 
8 2 . Calcula
Noi credem k=3 și treceți la pasul 3.
3 3 . Calcula
4 3 . Să calculăm.
Calculul s-a terminat. Punct găsit
II. Analiza punctelor x 3 .
În Exemplul 1.1 (Capitolul 2 §1) s-a arătat că funcţia f(x) este strict convexă și, prin urmare, în punctele3 este aproximarea găsită a punctului minim global X* .
Exemplul 3
Găsiți minimul local al unei funcții
I. Determinarea unui punct x jk , în care cel puțin unul dintre criteriile de reziliere este îndeplinit.
1 set
Găsiți gradientul unei funcții într-un punct arbitrar 
2. Setați j = 0.
treizeci . Să verificăm îndeplinirea condiției
40 . Hai să setăm k = 0.
cincizeci . Să verificăm îndeplinirea condiției
60 . Calcula
70. Să verificăm starea 
80. Hai să setăm
90. Calcula 
, Unde
100 . Să verificăm starea
Concluzie: presupunem și trecem la pasul 9.
9 01 . Calcula x 01 pas cu pas
1001 . Să verificăm starea 
110 . Să verificăm condițiile
Noi credem k=1 și treceți la pasul 5.
5 1 . Să verificăm starea
6 1 . Calcula
7 1 . Să verificăm starea
8 1 . Hai să setăm
9 1 . Calcula
10 1 . Să verificăm starea 
:
11 1 . Să verificăm condițiile
Noi credem k = 2 , treceți la pasul 5.
5 2 . Să verificăm starea. Setați, treceți la pasul 3.
3 1 . Să verificăm starea
4 1 . Hai să setăm k = 0.
5 2 . Să verificăm starea
6 2 . Calcula
7 2 . Să verificăm starea
8 2 . Hai să setăm
9 2 . Calcula
10 2 . Să verificăm starea 
11 2 . Să verificăm condițiile
Noi credem k=1 și treceți la pasul 5.
5 3 . Să verificăm starea
6 3 . Calcula
7 3 . Să verificăm condițiile
8 3 . Hai să setăm
9 3 . Calcula
10 3 . Să verificăm starea 
11 3 . Să verificăm condițiile
Hai să setăm k = 2 și treceți la pasul 5.
5 4 . Să verificăm starea 
Noi credem j \u003d 2, x 20 \u003d x 12 și treceți la pasul 3.
3 2 . Să verificăm starea
4 2 . Hai să setăm k=0 .
5 4 . Să verificăm starea
6 4 . Calcula
7 4 . Să verificăm starea
8 4 . Hai să setăm
9 4 . Calcula
10 4 . Să verificăm starea, treceți la pasul 11.
11 4 . Să verificăm condițiile
Condițiile sunt îndeplinite în două cicluri consecutive cu numere j = 2 și j -1= 1 . Calcul finalizat, punct găsit
Pe fig. 6, punctele obținute sunt conectate printr-o linie punctată.
În metoda coborării coordonatelor, coborâm de-a lungul unei linii întrerupte constând din segmente de linie paralele cu axele de coordonate.
II. Analiza punctuala x21.
Exemplul 1.1 a arătat că funcția f(x)
este strict convex, are un singur minim și, prin urmare, un punct 
este aproximarea găsită a punctului minim global.
În toate metodele de gradient de mai sus, succesiunea de puncte ( x k ) converge către un punct staționar al funcției f(x) sub propoziţii destul de generale despre proprietăţile acestei funcţii. În special, teorema este adevărată:
Teorema. Dacă funcția f (x) este mărginită de jos, gradientul ei satisface condiția Lipschitz () și alegerea valorii t n produs prin una dintre metodele descrise mai sus, apoi indiferent de punctul de plecare x 0 :
la .
În implementarea practică a schemei
k=1, 2, …n.
iterațiile se opresc dacă pentru toate i , i = 1, 2, ..., n , condiții de tip
,
unde este un număr dat care caracterizează acuratețea găsirii minimului.
În condițiile teoremei, metoda gradientului asigură convergența în funcție sau la cea mai mică limită inferioară (dacă funcția f(x) nu are minim; orez. 7), sau la valoarea funcției într-un punct staționar, care este limita secvenței (x la ). Este ușor să veniți cu exemple când se realizează o șa în acest moment, și nu un minim. În practică, metodele de coborâre în gradient ocolesc cu încredere punctele de șa și găsesc minime ale funcției obiectiv (în cazul general, minime locale).
CONCLUZIE
Exemplele de metode de gradient de optimizare neconstrânsă au fost luate în considerare mai sus. În urma muncii depuse, se pot trage următoarele concluzii:
1. Problemele mai mult sau mai puțin complexe ale găsirii unui extremum în prezența restricțiilor necesită abordări și metode speciale.
2. Mulți algoritmi pentru rezolvarea problemelor cu restricții includ minimizarea fără restricții ca o anumită etapă.
3. Diferitele metode de coborâre diferă unele de altele în modul de alegere a direcției de coborâre și a lungimii pasului de-a lungul acelei direcții.
4. Până acum nu există o astfel de teorie care să țină cont de orice trăsături ale funcțiilor care descriu formularea problemei. Ar trebui să se acorde preferință metodelor care sunt mai ușor de gestionat în procesul de rezolvare a problemei.
Problemele reale de optimizare aplicată sunt foarte complexe. Metodele moderne de optimizare nu fac întotdeauna față rezolvării problemelor reale fără ajutorul uman.
BIBLIOGRAFIE
1. Kosorukov O.A. Cercetarea operațională: un manual. 2003
2. Pantleev A.V. Metode de optimizare în exemple și sarcini: manual. Beneficiu. 2005
3. Shishkin E.V. Cercetare operațională: manual. 2006
4. Akulich I.L. Programare matematică în exemple și sarcini. 1986
5. Wentzel E.S. Cercetare operațională. 1980
6. Venttsel E.S., Ovcharov L.A. Teoria probabilității și aplicațiile sale de inginerie. 1988
©2015-2019 site
Toate drepturile aparțin autorilor lor. Acest site nu pretinde autor, dar oferă o utilizare gratuită.
Data creării paginii: 2017-07-02
Fig.3. Interpretarea geometrică a celei mai abrupte metode de coborâre. La fiecare pas, se alege astfel încât următoarea iterație să fie punctul minim al funcției pe raza L.
Această variantă a metodei gradientului se bazează pe alegerea pasului din următorul considerent. Din punctul ne vom deplasa în direcția antigradientului până când ajungem la minimul funcției f în această direcție, adică pe raza:
Cu alte cuvinte, este ales astfel încât următoarea iterație să fie punctul minim al funcției f pe raza L (vezi Fig. 3). Această variantă a metodei gradientului se numește metoda cea mai abruptă de coborâre. Rețineți, apropo, că în această metodă direcțiile treptelor adiacente sunt ortogonale.
Cea mai abruptă metodă de coborâre necesită rezolvarea unei probleme de optimizare unidimensională la fiecare pas. Practica arată că această metodă necesită adesea mai puține operații decât metoda gradientului cu un pas constant.
În situația generală, însă, rata teoretică de convergență a metodei celei mai abrupte coborâre nu este mai mare decât rata de convergență a metodei gradientului cu un pas constant (optim).
Exemple numerice
Metoda de coborâre cu gradient în pas constant
Pentru a studia convergența metodei de coborâre a gradientului cu un pas constant, a fost aleasă funcția:
Din rezultatele obținute, putem concluziona că metoda diverge dacă frecvența este prea mare și converge lent dacă frecvența este prea mică, iar precizia este mai slabă. Este necesar să alegeți pasul care este cel mai mare dintre cei pentru care metoda converge.
Metoda gradientului cu împărțire în trepte
Pentru a studia convergența metodei de coborâre a gradientului cu împărțirea în trepte (2), a fost aleasă următoarea funcție:
Aproximația inițială este punctul (10,10).
Criteriul de oprire utilizat:
Rezultatele experimentului sunt prezentate în tabel:
|
Sens parametru |
Valoarea parametrului |
Valoarea parametrului |
Precizie atinsă |
Numărul de iterații |
Din rezultatele obținute, putem concluziona că alegerea optimă a parametrilor este: , deși metoda nu este foarte sensibilă la alegerea parametrilor.
Cea mai abruptă metodă de coborâre
Pentru a studia convergența celei mai abrupte metode de coborâre, a fost aleasă următoarea funcție:
Aproximația inițială este punctul (10,10). Criteriul de oprire utilizat:
Metoda secțiunii de aur a fost folosită pentru a rezolva probleme de optimizare unidimensională.
Metoda a obținut o precizie de 6e-8 în 9 iterații.
Din aceasta putem concluziona că metoda de coborâre cu cea mai abruptă converge mai rapid decât metoda gradientului de împărțire a treptei și metoda de coborâre a gradientului constant.
Dezavantajul celei mai abrupte metode de coborâre este necesitatea de a rezolva o problemă de optimizare unidimensională.
Când programați metode de coborâre a gradientului, trebuie să aveți grijă la alegerea parametrilor, și anume
- · Metoda de coborâre în gradient cu pas constant: treapta trebuie aleasă mai mică de 0,01, în caz contrar metoda diverge (metoda poate diverge chiar și la acest pas, în funcție de funcția studiată).
- · Metoda gradientului cu divizare în trepte nu este foarte sensibilă la alegerea parametrilor. Una dintre opțiunile din care puteți alege:
- · Metoda cea mai abruptă de coborâre: Ca metodă de optimizare unidimensională, poate fi utilizată metoda secțiunii de aur (dacă este cazul).
Metoda gradientului conjugat este o metodă iterativă pentru optimizarea neconstrânsă în spațiul multidimensional. Principalul avantaj al metodei este că rezolvă problema de optimizare pătratică într-un număr finit de pași. Prin urmare, este descrisă mai întâi metoda gradientului conjugat pentru optimizarea funcționalei pătratice, sunt derivate formule iterative și sunt date estimări ale ratei de convergență. După aceea, se arată cum se generalizează metoda conjugată pentru a optimiza o funcționalitate arbitrară, se iau în considerare diferite versiuni ale metodei și se discută convergența.
Enunțul problemei de optimizare
Fie dată o mulțime și o funcție obiectiv (funcție obiectivă) definită pe această mulțime. Problema de optimizare este de a găsi exact limita superioară sau inferioară a funcției obiectiv pe mulțime. Se notează setul de puncte în care este atinsă limita inferioară a funcției obiectiv.
Dacă, atunci problema de optimizare se numește neconstrâns. Dacă, atunci problema de optimizare se numește constrânsă.
Metoda gradientului conjugat pentru o funcțională pătratică
Declarație de metodă
Luați în considerare următoarea problemă de optimizare:
Aici, este o matrice simetrică pozitiv-definită de dimensiune. O astfel de problemă de optimizare se numește pătratică. Observa asta. Condiția extremă a unei funcții este echivalentă cu sistemul Funcția își atinge limita inferioară într-un singur punct definit de ecuație. Astfel, această problemă de optimizare se reduce la rezolvarea unui sistem de ecuații liniare Ideea metodei gradientului conjugat este următoarea: Fie baza lui c. Apoi, pentru orice punct, vectorul este extins în termeni de bază. Astfel, poate fi reprezentat ca
Fiecare aproximare următoare este calculată cu formula:
Definiție. Doi vectori și se numesc conjugați față de o matrice simetrică B dacă
Să descriem metoda de construire a unei baze în metoda gradientului conjugat.Ca o aproximare inițială, alegem un vector arbitrar. La fiecare iterație, sunt alese următoarele reguli:
Vectorii de bază sunt calculați prin formulele:
Coeficienții sunt aleși astfel încât vectorii și să fie conjugați în raport cu A.
Dacă notăm cu, atunci după mai multe simplificări obținem formulele finale utilizate în aplicarea metodei gradientului conjugat în practică:
Următoarea teoremă este adevărată pentru metoda gradientului conjugat: Teorema Fie, unde este o matrice definită pozitivă simetrică de dimensiune. Apoi metoda gradientului conjugat converge în nu mai mult de pași și sunt valabile următoarele relații:
Convergența metodei
Dacă toate calculele sunt exacte, iar datele inițiale sunt exacte, atunci metoda converge către soluția sistemului în nu mai mult de iterații, unde este dimensiunea sistemului. O analiză mai fină arată că numărul de iterații nu depășește, unde este numărul de valori proprii diferite ale matricei A. Pentru a estima rata de convergență, următoarea estimare (mai degrabă aproximativă) este adevărată:
Permite estimarea ratei de convergență dacă sunt cunoscute estimări pentru valorile proprii maxime și minime ale matricei.În practică, cel mai des este utilizat următorul criteriu de oprire:
Complexitatea computațională
Operațiile sunt efectuate la fiecare iterație a metodei. Acest număr de operații este necesar pentru a calcula produsul - aceasta este procedura cea mai consumatoare de timp la fiecare iterație. Restul calculelor necesită operații O(n). Complexitatea totală de calcul a metodei nu depășește - deoarece numărul de iterații este de cel mult n.
Exemplu numeric
Aplicam metoda gradientului conjugat pentru a rezolva sistemul, unde C folosind metoda gradientului conjugat, solutia acestui sistem se obtine in doua iteratii. Valorile proprii ale matricei - 5, 5, -5 - două dintre ele sunt diferite, prin urmare, conform estimării teoretice, numărul de iterații nu ar putea depăși două
Metoda gradientului conjugat este una dintre cele mai eficiente metode de rezolvare a SLAE cu o matrice definită pozitivă. Metoda garantează convergența într-un număr finit de pași, iar precizia necesară poate fi obținută mult mai devreme. Problema principală este că, din cauza acumulării de erori, poate fi încălcată ortogonalitatea vântului de bază, ceea ce agravează convergența
Metoda gradientului conjugat în general
Să considerăm acum o modificare a metodei gradientului conjugat pentru cazul în care funcționala minimizată nu este pătratică: Vom rezolva problema:
O funcție diferențiabilă continuu. Pentru a modifica metoda gradientului conjugat pentru a rezolva această problemă, este necesar să se obțină pentru formulele care nu includ matricea A:
poate fi calculat folosind una dintre cele trei formule:
1. - Metoda Fletcher-Reeves
- 2. - Metoda Polak-Ribi`ere
Dacă funcția este pătratică și strict convexă, atunci toate cele trei formule dau același rezultat. Dacă este o funcție arbitrară, atunci fiecare dintre formule corespunde propriei modificări a metodei gradientului conjugat. A treia formulă este rar folosită deoarece necesită funcția și calculul Hessianului funcției la fiecare pas al metodei.
Dacă funcția nu este pătratică, metoda gradientului conjugat poate să nu convergă într-un număr finit de pași. În plus, calculul exact la fiecare pas este posibil doar în cazuri rare. Prin urmare, acumularea erorilor duce la faptul că vectorii nu mai indică direcția funcției descrescătoare. Apoi, la un pas, ei presupun. Setul tuturor numerelor pentru care este acceptat va fi notat ca. Numerele se numesc timpi de actualizare a metodei. În practică, se alege adesea unde este dimensiunea spațiului.
Convergența metodei
Pentru metoda Fletcher-Reeves, există o teoremă de convergență care impune condiții nu prea stringente asupra funcției care este minimizată: Teoremă. Să fie îndeplinite următoarele condiții:
Setul este limitat
Derivata satisface condiția Lipschitz cu o constantă într-o anumită vecinătate
seturi M: .
Convergența este dovedită pentru metoda Polack-Reiber sub ipoteza că este o funcție strict convexă. În cazul general, este imposibil să se dovedească convergența metodei Polak-Reiber. Dimpotrivă, următoarea teoremă este adevărată: Teorema. Să presupunem că în metoda Polak-Reiber valorile la fiecare pas sunt calculate exact. Apoi există o funcție și o aproximare inițială, astfel încât.
Cu toate acestea, metoda Polak-Reiber funcționează mai bine în practică. Cele mai comune criterii de oprire în practică: Norma gradientului devine mai mică decât un anumit prag. Valoarea funcției în timpul m iterații succesive aproape nu s-a schimbat
Complexitatea computațională
La fiecare iterație a metodelor Polack-Reiber sau Fletcher-Reeves, funcția și gradientul acesteia sunt calculate o dată, iar problema optimizării unidimensionale este rezolvată. Astfel, complexitatea unei etape a metodei gradientului conjugat este de aceeași ordine cu complexitatea pasului metodei celei mai abrupte coborâri. În practică, metoda gradientului conjugat arată cea mai bună rată de convergență.
Vom căuta minimul funcției prin metoda gradienților conjugați
Minimul acestei funcții este egal cu 1 și este atins în punctul (5, 4). Să comparăm metodele lui Polack-Reiber și Fletcher-Reeves pe exemplul acestei funcții. Iterațiile în ambele metode se opresc atunci când pătratul normei de gradient devine mai mic la pasul curent. Pentru selecție se folosește metoda secțiunii de aur.
|
Metoda Fletcher-Reeves |
Metoda Polack-Reiber |
|||||
|
Numărul de iterații |
Soluție găsită |
Valoarea funcției |
Numărul de iterații |
Soluție găsită |
Valoarea funcției |
|
|
(5.01382198,3.9697932) |
(5.03942877,4.00003512) |
|||||
|
(5.01056482,3.99018026) |
(4.9915894,3.99999044) |
|||||
|
(4.9979991,4.00186173) |
(5.00336181,4.0000018) |
|||||
|
(4.99898277,4.00094645) |
(4.99846808,3.99999918) |
|||||
|
(4.99974658,4.0002358) |
(4.99955034,3.99999976) |
Sunt implementate două versiuni ale metodei gradientului conjugat: pentru minimizarea unei funcționale pătratice și pentru minimizarea unei funcții arbitrare. În primul caz, metoda este implementată de funcția vectorială
Metodele de coborâre în gradient sunt un instrument destul de puternic pentru rezolvarea problemelor de optimizare. Principalul dezavantaj al metodelor este aria limitată de aplicabilitate. Metoda gradientului conjugat utilizează informații numai despre partea liniară a incrementului într-un punct, ca în metodele de coborâre a gradientului. În același timp, metoda gradientului conjugat permite rezolvarea problemelor pătratice într-un număr finit de pași. În multe alte probleme, metoda gradientului conjugat depășește și metoda de coborâre a gradientului. Convergența metodei gradientului depinde în esență de cât de precis este rezolvată problema de optimizare unidimensională. Buclele posibile ale metodei sunt remediate cu actualizări. Cu toate acestea, dacă metoda atinge minimul local al funcției, cel mai probabil nu va putea ieși din ea.
Adnotare: În această prelegere, sunt acoperite pe larg metode de optimizare multi-parametrică, cum ar fi cea mai abruptă metodă de coborâre și metoda Davidon-Fletcher-Powell. În plus, se efectuează o analiză comparativă a metodelor de mai sus pentru a determina cele mai eficiente, sunt identificate avantajele și dezavantajele acestora; și, de asemenea, ia în considerare probleme de optimizare multivariată, cum ar fi metoda ravenelor și metoda multi-extremalitate.
1. Metoda celei mai abrupte coborâri
Esența acestei metode este aceea cu ajutorul celor menționate anterior metoda coborării coordonate se efectuează o căutare dintr-un punct dat într-o direcție paralelă cu una dintre axe, până la un punct minim în această direcție. Căutarea se efectuează apoi într-o direcție paralelă cu cealaltă axă și așa mai departe. Direcțiile sunt, desigur, fixe. Pare rezonabil să încercăm să modificați această metodă în așa fel încât în fiecare etapă căutarea punctului minim să fie efectuată pe direcția „cea mai bună”. Nu este clar care direcție este „cea mai bună”, dar se știe că direcția gradientului este direcția celei mai rapide creșteri a funcției. Prin urmare, direcția opusă este direcția celei mai rapide scăderi a funcției. Această proprietate poate fi justificată după cum urmează.
Să presupunem că ne deplasăm de la punctul x la următorul punct x + hd , unde d este o direcție și h este un pas de o anumită lungime. Prin urmare, deplasarea se face de la punct (x 1, x 2, ..., x n) la punct (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Unde
Modificarea valorilor funcției este determinată de relații
| (1.3) |
Până la primul ordin zx i , iar derivatele parțiale se calculează în punctul x . Cum ar trebui să fie alese direcțiile d i care satisfac ecuația (1.2) pentru a obține cea mai mare modificare a funcției df? Aici apare problema maximizării cu o constrângere. Aplicam metoda multiplicatorilor Lagrange, cu ajutorul carora definim functia
Valoarea lui df care satisface constrângerea (1.2) atinge maximul atunci când funcția
Atinge maximul. Derivatul său
Prin urmare,
 |
(1.6) |
Atunci di ~ df/dx i si directia d este paralela cu directia V/(x) in punctul x.
În acest fel, cea mai mare creștere locală funcția pentru un pas mic dat h apare atunci când d este direcția Vf(x) sau g(x) . Prin urmare, direcția de coborâre cea mai abruptă este direcția
Într-o formă mai simplă, ecuația (1.3) poate fi scrisă după cum urmează:
Unde este unghiul dintre vectorii Vf(x) și dx . Pentru o valoare dată a lui dx, minimizăm df alegând , astfel încât direcția lui dx să fie aceeași cu direcția lui -Vf(x) .
cometariu. Direcția gradientului perpendicular pe orice punct de pe linia de nivel constant, deoarece funcția este constantă de-a lungul acestei linii. Astfel, dacă (d 1 , d 2 , ..., d n) este un pas mic de-a lungul liniei de nivel, atunci
Prin urmare
 |
(1.8) |
Exemplul 6.8.3-1. Găsiți minimul funcției Q(x, y) folosind metoda GDS.
Fie Q(x,y) = x 2 +2y 2 ; x 0 = 2; y 0 = 1.
Să verificăm condițiile suficiente pentru existența unui minim:
Să facem o iterație conform algoritmului.
1. Q(x0,y0) = 6.
2.
Când x \u003d x 0 și y \u003d y 0, 
3. Pasul l k \u003d l 0 \u003d 0,5
Deci 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.
Esența metodei este următoarea. Din punctul selectat (x 0 ,y 0) coborârea se efectuează în direcția anti-gradient până când se atinge valoarea minimă a funcției obiectiv Q(x, y) de-a lungul fasciculului (Fig. 6.8.4-). 1). În punctul găsit, fasciculul atinge linia de nivel. Apoi, din acest punct, coborârea se efectuează în direcția anti-gradientului (perpendicular pe linia de nivel) până când fasciculul corespunzător atinge linia de nivel care trece prin aceasta într-un nou punct și așa mai departe.
Să exprimăm funcția obiectiv Q(x, y) în termenii pasului l. În același timp, reprezentăm funcția obiectiv la un anumit pas ca o funcție a unei variabile, i.e. dimensiunea pasului
Dimensiunea pasului la fiecare iterație este determinată din condiția minimă:
Min( (l)) l k = l*(x k , y k), l >0.
Astfel, la fiecare iterație, alegerea pasului l k implică rezolvarea unei probleme de optimizare unidimensională. Conform metodei de rezolvare a acestei probleme, există:
· metoda analitica (NSA);
· Metoda numerică (NCh).
În metoda NSA, valoarea pasului este obținută din condiția , iar în metoda LSS, valoarea l k este găsită pe un segment cu o precizie dată folosind una dintre metodele de optimizare unidimensională.
Exemplul 6.8.4-1. Aflați minimul funcției Q(x,y)=x 2 + 2y 2 cu o precizie de e=0,1, în condițiile inițiale: x 0 =2; y 0 =1.
Să facem o iterație după metodă NSA.
=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .
Din condiția ¢(l)=0 găsim valoarea l*: 
Funcția rezultată l=l(x,y) vă permite să găsiți valoarea lui l. Pentru x=2 și y=1 avem l=0,3333.
Calculați valorile coordonatelor următorului punct:
Să verificăm îndeplinirea criteriului de terminare a iterației pentru k=1:
Deoarece |2*0.6666|>0.1 și |-0.3333*4|>0.1 , nu sunt îndeplinite condițiile de terminare a procesului de iterație, adică. minim nu a fost găsit. Prin urmare, ar trebui să calculați noua valoare a lui l la x=x 1 și y=y 1 și să obțineți coordonatele următorului punct de coborâre. Calculele continuă până când sunt îndeplinite condițiile finale ale coborârii.
Diferența dintre metoda numerică NN și cea analitică este că căutarea valorii lui l la fiecare iterație se realizează prin una dintre metodele numerice de optimizare unidimensională (de exemplu, metoda dihotomiei sau metoda secțiunii de aur). În acest caz, intervalul de valori admisibile pentru l - servește ca interval de incertitudine.
