vii. metode numerice de rezolvare a problemelor de optimizare fără

Metode de Optimizare – Curs 12

1

VII. Metode numerice de rezolvare a problemelor

de optimizare fără restricţii

Considerăm X o submulţime convexă deschisă a lui Rn , f: X → R o

funcţie convexă diferenţiabilă şi problema de optimizare

x Xinf f (x)∈

(P)

Metodele iterative de rezolvare a problemei constau în construirea unui şir

(xk)k îndeplinind condiţia :

f(xk+1) < f(xk), pentru orice k≥0 (x0 ∈ X dat).

şi având un punct limită un x ∈X care să fie punct staţionar pentru f (cu alte

cuvinte şirul (xk)k are un subşir (k jx )j cu proprietatea că

k j

jlim x→∞

= x ∈X şi ∇f( x ) =

0). Funcţia f fiind convexă, X fiind deschisă şi ∇f( x ) = 0, rezultă că x este punct

de minim global pentru f pe X (soluţie optimă a problemei studiate). Dacă f nu

este convexă, atunci pentru a asigura că x este punct de minim local (soluţie

optimă locală) ar trebui verificate condiţiile de ordinul 2 (Hf( x ) pozitiv definită).

Metodele iterative de rezolvare a problemelor de optimizare fără restricţii pot fi

clasificate în

- Metode de ordin 0: utilizează doar valorile funcţiei f în punctul xk şi

eventual în câteva puncte vecine (de explorare).

- Metode de ordin 1: necesită calculul valorii funcţiei f precum şi al

gradientului lui f în punctul xk. Aceste metode realizează un compromis

între simplitate (volum de calcul) şi eficienţă, fiind frecvent utilizate în

practică

- Metode de ordin 2: necesită atât valorile funcţiei f, a gradientului şi

hessianei lui f în punctul xk cât şi inversarea hessianei. Prin compensaţie

Mădălina Roxana Buneci Metode de Optimizare – Curs - 2007

2

cu volumul de calcul aceste metode asigură o viteză de convergenţă

superioară.

- Metode de ordin superior: volum de calcul sporit pentru evaluarea

valorile derivatelor de ordin superior lui 2 ale funcţiei f, fiind rar

folosite în practică

Vom prezenta in continuare metode de ordinul 1 şi 2 denumite metode de căutare

liniară („linesearch methods”). Şirul construit are forma

k kk 1 k kk k n

t , t 0 pas dedeplasarex x t v

v direcţiededeplasare+

∈ ≥ →= +

∈ →

R

R (LS)

f(xk+1) < f(xk), pentru orice k≥0.

Definiţie 1. X o submulţime deschisă a lui Rn , f: X → R o funcţie

diferenţiabilă şi x∈X. Un vector v∈Rn se numeşte direcţie descendentă în x dacă

<v, ∇f(x)> < 0.

Dacă v este direcţie descendentă în x atunci există λ >0 astfel încât pentru

orice t ∈ (0, λ ), f(x + tv) < f(x). Într-adevăr, aplicând formula lui Taylor de

ordinul 1, există δ0>0 astfel încât pentru orice δ∈R cu δ< δ0 1

v avem

f(x+ δv) = f(x) + δ<∇f(x),v>v + o(δ), unde ( )

δ 0

o δlim

δ→=0

Există λ >0, λ≤ δ0 astfel încât pentru orice 0 < t < λ , ( )o t

t < - <∇f(x),v>v şi ca

urmare:

f(x+ tv) = f(x) + t(<∇f(x),v>v +( )o t

t) < f(x).

Pe de altă parte dacă pentru orice v∈ Rn avem <v, ∇f(x)> ≥ 0, atunci x este punct

de staţionar pentru f (iar dacă presupunem în plus, f convexă, atunci x este punct

de minim pentru f). Într-adevăr, luând v = -∇f(x), rezultă -<∇f(x), ∇f(x)> ≥ 0 sau

echivalent ∇f(x) = 0.

Algoritmul generic pentru construcţia şirului (xk)k care să aibă un punct

limită x ∈X care să fie punct staţionar pentru f este schiţat mai jos.

x0∈X dat


3

cât timp ||∇f(xk)|| ≠0 execută

pasul 1: *se determină o direcţie de deplasare vk care să fie direcţie

descendentă în xk (dacă nu există o astfel de direcţie atunci STOP, xk

este soluţie optimă – mai precis ∇f(xk) = 0)

pasul 2: *se determină pasul de deplasare tk astfel încât

f(xk + tkvk) < f(xk)

pasul 3: xk+1 = xk + tkvk; k:=k+1;

La ieşire xk cu proprietatea ∇f(xk) = 0 este punct staţionar al lui f. În practică se dă

ε > 0 (precizia cu care se identifică soluţia optimă) iar criteriul de oprire ||∇f(xk)||

≠0 se înlocuieşte cu una din condiţiile

a. ||∇f(xk)|| < ε (gradientul este „suficient de mic”)

b. ||xk+1 - xk|| < ε (cele două iteraţii succesive sunt „suficient de apropiate”)

c. |f(xk) - f(xk+1)| < ε (micşorarea funcţiei obiectiv „nu este semnificativă”)

unde ||⋅|| este o norma convenabil aleasă. În criteriile de oprire pot fi folosite valori

relative, astfel de exemplu condiţia de la c poate fi înlocuită cu

( ) ( )( )

k k 1

k

f x f x

1 f x

+−

+< ε

În cele ce urmează vom presupune că în etapa k a algoritmului de mai sus

a fost determinată o direcţie de deplasare vk şi rămâne să determinăm pasul de

deplasare tk. Metodele de determinare a pasului tk pot fi clasificate în

1. proceduri de alegere optimală a pasului (algoritmi de căutare liniară

exactă)

2. proceduri de alegere suboptimală a pasului (algoritmi de căutare liniară

inexactă

VII.1. Proceduri de alegere optimală a pasului

Procedurile de alegere optimală a pasului presupun determinarea lui tk din

condiţia

f(xk+tkvk) =

t 0inf

≥f(xk + tvk)


4

(adică tk este soluţie optimă a problemei t 0inf

≥f(xk + tvk)). Altfel spus procedurile

de alegere optimală a pasului presupun minimizare funcţiei ϕ: [0, λ )→R, definită

prin ϕ(t) = f(xk+tvk), unde λ este ales astfel încât xk+tvk ∈X pentru orice t∈[0, λ )

(ţinând cont că xk∈X şi X este o mulţime deschisă, rezultă că există δ>0 astfel

încât B(xk,δ) ⊂ X, λ = k

1

vδ îndeplineşte condiţia cerută).

Lema 2. X o mulţime convexă şi f: X → R o funcţie convexă. Atunci

funcţia ϕ: [0, λ )→R, definită prin ϕ(t) = f(xk+tvk), este convexă, unde λ ∈ R este

ales astfel încât xk+tvk ∈X pentru orice t∈[0, λ ).

Demonstraţie. Fie t1, t2 ∈ [0, λ ) şi fie λ∈(0,1). Atunci

ϕ(λt1 + (1-λ)t2) = f(xk + (λt1 + (1-λ)t2)vk) = f(λ(xk + t1v

k)+(1-λ)(xk + t2 vk))

f convexa

≤ λ f(xk + t1vk)+ (1-λ)f(xk + t2 v

k) =λ ϕ(t1) + (1-λ) ϕ(t2).

■

Metodele de explorare directă pentru determinarea unui punct de minim al

lui ϕ constau în identificarea în prealabil a unui interval [a0, b0] care conţine un

punct de minim al lui ϕ.

Lema 3. Fie I un interval de numere reale, ϕ : I → R o funcţie convexă

care admite un punct de minim.

1. Dacă t1, t2, t3 ∈ I, t1 < t2 < t3, astfel încât

ϕ(t1) > ϕ(t2) ≤ ϕ(t3).

atunci există un punct de minim al lui ϕ în intervalul [t1, t3].

2. Dacă I = [a, λ ), λ ∈ R şi t∈ (a, λ ) cu ϕ(t) ≥ ϕ(a), atunci există un

punct de minim al lui ϕ în intervalul [a, t].

Demonstraţie. Fie t* un punct de minim al lui ϕ .

1. Presupunem prin absurd t* < t1 sau echivalent t1∈(t*, t2). Atunci există

λ∈(0, 1) astfel încât t1 = λt*+(1-λ)t2 şi ca urmare

ϕ(t1) = ϕ(λt*+(1-λ)t2) ≤ λϕ(t*) + (1-λ)ϕ(t2) ≤ λϕ(t2) + (1-λ)ϕ(t2) = ϕ(t2)


5

ceea ce contrazice ϕ(t1) > ϕ(t2). Deci t* ≥ t1. Dacă t*≤t3, atunci t*∈[t1, t3]. Dacă

t*>t3 sau echivalent t3∈(t2, t*), atunci există λ∈(0, 1) astfel încât t3 = λt2+(1-λ)t*

şi ca urmare

ϕ(t3) = ϕ(λt2+(1-λ)t*) ≤ λϕ(t2) + (1-λ)ϕ(t*) ≤ λϕ(t2) + (1-λ)ϕ(t2) = ϕ(t2) ≤ϕ(t3).

De aici rezultă ϕ(t*) = ϕ(t2), adică t2 este punct de minim pentru ϕ şi în plus

t2∈[t1, t3].

2. Dacă t*≤t, atunci t*∈[a, t]. Dacă t*>a sau echivalent t∈(a t*), atunci

există λ∈(0, 1) astfel încât t= λa+(1-λ)t* şi ca urmare

ϕ(t) = ϕ(λa+(1-λ)t*) ≤ λϕ(a) + (1-λ)ϕ(t*) ≤ λϕ(a) + (1-λ)ϕ(a) = ϕ(a) ≤ϕ(t),

de unde rezultă ϕ(t*) = ϕ(a), adică a este punct de minim pentru ϕ şi în plus

a∈[a,t].

■

Algoritm de determinare al a unui interval [a0, b0] care conţine un

punct de minim pentru funcţia convexă ϕϕϕϕ: [a, ∞) →→→→ R (presupunând că ϕϕϕϕ

admite un punct de minim):

ϕ: [a, ∞) → R funcţie convexă

c > 0 dat

t1:=a; t2: = a+c; y1:=ϕ(t1); y2:=ϕ(t2);

dacă y1 ≤ y2, atunci a0 : =t1 şi b0 : = t2

altfel cât timp y1 > y2 execută

y1 : = y2;

t1:=t2; t2:= t2+c;

y2: = ϕ(t2);

a0 : = t1-c; b0 : = t2;

Procedura MAPLE de mai jos are drept parametri funcţia convexă ϕ, a

(capatul inferior al intervalului de definiţie al lui ϕ) şi c>0. Procedura returnează

intervalul [a0, b0] ce conţine un punct de minim pentru ϕ: [a, ∞) → R

(presupunând că ϕ admite un punct de minim):

> init:=proc(phi,a,c)

> local a0,b0,y1,y2,t1,t2;

> t1:=evalf(a); t2:=evalf(a+c); y1:=phi(t1); y2:=phi(t2);


6

> if y1<=y2 then a0:=t1; b0:=t2 else

> while y1>y2 do y1:=y2;t1:=t2;t2:=t2+c;y2:=phi(t2) od;

> a0:=t1-c; b0:=t2

> fi;

> RETURN([a0, b0])

> end;

Exemplu 4. Aplicăm această procedură funcţiilor ϕ1: [0, ∞) → R, ϕ1(t) =

t2 -3t+5 şi ϕ2: [-3/4,∞) → R, ϕ2(t) = t – ln(t+1):

> phi1:=t->t^2 -3*t-5;

> phi2:=t->t-ln(t+1);

şi obţinem

> I01:=init(phi1,0,1);

:= I01 [ ],0. 2.

> I02:=init(phi2,-3/4,1);

:= I02 [ ],-0.7500000000 1.250000000

După determinarea unui interval [a0, b0] ce conţine un punct de minim

pentru ϕ: [a, λ )→ R ( λ ∈ R ) prin metodele de explorare directă se urmăreşte

reducerea iterativă a lungimii acestui interval până la atingerea unei precizii

impuse ε>0 de localizare a lui unui punct de minim t*. Cu alte cuvinte se

urmăreşte construirea unui şir de intervale [aj, bj], j≥0 cu proprietatea că jlim→∞

Lj=0,

unde Lj = |bj - aj| este lungimea intervalului [aj, bj] pentru orice j≥0.

Lema 5. Fie I un interval de numere reale, ϕ : I → R o funcţie convexă şi

[a,b] ⊂ I un subinterval ce conţine un punct de minim al lui ϕ . Fie a , b ∈ (a,b)

cu a < b .

1. Dacă ϕ( a ) < ϕ( b ), atunci intervalul [a, b ] conţine un punct de minim

pentru ϕ.

2. Dacă ϕ( a ) ≥ ϕ( b ), atunci intervalul [ a ,b] conţine un punct de minim

pentru ϕ.

Demonstraţie. Fie t* un punct de minim al lui ϕ .

1. Presupunem prin absurd t* > b sau echivalent b ∈ ( a ,t*). Atunci

există λ∈(0, 1) astfel încât b = λ a +(1-λ)t* şi ca urmare


7

ϕ( b ) = ϕ(λ a +(1-λ)t*) ≤ λϕ( a ) + (1-λ)ϕ(t*) ≤ λϕ( a ) + (1-λ)ϕ( a ) = ϕ( a )

ceea ce contrazice ϕ( b ) > ϕ( a ). Deci b ≥ t*.

2. Dacă t* ≥ a , atunci t*∈[ a , b]. Dacă t*< a sau echivalent a ∈(t*, b ),

atunci există λ∈(0, 1) astfel încât a = λt*+(1-λ) b şi ca urmare

ϕ( a ) = ϕ(λt*+(1-λ) b ) ≤ λϕ(t*) + (1-λ)ϕ( b ) ≤

≤ λϕ( b ) + (1-λ)ϕ( b ) = ϕ( b ) ≤ϕ( a ),

de unde rezultă ϕ(t*) = ϕ( b ), adică b este punct de minim pentru ϕ şi în plus

b ∈[ a ,b].

■

Această lemă sugerează următorul algoritm de construcţie a şirului de

intervale [aj,bj], j≥0 cu proprietatea că jlim→∞

|bj - aj| =0 (sau cel puţin, având

proprietatea că dacă precizia ε>0 este fixată există jε cu | jbε

- jaε|< ε) şi astfel

încât fiecare interval [aj,bj] să conţină un punct de minim pentru funcţia convexă

ϕ:

ϕ - funcţie convexă

ε > 0 dat – precizia de localizare a unui punct de minim t* al lui ϕ

[a0, b0] – interval iniţial ce conţine un punct de minim al lui ϕ

j: = 0;

cât timp |bj-aj| ≥ ε execută

Pasul 1: *se aleg ja < jb , ja , jb ∈(aj, bj)

Pasul 2: dacă ϕ( ja ) <ϕ( jb ) atunci aj+1 =aj ; bj+1 = jb ;

altfel aj+1 = ja ; bj+1 =bj;

j: = j+1;

t* ≈ (bj +aj)/2

Eroarea absolută cu care (bj+aj)/2 aproximează t* (punct de minim al lui

ϕ) este cel mult 1

2ε.


8

Există diverse posibilităţi de alegere a ja , jb ∈(aj, bj) cu ja < jb . De

exemplu putem alege ja = 1

2(aj + bj) - δ şi jb =

1

2(aj + bj) + δ cu δ>0 foarte mic.

Atunci Lj+1 = bj+1 –aj+1 = 1

2(bj –aj) + δ =

1

2Lj + δ pentru orice j ≥ 0. Aşadar Lj =

2j

11

2 −

0

1L

2 − + δ

+L0. Avem jlim→∞

Lj = 2δ. Deci dacă δ < 1

2ε, atunci există jε

cu | jbε

- jaε| = jL

ε < ε. Descriem mai jos algoritmul corespunzător:

ϕ - funcţie convexă


δ > 0 dat (având proprietatea că δ< ε/2)


a: = a0; b: = b0;

cât timp b – a ≥ ε execută

c: = (a+b)/2;

dacă ϕ(c-δ) < ϕ(c+δ) atunci b: = c+δ

altfel a:= c-δ

t* ≈ (b +a)/2;

Procedura MAPLE dichotomous_search implementează algoritmul de mai

sus. Parametrii procedurii sunt: funcţia convexă ϕ, lista I0 cu capetele a0, b0 ale

unui interval ce conţine un punct de minim pentru ϕ, precizia ε de localizare a

unui punct de minim şi δ. Procedura întoarce o aproximaţie a unui punct de minim

al lui ϕ cu eroare cel mult 1

2ε.

> dichotomous_search:=proc(phi,I0,epsilon,delta)

> local a,b,c;

> a:=evalf(I0[1]);b:=evalf(I0[2]);

> while b-a>=epsilon do

> c:=(a+b)/2;

> if evalf(phi(c-delta))<evalf(phi(c+delta))then b:=c+delta

> else a:=c-delta fi;

> od;


9

> RETURN((a+b)/2)

> end;

Exemplu 6. Aplicăm procedura dichotomous_search funcţiilor ϕ1,

respectiv ϕ2 din exemplul 4 şi intervalelor date de listele I01, respectiv I02

obţinute ca urmare a aplicării procedurii init (în exemplul 4):

> dichotomous_search(phi1,I01,10^(-5),10^(-5)/4);

1.500046434

> dichotomous_search(phi2,I02,10^(-5),10^(-5)/4);

-0.1282343865 10-5

Există însă o modalitate mai bună de alegere a ja , jb ∈(aj, bj) cu ja < jb

astfel încât la fiecare iteraţie să se facă o singură evaluare a funcţiei ϕ (în loc de

două câte se efectuează în algoritmul precedent).

VII.1.1. Metoda secţiunii de aur

Această metodă este bazată pe aşa numita secţiune de aur (golden

section). Secţiunea de aur a unui segment este o diviziunea a acestuia în două

subsegmente astfel încât raportul dintre lungimea subsegmentului mai lung şi

lungimea întregului segment este egală este egal cu raportul dintre lungimea

subsegmentului mai scurt şi cea a subsegmentului mai lung:

Dacă lungimea segmentului considerat este 1 iar lungimea subsegmentului mai

lung este α, atunci 1

α =

1− αα

, sau echivalent α2 + α - 1 = 0. Singura soluţie a

acestei ecuaţii din intervalul [0, 1] este α = 5 1

2

− ≈ 0.618.

Pentru fiecare j ≥ 0 se aleg ja = aj + (1-α)(bj – aj) iar jb = aj + α(bj – aj).

Dacă ϕ( ja )<ϕ( jb ), atunci aj+1= aj şi bj+1= jb şi ca urmare

α 1-α

1


10

j 1b + =aj+1 + α( bj+1 – aj+1) =aj +α2(bj-aj) = aj +(1-α)(bj – aj) = ja .

Legătura dintre cele două iteraţii j şi j+1 este ilustrată mai jos:

Deci la iteraţia j+1 va trebui să evaluăm doar ϕ( j 1a + ) deoarece valoarea lui

ϕ( j 1b + )=ϕ( ja ) este cunoscută de la iteraţia j.

Analog dacă ϕ( ja )≥ϕ( jb ), atunci aj+1= ja şi bj+1=bj şi ca urmare

j 1a + =aj+1 + (1-α)( bj+1 – aj+1) = ja +(1-α)α(bj-aj) =

= aj + (1-α)(bj – aj) +(α-α2)(bj – aj) = aj +(1-α2)(bj – aj) =

= aj +α(bj – aj) = jb .

Cazul ϕ( ja )≥ϕ( jb ):

Ca urmare în acest caz va trebui să evaluăm doar ϕ( j 1b + ) deoarece valoarea lui

ϕ( j 1a + )=ϕ( jb ) este cunoscută de la iteraţia j.

În ambele cazuri avem Lj+1 = bj+1 – aj+1 = α(bj – aj) = αLj pentru orice j ≥

0. Aşadar Lj = αjL0 pentru orice j ≥ 0 şi ca urmare jlim→∞

Lj = 0. Numărul de iteraţii

Iteraţia j

Iteraţia j+1 aj+1 j 1a + j 1b + bj+1

aj ja jb bj

Iteraţia j

Iteraţia j+1 aj+1 j 1a + j 1b + bj+1

aj ja jb bj


11

necesare pentru reducerea lungimii intervalului Lj < ε este nε =( )

( )0ln L

ln

ε

α +1.

Descriem mai jos algoritmul corespunzător denumit metoda secţiunii de aur:



α : = 5 1

2

−

a: = a0; b: = b0; L: = b-a; nmax:=( )

( )ln b a

ln

ε −

α +1

a : = a + (1-α)L; b : = a + αL;

y1:=ϕ( a ); y2: = ϕ( b ); j: = 0;

cât timp j < nmax execută

dacă y1 < y2 atunci b:= b ; L:=b-a; b : = a ; y2:=y1;

a : = a + (1-α)L; y1:=ϕ( a );

altfel a: = a ; L:=b-a; a : = b ; y1:=y2;

b : = a + αL; y1:=ϕ( b );

j: = j +1;

t* ≈ (b +a)/2;

Procedura MAPLE golden_section implementează algoritmul de mai sus.

Parametrii procedurii sunt: funcţia convexă ϕ, lista I0 cu capetele a0, b0 ale unui

interval ce conţine un punct de minim pentru ϕ şi precizia ε de localizare a unui

punct de minim al lui ϕ. Procedura întoarce o aproximaţie a unui punct de minim

al lui ϕ cu eroare cel mult 1

2ε.

> golden_section:=proc(phi,I0,epsilon)

> local alpha,beta,a,b,y1,y2,L,u,v,j,nmax;

> alpha:=evalf((5^(1/2)-1)/2);beta:=1-alpha;

> a:=evalf(I0[1]);b:=evalf(I0[2]);L:=b-a;

> u:=a+beta*L;v:=a+alpha*L;y1:=phi(u);y2:=phi(v);

> nmax:=ceil(ln(epsilon/L)/ln(alpha));j:=0;

> while j<nmax do

> if y1<y2 then b:=v;L:=b-a;


12

> y2:=y1;v:=u;u:=a+beta*L;y1:=phi(u)

> else a:=u;L:=b-a;

> y1:=y2;u:=v;v:=a+alpha*L;y2:=phi(v);

> fi;

> j:=j+1

> od;

> RETURN((a+b)/2)

> end;

Exemplu 7. Aplicăm procedura golden_section funcţiilor ϕ1, respectiv ϕ2

din exemplul 4 şi intervalelor date de listele I01, respectiv I02 obţinute ca urmare

a aplicării procedurii init (în exemplul 4):

> golden_section(phi1,I01,10^(-5));

1.500020428

> golden_section(phi2,I02,10^(-5));

0.00001292625968

Alt grup de metode pentru determinarea unui punct de minim al funcţiei

convexe ϕ se bazează pe echivalenţa: t* punct de minim <=> ′ϕ (t*) = 0. Ca

urmare pentru determinarea lui t* se poate aplica orice metodă de rezolvare a

ecuaţiei (neliniare) ′ϕ (t) = 0. Vom exemplifica cu metoda bisecţiei şi metoda

tangentei.

VII.1.2. Metoda bisecţiei

Metoda bisecţiei (metoda înjumătăţirii intervalului) presupune cunoscut

un interval [a0,b0] cu proprietatea că ′ϕ (a0) ′ϕ (b0) < 0. Pentru găsirea rădăcinii

ecuaţiei ′ϕ (t) = 0 se micşorează la fiecare pas intervalul în care funcţia ′ϕ îşi

schimbă semnul. Metoda bisecţiei presupune înjumătăţirea la fiecare pas a acestui

interval. Astfel

• se determină mijlocul c = 0 0a b

2

+ al intervalului (a0,b0).

• dacă ′ϕ (c) ′ϕ (a0)<0, atunci se continuă algoritmul cu intervalul [a0,c]

• dacă ′ϕ (c) ′ϕ (b0)<0, atunci se continuă algoritmul cu intervalul [c,b0]

• dacă ′ϕ (c) =0 s-a determinat o rădăcină a ecuaţiei ′ϕ (t) = 0.


13

Se construieşte astfel un şir de intervale [aj, bj], j≥0 cu lungimea lui Lj+1 = bj+1 –

aj+1 = 1

2Lj . Deci

jlim→∞

Lj= jj

1lim

2→∞L0 =0. În plus, fiecare din aceste intervale conţine

o soluţie a ecuaţiei ′ϕ (t) = 0. Presupunând că se dă o precizie ε>0, considerăm că

mijlocul intervalului [aj, bj] este o aproximaţie satisfăcătoare a soluţiei ecuaţiei

′ϕ (t) = 0 dacă Lj = bj –aj < ε. Numărul de iteraţii necesare pentru ca Lj < ε este nε

=( )

( )0ln L

ln 2

ε

+1.

ϕ convexă derivabilă

[a0,b0] cu ′ϕ (a0) ′ϕ (b0) < 0

ε > 0 dat – precizia de localizare a unui punct de minim t* al lui ϕ (sau

echivalent punct staţionar al lui ϕ)

a: = a0; b:=b0; nmax:=( )

( )ln b a

ln 2

− ε

+1; j: = 0;

cât timp j < nmax execută

c: =2

ba + ;

dacă ′ϕ (c) = 0 atunci a :=c; b:=c; j: = nmax+1;

altfel dacă ′ϕ (c) ′ϕ (a)<0 atunci b : = c; altfel a : = c;

j: = j+1;

t* ≈2

ba +

La ieşire c=2

ba + este o aproximaţie a unei rădăcini t* ∈(a0,b0) a ecuaţiei ′ϕ (t) = 0

cu eroarea absolută |t*-c| < 2

ε.

Procedura MAPLE bisection implementează algoritmul de mai sus.

Parametrii procedurii sunt: funcţia convexă ϕ, lista I0 cu punctele a0, b0 cu

proprietatea că ′ϕ (a0) ′ϕ (b0) < 0 şi precizia ε de localizare a unui punct de minim

al lui ϕ. Procedura întoarce o aproximaţie a unui punct staţionar (sau echivalent

punct de minim) al lui ϕ cu eroare cel mult 1

2ε.


14

> bisection:=proc(phi,I0,epsilon)

> local c,a,b,d,j,nmax;

> a:=evalf(I0[1]);b:=evalf(I0[2]);d:=D(phi);

> nmax:=ceil(ln(abs((b-a)/epsilon))/ln(2)); j:=0;

> while j<nmax do

> c:=(a+b)/2;

> if d(c)=0 then a:=c;b:=c;j:=nmax+1 else

> if evalf(d(c)*d(a))<0 then b:=c else a:=c fi fi;

> j:=j+1 od;

> c:=(a+b)/2;

> RETURN(c)

> end;

Exemplu 8. Aplicăm procedura bisection funcţiilor ϕ1, respectiv ϕ2 din

exemplul 4 şi intervalelor date de listele I01, respectiv I02 obţinute ca urmare a

aplicării procedurii init (în exemplul 4):

> evalf(D(phi1)(I01[1])*D(phi1)(I01[2]));

-3.

> bisection(phi1,I01,10^(-5));

1.500000000

> evalf(D(phi2)(I02[1])*D(phi2)(I02[2]));

-1.666666667

> bisection(phi2,I02,10^(-5));

0.

VII.1.3. Metoda tangentei (metoda lui Newton)

Prin metoda tangentei (metoda lui Newton) se determină o rădăcină a

unei ecuaţii h(t) = 0 ca limita unui şir. Se pleacă de la un punct t0 dat.

Presupunând că s-a construit termenul tj-1, termenul tj se determină ca fiind abscisa

intersecţiei dintre tangenta la graficul funcţiei h în tj-1 şi axa absciselor.


15

Presupunem că funcţia h: [a0, b0] → R este de 2 ori derivabilă şi că h′ nu se

anulează. Ecuaţia tangentei în tn-1 fiind:

y – h(tj-1) = h′ (xj-1)(x – xj-1)

rezultă (luând y = 0)

tj = tj-1 - ( )( )

j 1

j 1

h t

h t

−

−′.

Convergenţa şirului este determinată de termenul iniţial t0. Mai precis dacă t0 se

află într-o vecinătate suficient de mică a soluţiei t* a ecuaţiei h(t) = 0, atunci şirul

(tj)j converge la t*. Mai mult, avem

|t* - tj| ≤ ( )22

j j 11

Mt t

2m −−

unde m1 = [ ]

( )0 0t a ,b

h tinf∈

′ şi M2 = ( )0 0t [a ,b ]

h tsup∈

′′ .

Pentru rezolvarea ecuaţiei ′ϕ (t) = 0, şirul corespunzător metodei tangentei

este definit prin:

tj = tj-1 - ( )( )

j 1

j 1

t

t

−

−

′ϕ

′′ϕ, t0 dat

iar algoritmul corespunzător:

ϕ strict convexă de clasă C2

t00– dat (punct iniţial)

ε > 0 dat – precizia de localizare a unui punct de minim t* al lui ϕ (sau

echivalent punct staţionar al lui ϕ)

t0 : = t00;

tj tj-1


16

t1: = t0 - ( )( )

0

0

t

t

′ϕ′′ϕ

;

cât timp |t1 – t0 |2 ≥ ε execută

t0 := t1;

t1 : = t0 - ( )( )

0

0

t

t

′ϕ′′ϕ

;

La ieşire t1 este o aproximaţie a unei rădăcini t* a ecuaţiei ′ϕ (t) = 0 cu eroarea

absolută mai mică decât ε. Prezentăm în continuare o variantă a acestui algoritm

pentru cazul în care şirul construit nu converge. Introducem ca dată suplimentară

de intrare numărul maxim de termeni din şir ce urmează a fi calculaţi (Nmax) şi

afişăm termenul şirului corespunzător fiecărei iteraţii. Condiţia de oprire se

transformă

| tj - tj-1 |2 < ε sau n > Nmax

t0 : = t00;

t1: = t0 - ( )( )

0

0

t

t

′ϕ′′ϕ

;

j:=1;

cât timp (|t1 – t0 |2 ≥ ε) şi (j ≤ Nmax) execută

t0 := t1;

t1 : = t0 - ( )( )

0

0

t

t

′ϕ′′ϕ

;

j: = j+1;

afişează t1;

Trebuie verificat la ieşirea din ciclu dacă ′ϕ (t1) ≅ 0. Dacă problema este

bine condiţionată (adică ( )*

1

t′′ϕ mic), aceasta condiţie va asigura acurateţea

aproximaţiei.

Procedurile MAPLE corespunzătoare sunt prezentate mai jos:

> newton1:=proc(phi,t00,epsilon)

> local t0,t1,d1,d2;

> d1:=D(phi); d2:=D(d1);t0:=evalf(t00);t1:=t0-d1(t0)/d2(t0);


17

> while ((t1-t0)^2)>=epsilon do

> t0:=t1;t1:=t0-d1(t0)/d2(t0) od;

> RETURN(t1)

> end;

> newton1_:=proc(phi,t00,epsilon,Nmax)

> local t0,t1,d1,d2,j;

> d1:=D(phi); d2:=D(d1);t0:=evalf(t00);t1:=t0-d1(t0)/d2(t0); j:=1;

> while (((t1-t0)^2)>=epsilon) and (j<=Nmax) do

> t0:=t1;t1:=t0-d1(t0)/d2(t0); j:=j+1;

> print(t1) od;

> RETURN(t1)

> end;

Exemplu 9. Aplicăm procedura newton1 funcţiei ϕ1 din exemplul 4 cu

punctele iniţiale t0=0, respectiv t0 = 2 :

> newton1(phi1,0,10^(-5));

1.500000000

> newton1(phi1,2,10^(-5));

1.500000000

şi funcţiei ϕ2 din exemplul 4 cu punctele iniţiale t0=0.7, respectiv t0 = -0.7 :

> newton1(phi2,0.7,10^(-5));

-0.7398 10-10

> newton1(phi2,-0.7,10^(-5));

-0.7398 10-10

Aplicăm procedura newton1_ funcţiei ϕ1 cu punctele iniţiale t0=10 (număr

maxim de iteraţii 1) , respectiv t0 = 2 (număr maxim de iteraţii 1) :

> newton1_(phi1,10,10^(-5), 1);

1.500000000

1.500000000

> newton1_(phi1,-30,10^(-5),1);

1.50000000

1.50000000


18

precum şi funcţiei ϕ2 cu punctele iniţiale: t0=0.7 (număr maxim de iteraţii 5) , t0= -

0.7 (număr maxim de iteraţii 5) , t0=1.25 (număr maxim de iteraţii 5) , respectiv

t0= 1.05 (număr maxim de iteraţii 5): > newton1_(phi2,0.7,10^(-5),5);

-0.2400999999

-0.0576480102

-0.00332329345

-0.000011044830

-0.7398 10-10

-0.7398 10-10

> newton1_(phi2,-0.7,10^(-5), 5);

-0.2400999999

-0.0576480102

-0.00332329345

-0.000011044830

-0.7398 10-10

-0.7398 10-10

> newton1_(phi2,1.25,10^(-5),5);

-2.441406250

-5.960464478

-35.52713679

-1262.177449

-0.1593091913 107

-0.1593091913 107

> newton1_(phi2,1.05,10^(-5), 5);

-1.215506252

-1.477455449

-2.182874604

-4.764941536

-22.70466784

-22.70466784


19

Se observă că pentru punctele iniţiale t0 =1.25 şi t0 = 1.05 şirul construit prin

metoda lui Newton nu converge la punctul staţionar al funcţiei ϕ.

VII.2. Proceduri de alegere suboptimală a pasului

Procedurile de alegere suboptimală a pasului presupun determinarea

pasului tk din condiţia realizării unei reduceri semnificative (dar nu neapărat

optimale) a funcţiei f în direcţia vk (vk direcţie descendentă în xk) :

f(xk + tkvk) < f(xk)

Aşa cum am arătat mai înainte dacă f este diferenţiabilă şi vk este o direcţie

descendentă în xk, atunci există kλ >0 astfel încât pentru orice t ∈ (0, kλ )

f(xk + tvk) < f(xk).

Deci orice valoare tk∈(0, kλ ) satisface f(xk + tkvk) < f(xk). Să observăm însă în

exemplul următor ce se întâmplă dacă valorile tk sunt prea mici. Fie f : R → R, f(x)

= x2, x0 = 2, vk = -1, tk = k 1

1

2 + , xk+1 = xk + tkvk pentru orice k ≥ 0.

Deoarece paşii de deplasare tk sunt prea mici şirul construit xk = 2 - k

jj 1

1

2=∑

converge la 1 şi nu la punctul de minim x =0 al funcţiei f. Algoritmul de alegere a

lui tk prezentat mai jos previne situaţia în care pasul tk ar deveni „prea mic”.

tinit > 0 – valoare iniţială dată (de exemplu, tinit = 1 dacă domeniul de

definiţie al lui f este Rn)

β ∈ (0, 1) – dat (de exemplu, β = 1

2)

(x0, f(x0))

(x1, f(x1))

(x2, f(x2))


20

t: = tinit

cât timp f(xk+tvk) ≥ f(xk) execută

t : = t * β;

tk : = t;

Ca urmare tk va lua cea ai mare valoare dintre cele de forma tinitβj, j = 0,1,... care

îndeplineşte condiţia f(xk+tinitβjvk) < f(xk).

Pe de altă parte nici situaţia în care tk este „prea mare relativ la

descreşterea lui f” nu convine după cum rezultă din exemplul următor. Fie f:R→R,

f(x) = x2, x0 = 2, vk = (-1)k+1, tk = 2+k 1

3

2 + , xk+1 = xk + tkvk pentru orice k ≥ 0.

În acest exemplu paşi tk sunt prea mari relativ la valorile cu care descreşte f, iar

termenii xk = (-1)k + k

1

2 −

oscilează de o parte şi cealaltă a minimului. Şirul

(xk)k are două subşiruri convergente la 1 şi respectiv -1, fără ca vreunul din

punctele -1 sau 1 să fie punct de minim pentru f. Pentru a preveni această situaţie

se impune o condiţie mai tare decât simpla descreştere f(xk + tkvk) < f(xk), şi

anume:

f(xk + tkvk) ≤ f(xk) + tkδ<∇f(xk), vk> (10)

unde δ ∈ (0, 1). Condiţia (10) poartă denumirea de condiţia lui Armijo.

Algoritmul backtracking – Armijo (de căutare liniară) pentru determinarea

lui tk este redat mai jos:

tinit > 0 – valoare iniţială dată (de exemplu, tinit = 1)

(x0, f(x0))

(x1, f(x1))

(x2, f(x2))

(x3, f(x3)) (x4, f(x4))


21

β ∈ (0, 1) – dat (de exemplu, β = 1

2)

δ ∈ (0, 1) - dat (de exemplu, δ = 0.1 sau 10-4)

t: = tinit

cât timp f(xk+tvk) > f(xk) + tkδ<∇f(xk), vk> execută

t : = t * β;

tk : = t;

Procedura MAPLE suboptimal are drept parametri funcţia f, punctul xk, direcţia

descendentă vk, şi valorile tinit, β şi δ. Procedura întoarce pasul tk astfel încât

condiţia Armijo să fie verificată.

> suboptimal:=proc(f,xk,vk,tinit,beta,delta)

> local yk, tk,n,g,gk,xk1;

> n:=vectdim(xk);

>g:=grad(f(seq(x[i],i=1..n)),vector([seq(x[i],i=1..n)]));

>gk:=vector([seq(subs(seq(x[i]=xk[i], i=1..n),g[j]),j=1..n)]);

>yk:=evalf(f(seq(xk[i],i=1..n)));

>tk:=evalf(tinit);xk1:=vector(n);xk1:=evalm(xk+tk*vk);

> while f(seq(xk1[i],i=1..n))>yk+tk*delta*sum(gk[i]*vk[i],i=1..n)

> do tk:=tk*beta; xk1:=evalm(xk+tk*vk)

> od;

> RETURN(tk)

> end;

Aplicând această procedură funcţiei f1 : R2 → R, definită prin

f1(x,y) = 3x2+2y2 -2xy -4x +2y -3

> f1:=(x,y)->3*x^2+2*y^2-2*x*y-4*x+2*y-3;

:= f1 → ( ),x y + − − + − 3 x2 2 y2 2 x y 4 x 2 y 3

şi punctului xk = [0,0], direcţiei vk = [1,-1] şi luând tinit = 1, β = 0.5 şi δ =0.1

(respectiv δ = 0.45) obţinem:

> suboptimal(f1,vector([0,0]),vector([1,-1]),1,0.5,0.1);

0.5

> suboptimal(f1,vector([0,0]),vector([1,-1]),1,0.5,0.45);

0.25

Rămâne să arătăm că algoritmul de determinare a lui tk se termină într-un

număr finit de paşi şi că valoarea lui tk nu „devine prea mică”. În plus vom studia


22

convergenţa şirului construit (xk)k. Vom presupune că gradientul funcţiei f este o

funcţie Lipschitz continuă.

Definiţie 11. Fie V şi W două spaţii normate şi X ⊂ V o submulţime.

Funcţia F:X→W se numeşte Lipschitz continuă pe X dacă există o constantă γ>0

(numită constanta Lipschitz) astfel încât pentru orice x,y ∈X să avem:

||F(y) – F(x)|| ≤ γ||y-x||.

Este uşor de observat că orice Lipschitz continuă pe X este uniform

continuă pe X (în particular, continuă pe X).

Restricţia oricărei funcţii de clasă C1 la o mulţime compactă K este

Lipschitz continuă pe K (rezultă din teorema creşterilor finite).

Observaţie 12. Pentru funcţii având diferenţiale de ordinul 1, respectiv de

ordinul 2, Lipschitz continue sunt valabile următoarele formule Taylor:

• Presupunem că: X este o submulţime deschisă a lui Rn, f:X → R o funcţie

de clasă C1, ∇f Lipschitz continuă (cu constanta Lipschitz γL), x0∈X,

h∈Rn cu proprietatea că x0+λh∈X pentru orice λ ∈[0, 1] . Atunci

|f(x0 + h) - f(x0) - <∇f(x0), h>| ≤ 1

2γL||h||2

• Presupunem că: X o este o submulţime deschisă a lui Rn, f:X → R o

funcţie de clasă C2, Hf Lipschitz continuă (cu constanta Lipschitz γP),

x0∈X, h∈Rn cu proprietatea că x0+λh∈X pentru orice λ ∈[0, 1]. Atunci

|f(x0 + h) - f(x0) - <∇f(x0), h> -1

2<Hf(x0)h, h>| ≤

1

6γP||h||3

Teoremă 13. Fie X o submulţime deschisă a lui Rn, f: X→R o funcţie de

clasă C1 având gradientul ∇f Lipschitz continuu cu constanta Lipschitz γ şi fie

x∈X. Dacă δ∈(0, 1) şi v este o direcţie descendentă în x, atunci condiţia Armijo

este satisfăcută pentru orice t ∈[0, ( )x,vλ ], unde

( )x,vλ = ( ) ( )

2

2 1 v, f x

v

δ − < ∇ >

γ

(norma considerată fiind ||⋅||2).

Demonstraţie. Fie t∈∈[0, ( )x,vλ ]. Deoarece


23

f(x+ tv) - f(x) - t<∇f(x), v> ≤ |f(x+ tv) - f(x) - t<∇f(x), v>| ≤ 1

2γt2||v||2

rezultă că

f(x+tv) ≤ f(x) + t<∇f(x), v> + 1

2γt2||v||2

≤ f(x) + t<∇f(x), v> + 1

2γt

( ) ( )2

2 1 v, f x

v

δ − < ∇ >

γ||v||2

= f(x) + t<∇f(x), v> + t(δ-1) <v, ∇f(x)>

= f(x) + δt<v, ∇f(x)>

■

Corolar 14. Fie f: Rn →R o funcţie de clasă C1 având gradientul ∇f

Lipschitz continuu cu constanta Lipschitz γ şi fie xk∈X. Dacă β∈(0, 1), δ∈(0,1) şi

vk este o direcţie descendentă în xK, atunci pasul tk generat de algoritmul

backtracking-Armijo satisface condiţia

tk ≥ ( ) ( )k k

init 2k

2 1 v , f xmin t ,

v

β δ − < ∇ >

γ


Demonstraţie. Există două posibilităţi

1. tinit satisface condiţia Armijo şi atunci tk = tinit.

2. tinit nu satisface condiţia Armijo şi atunci tk este de forma tinitβi cu i∈N*.

Fie j cel mai mare număr natural cu proprietatea că

tinitβj > ( ) ( )k k

2k

2 1 v , f x

v

δ − < ∇ >

γ. (14.1)

Atunci

tinitβj+1 ≤ ( ) ( )k k

2k

2 1 v , f x

v

δ − < ∇ >

γ

şi conform teoremei precedente tinitβj+1 satisface condiţia Armijo. Aşadar

tk ≥ tinitβj+1 = β tinitβj ( )>

14.1

( ) ( )k k

2k

2 1 v , f x

v

β δ − < ∇ >

γ.


24

În consecinţă, în ambele cauze tk ≥ ( ) ( )k k

init 2k

2 1 v , f xmin t ,

v

β δ − < ∇ >

γ

.

■

Teoremă 15 (convergenţa algoritmilor de căutare liniară inexactă în

cazul generării pasului de deplasare prin algoritmul backtracking-Armijo).

Fie f: Rn → R o funcţie de clasă C1 având gradientul ∇f Lipschitz continuu i fie

x0∈X. Se construieşte şirul definit prin

xk+1 = xk + tkvk, k≥0

unde vk este o direcţie descendentă în xk, iar tk este pasul de deplasare obţinut

aplicând algoritmul backtracking-Armijo. Atunci are loc una din următoarele trei

situaţii:

1. ∇f(xk) = 0 pentru un anumit k ≥ 0

2. ( )k

kinf f x = - ∞

3. ( ) ( )k k

k k

kk

v , f xlim min v , f x ,

v→∞

< ∇ > < ∇ >

= 0


Demonstraţie. Presupunem că ( )k

kinf f x >-∞ şi că ∇f(xk)≠0 pentru orice

k≥0. Din condiţia Armijo rezultă că pentru orice k ≥ 0

f(xk + tkvk) ≤ f(xk) + tkδ<∇f(xk), vk>

f(xk+1) - f(xk) ≤ tkδ<∇f(xk), vk>

f(xk) - f(xk+1) ≥ - tkδ<∇f(xk), vk>.

Sumând după k se obţine

f(x0) - f(xj+1) ≥ ( )j

k kk

k 0

t v , f x=

− δ < ∇ >∑ .

Cu alte cuvinte şirul sumelor parţiale ale seriei cu termeni pozitivi

( )k kk

k 0

t v , f x∞

=

− δ < ∇ >∑ este mărginit, deci seria este convergentă şi ca urmare

termenul ei general converge la zero:


25

klim

→∞tk<∇f(xk), vk> = 0. (15.1)

Fie γ constanta Lipschitz asociată gradientului ∇f. Notăm

K1 = ( ) ( )k k

init 2k

2 1 v , f xk, t

v

β δ − < ∇ > > γ

K2 = ( ) ( )k k

init 2k

2 1 v , f xk, t

v

β δ − < ∇ > ≤ γ

.

Ţinând cont de corolarul 14, rezultă că pentru orice k ∈ K1 avem

tk ≥ ( ) ( )k k

2k

2 1 v , f x

v

β δ − < ∇ >

γ

( ) ( )k kkv , f x t

2 1

−γ< ∇ >

β − δ ≥

( ) 2k k

k

v , f x

v

< ∇ >

( ) ( )k k

kv , f x t2 1

−γ< ∇ >

β − δ ≥

( )k k

k

v , f x

v

< ∇ > (15.2)

Pentru orice k∈K2 avem tk ≥ tinit şi ca urmare

|<∇f(xk), vk>| = ( )k k

k

k

v , f x t

t

< ∇ >≤

( )k kk

init

v , f x t

t

< ∇ > (15.3).

Din (15.2) şi (15.3) rezultă că

0≤ ( ) ( )k k

k k

k

v , f xmin v , f x ,

v

< ∇ > < ∇ >

≤ ( ) ( ) ( )k k

kk kk

init

v , f x tmin v , f x t ,

2 1 t

< ∇ >−γ < ∇ > β − δ

.

Dar din (15.1) rezultă că

( ) ( ) ( )k kkk k

kk

init

v , f x tlim min v , f x t ,

2 1 t→∞

< ∇ >−γ < ∇ > β − δ

= 0


26

şi ca urmare ( ) ( )k k

k k

kk

v , f xlim min v , f x ,

v→∞

< ∇ > < ∇ >

= 0

■

Observaţie 16. După cum rezultă teorema anterioară algoritmul

backtracking-Armijo (prin care tk este cel mai mare număr de forma tinitβi (cu

i∈N) care satisface condiţia Armijo) asigură convergenţa metodelor de căutare

liniară inexactă, dacă se impun condiţii suplimentare asupra lui f (f să fie

mărginită inferior) şi asupra direcţiei vk astfel încât din condiţia 3 a teoremei 15 să

rezulte convergenţa la 0 a şirului (∇f(xk))k sau măcar a unui subşir al acestuia.

Există însă şi alte modalităţi pentru a evita ca tk să devină prea mic sau prea mare

(relativ la descreşterea lui f) .

Se spune că tk satisface condiţiile Wolfe dacă

f(xk + tkvk) ≤ f(xk) + tkδ1<∇f(xk), vk> (17a)

<∇f(xk + tkvk), vk> ≥ δ2<∇f(xk), vk> (17b)

cu 0 < δ1 < δ2 < 1 (de exemplu, δ1 = 10-4 şi δ2 = 0.9 dacă direcţia vk este aleasă

printr-o metodă de tip Newton sau δ2 = 0.1 dacă direcţia vk este aleasă prin

metoda de gradientului conjugat).

Se spune că tk satisface condiţiile Wolfe în sens tare dacă

f(xk + tkvk) ≤ f(xk) + tkδ1<∇f(xk), vk> (18a)

|<∇f(xk + tkvk), vk>| ≤ δ2|<∇f(xk), vk>| (18b)

cu 0 < δ1 < δ2 < 1.

Se spune că tk satisface condiţiile Goldstein dacă

f(xk) + tk(1-δ)<∇f(xk), vk> ≤ f(xk + tkvk) ≤ f(xk) + tkδ<∇f(xk), vk> (19)

cu 0 < δ < 1

2. Un dezavantaj al condiţiilor lui Goldstein relativ la condiţiile Wolfe

este acela că prima dintre inegalităţi poate exclude toate punctele de minim ale

funcţiei ϕ (ϕ(t) = f(xk + tvk)). Condiţiile Goldstein se utilizează în cazul metodei

Newton, dar nu sunt potrivite pentru metodele cvasi-Newton. De asemenea

algoritmul backtracking-Armijo este foarte potrivit metodei Newton, dar mai

puţin potrivit metodele cvasi-Newton sau de gradient conjugat (ce vor fi descrise

în subcapitolul următor).


27

Ca şi în cazul algoritmului backtracking-Armijo, condiţiile Wolfe nu sunt

suficiente pentru a asigura convergenţa indiferent de alegerea direcţiilor vk.

Următoarea teoremă datorată lui Zoutendijk stă la baza rezultatelor privind

convergenţa diverselor metode în care paşii de deplasare satisfac condiţiile Wolfe.

Teoremă 20 (convergenţa algoritmilor de căutare liniară inexactă în

cazul în care pasul de deplasare satisface condiţiile Wolfe) Fie f:Rn→R o

funcţie de clasă C1 având gradientul ∇f Lipschitz continuu cu constanta Lipschitz

γ şi fie x0∈X. Se construieşte şirul definit prin

xk+1 = xk + tkvk, k≥0

unde vk este o direcţie descendentă în xk, iar pasul de deplasare tk îndeplineşte

condiţiile Wolfe (17a, 17b) pentru orice k≥0. Atunci are loc una din următoarele

trei situaţii:

1. ∇f(xk) = 0 pentru un anumit k ≥ 0

2. ( )k

kinf f x = - ∞

3. Seria

( ) ( )2

2 kk

k 0

cos f x≥

θ ∇∑

este convergentă. În particular, klim

→∞( ) ( ) 2

2 kkcos f xθ ∇ =0, unde

cos(θk) = ( )

( )k k

k k

f x ,v

f x v

− < ∇ >

∇.

Demonstraţie. Presupunem că ( )k

kinf f x >-∞ şi că ∇f(xk)≠0 pentru orice

k≥0. Datorită condiţiilor Wolfe, mai precis, din (17b) rezultă că

<∇f(xk + tkvk) - ∇f(xk), vk> ≥ (δ2-1) <∇f(xk), vk> (20.1)

Din faptul că ∇f este Lipschitz continuă, rezultă că

||∇f(xk + tkvk) - ∇f(xk)|| ≤ γtk||vk||

de unde,

<∇f(xk + tkvk) - ∇f(xk), vk> ≤ γtk||vk||2. (20.2)

Din (20.1) şi din (20.2) obţinem inegalitatea


28

tk ≥ 2 1δ −γ

( )k k

2k

f x ,v

v

< ∇ >,

şi folosind prima condiţie Wolfe (17a) rezultă mai departe

f(xk + tkvk) ≤ f(xk) + 2 1δ −

γ

( )( )2k k

2k

f x ,v

v

< ∇ >δ1

Dacă notăm c = 21

1− δδ

γ şi ţinem cont că xk + tkv

k = xk+1 obţinem

f(xk+1) ≤ f(xk) - c( )( )2

k k

2k

f x ,v

v

< ∇ >

iar sumând după k şi ţinând seama că cos(θk) = ( )

( )k k

k k

f x ,v

f x v

− < ∇ >

∇, rezultă

f(xk+1) ≤ f(x0) - c ( ) ( )2k

2 jj

j 0

cos f x=

θ ∇∑

( ) ( )2k

2 jj

j 0

cos f x=

θ ∇∑ ≤ 1

c(f(x0) - f(xk+1))

Cu alte cuvinte şirul sumelor parţiale ale seriei cu termeni pozitivi

( ) ( )2

2 kk

k 0

cos f x≥

θ ∇∑ este mărginit, deci seria este convergentă şi ca urmare

termenul ei general converge la zero: klim

→∞( ) ( ) 2

2 kkcos f xθ ∇ =0.

■

Observaţie 21. Rezultate similare teoremei precedente se obţin în cazul în

care pasul tk satisface condiţiile Goldstein pentru orice k ≥ 0 sau condiţiile Wolfe

în sens tare pentru orice k ≥ 0. Şi în cazul acestor strategii dacă f este mărginită

inferior, fie ∇f(xk) = 0 pentru un anumit k, fie este îndeplinită condiţia

seria ( ) ( )2

2 kk

k 0

cos f x≥

θ ∇∑ convergentă (22)

numită condiţia Zoutendijk.

Observaţie 23. Încheiem acest subcapitol cu un comentariu asupra alegerii

lui tinit (prima încercare pentru determinarea pasului tk). Indiferent de strategie


29

(backtracking-Armijo, Wolfe (sau Wolfe în sens tare), Goldstein), dacă metoda de

determinare a direcţiei este de tip Newton sau cvasi-Newton, atunci tinit = 1. În

cazul metodelor gradientului sau gradientului conjugat este important ca la fiecare

pas să se ţină cont de informaţia curentă. Astfel tinit la pasul k (adică cel folosit

pentru determinarea lui tk) poate fi luat

tk-1 ( )

( )k 1 k 1

k k

f x ,v

f x ,v

− −< ∇ >

< ∇ > sau

( ) ( )( )( )

k k 1

k 1 k 1

2 f x f x

f x ,v

−

− −

−

< ∇ >.

vii. metode numerice de rezolvare a problemelor de optimizare fără

Documents