toppart2

Algoritmi de optimizare multi-variabile (multi-dimensionala) fara constrangeri

• Alg. Deterministi: evolutia algoritmului este unic

determinata; pasii/etapele care se execute sunt mereu aceleasi indiferent de cate ori se repeta algoritmul pentru aceeasi problema data,cu aceeasi initializare, rezultatul este mereu acelasi.

• Alg. Stocastici: evolutia algoritmului este infuentata

de valori/parametrii cu caracter aleator; repetarea algoritmului pentru aceasi problema conduce la evolutii diferite, putandu-se obtine si rezultate diferite.

Algoritmi opt. multi-dim. deterministi

Fiind data fct. ob.: f(x): n se cauta x* minxf(x)

Structura generala a algoritmilor (Alg. descrestere):

– La iteratia k ne situăm într-un punct xk n

– Se determina o direcţie convenabilă de căutare dk

– Se stabileste lungimea pasului de căutare k care conduce la o valoare mai mica a functiei obiectiv

f( xk + k dk) < f( xk)

Obs: de multe ori k se obtine prin optimizarea 1D a functiei f( ) = f( xk + dk ) (line search)

– Se calculeaza noul punct: xk +1 = xk + k dk

– Se reia procesul iterativ pana la convergenta

Algoritmi opt. multi-dim. deterministi

• Nederivativi

– Proprietati de convergenta slabe

– Volum de calcul mare

– Avantaj major: NU necesita acces/estimare derivate

• Derivativi

– Folosind derivata I

– Folosind derivata II

Algoritmi optimizare M-Dim nederivativi Algoritmul de cautare pe axele de coordonate (Baniciuc)

Fie versorii axelor e i = (0 … 0 1 0 … 0)T (pozitie i)

Definim setul de directii de cautare { d 2i

= e i , d 2i+1 = - e i } i = 1…n

1. Se aleg: punctul initial x0 , pasul de inaintare p > 0 precizia de cautare > 0, rata de diminuare a pasului p 0 < < 1

2. k = -1

3. pentru i = 1… 2n

repeta (Avansare pe directia di cu pasul p

k = k + 1 cat timp functia descreste)

xk+1 = xk+ p di

cat timp f( xk+1 ) < f( xk )

k = k - 1

Algoritmi optimizare M-Dim nederivativi

Algoritmul de cautare pe axele de coordonate (Baniciuc)

4. Daca dupa o parcurgere a pasului 3 nu se face nicio inaintare

Atunci se diminueaza pasul de inaintatre p = p

Altfel

daca p <

atunci STOP

5. Se reia procesul

de cautare pe axe

de la punctul 3


Algoritmul de optimizare pe axele de coordonate

(Coordinate Descent Method, Metoda cautarilor ciclice)

Esenta: Cautarea repetata pe directiile versorilor cu optimizarea 1D pe fiecare directie

Setul directiilor de cautare: { di = e i } i = 1…n

1. Se aleg: punctul initial x0, precizia de cautare >0, k=0

2. pentru i = 1… n se determina optimul pe directia de cautare di

optimizare 1D a functiei f( ) = f( xk + di ) (line search)

se calculeaza noul punct: xk +1 = xk + k di , k = k + 1

3. Daca || xk – xk-n || < atunci STOP

altfel reia de la punctul 2

Algoritmi optimizare M-Dim nederivativi Algoritmul de optimizare pe axele de coordonate

Convergenta este dependenta de functia obiectiv si punctul initial. Accidental converge rapid (in cativa pasi), insa cel mai des apare un proces lent de convergenta, cu deplasari in zig-zag cu pasi din ce in ce mai mici in propierea punctului de optim.

IMPORTANT este faptul ca metoda converge mereu.


Algoritmul de optimizare pe axele de coordonate

Variante de imbunatatire:

• Metoda dublu ciclica a lui Aitken: Se minimizeaza succesiv in raport cu d1, d2, ..., dn, si apoi inapoi dn, dn-1, ..., d1, si apoi se repeta in conditiile algoritmului clasic

• Metoda Gauss–Southwell: La fiecare pas se minimizeaza coordonata corespunzatoare celei mai mari descresteri.


Cautare ciclica (pe axele de coordonate) cu pas de accelerare (Pattern search)

Algoritm general (Powell ?!)

Metode constă în intercalarea între două etape

de căutare ciclică după axele de coordonate, a

unui pas accelerat în care căutarea se face după

direcţia impusă de dreapta care uneşte punctele

initial si final din căutarea ciclica anteriora.

AVANTAJ: creste viteza de convergenta prin

eliminarea pasilor mici facuti in zig-zag, mai

ales in vecinatatea pct de optim.

opt x2

opt x1

opt x1

opt x2

pas acc.

pas acc.


Cautare ciclica (pe axele de coordonate) cu pas de accelerare

Setul directiilor de cautare pe axe: { di = e i } i = 1…n



f( ) = f( xk + di ) (line search)

xk +1 = xk + di , k = k + 1

3. Opt. pe directia d= xk – xk-n

f( ) = f( xk + d) (line search)

xk +1 = xk + d , k = k + 1

4. Daca || xk – xk-n-1 || <

atunci STOP

altfel reia de la punctul 2

Algoritmi optimizare M-Dim nederivativi Algoritmul Hooke si Jeeves (Caz particular Cautare ciclica cu pas de accelerare)

1. Se aleg: punctul initial x0 , pasii de inaintare pe fiecare axa pi > 0 precizia de cautare > 0, rata de diminuare a pasilor pi 0 < < 1 , k =1

2. Etapa k de explorare dupa axe:

i = 1 (ciclu dupa nr. de coordonate)

2.1. x' = x(k,i-1) + pi (k)

ei (explorare in dir. pozitiva cu pas discret )

Daca f( x' ) < f( x(k,i-1) ) atunci salt la pas 2.2.

Altfel x' = x' - 2 pi (k)

ei (explorare in dir. negativa cu pas discret )

Daca f( x‘ ) < f( x(k,i-1) ) atunci salt la pas 2.2.

Altfel x' = x' + pi (k)

ei (revenire la punctul initial )

2.2. Se retine valoarea mai buna dupa cautarea pe axa i

x(k,i) = x'


Daca i < n atunci i = i+1 (urmatoare directie/coord.)

salt la pas 2.1.

3. Testare esuare totala in optimizarea pe cele n directii

Daca f( x(k,n) ) f( x(k,0) ) atunci salt la pas 9.

4. Pas accelerat (pas extrapolare)

x(k+1,0) = x(k,n) + ( x(k,n) - x(k,0) )

SAU varianta: x(k+1,0) = x(k,n) + ( x(k,n) - x(k-1,n) )

OBS.: Pasul accelerat se face in mod OBLIGATORIU

NU se verifica succesul sau, se accepta asa cum este

5. pi (k+1) = pi

(k) sign( xi (k,n) - xi

(k,0)), k = k + 1, i = 1

SAU varianta: pi (k+1) = pi

(k) sign( xi (k,n) - xi

(k-1,n))


6. Explorare vecinatate dupa extrapolare (cautare pe axe):

6.1. x' = x(k,i-1) + pi (k)

ei (explorare in dir. pozitiva cu pas discret )

Daca f( x' ) < f( x(k,i-1) ) atunci salt la pas 6.2.

Altfel x' = x' - 2 pi (k)

ei (explorare in dir. negativa cu pas discret )

Daca f( x‘ ) < f( x(k,i-1) ) atunci salt la pas 6.2.

Altfel x' = x' + pi (k)

ei (revenire la punctul initial )

6.2. Se retine valoarea mai buna dupa cautarea pe axa i

x(k,i) = x'

Daca i < n atunci i = i+1 (urmatoare directie/coord.)

salt la pas 6.1.


7. Testare esuare totala in optimizarea pe cele n directii

dupa extrapolare

Daca f( x(k,n) ) f( x(k,0) ) atunci

revenire la pozitia dinaintea pas extrapolare:

x(k+1,0) = x(k-1,n)

pi (k+1) = pi

(k) pt. i = 1, n

salt la pas 10 (reluare proces cautare de la inceput)

(Altfel…. Pas 8)


8. In caz de success a etapei de extrapolare, retinem val.:

x(k+1,0) = x(k,n)

Daca |xi (k,n) - xi

(k-1,n) | < |pi (k)| / 2 pt. i=1,n atunci

salt la pas 9 (testare terminare algoritm)

Altfel salt la pas 4 (se mai face un pas de extrapolare)

9. Daca pi (k) < pt. i =1, n atunci STOP

Altfel pi (k+1) = pi

(k) pt. i =1, n (Micsorare pas de cautare!!)

10. k = k + 1, salt la pas 2

Algoritmi optimizare M-Dim nederivativi Cu modificarea setului de directii de cautare

Algoritmul Powell


Setul initial de directii de cautare: { di = e i } i = 1…n




3. Se calculeaza intregul m, 1 m n, a.i.

= f( xm-1) - f ( xm) = maxj { f( xj-1) - f ( xj ) }

4. Se calculeaza/noteaza: f1 = f ( x0 )

f2 = f ( xn )

f3 = f ( 2xn - x0 )


Algoritmul Powell (obs: Modification by Sargent, Zangwill din L2-Unconstrained.pdf)!

5. Daca || xn – x0 || < atunci STOP

( altfel continua pas 6)

6. Daca f3 f1 sau ( f1 -2 f2 + f3 ) ( f1 - f2 - )2 ( f1 - f3 ) 2

atunci continuam cu acelasi directii de cautare { di } i = 1…n

x0 = xn

Altfel def. noua directie de cautare: d = ( xn – x0 ) / || xn – x0 ||

opt. 1D functiei f( ) = f( xn + d ) (line search)

se calculeaza noul punct: x0 = xn + d

se inlocuieste directia dm cu d

7. Salt la pas 2


Metoda Rosenbrock

După efectuarea unui ciclu complet de căutare, în funcţie de rezultatele

obţinute, se construieste un nou sistem de coordonate (vectori

ortogonali, liniar independenţi, de normă unitară) după care se face

căutarea.


Setul initial de directii de cautare: { di = e i } i = 1…n




Algoritmi optimizare M-Dim nederivativi Metoda Rosenbrock

3. Daca || xn – x0 || < atunci STOP

Altfel se determină noile direcţii de căutare:

2

1

0

0

1

1

jpentruddaa

jpentrua

b

d

d

a

j

i

jjjj

j

j

j

n

ji

ii

jj

j

j

j

jb

bd

noile directii sunt:

4. Salt pas 2

Algoritmi optimizare M-Dim nederivativi Comparatie intre metode f(x1, x2)=( x1 – 3 ) 4+ ( x1 – 3 x2 )

2

Cautare

ciclica

25 pasi


2

Pas de

accelearre

9 pasi


2

Rosenbrock

6 pasi

Algoritmi optimizare M-Dim nederivativi Algoritmul Nelder-Mead

Metoda se bazeaza pe modificarea succesiva a unui simplex din spatiul

variabilelor de control, care se restrange si converge catre optim.

Se defineste un simplex in spatiul Rn, un set de n+1 puncte:

{ xi } i = 1,n+1

Obs.: (a) NU trebuie confundata aceasta metoda cu metoda SIMPLEX pentru

optimizarea problemelor definite prin n functii obiectiv liniare de n variabile.

(b) Din punct de vedere geometric, un simplex corespunde unui hiper-poliedru

in spatiul n-dimensional

In R2 avem

un triunghi

In R3 avem

un tetraedru

http://upload.wikimedia.org/wikipedia/commons/4/45/Triangle_illustration.svg


Vârfurile simplexului { x1, ..., xn , xn+1 } sunt indexate in ordinea

crescatoare a functiei obiectiv, deci:

f ( x1 ) f ( x1 ) ... f ( xn ) f ( xn+1 )

Se calc. centroidul primelor n varfuri (se exclude pct. cel mai prost):

n

iic xx

1

1

n


Se definesc 4 operatii prin care se incearca modificare simplexului,

a.i. sa cuprinda valori mai bune (mici):

(A) reflexia punctului xn+1 fata de

centroidul xc

xr = xc + (xc – xn+1 )

Scalarul > 0 se numeste factor de reflexie (usual = 1 )

Daca f ( x1 ) f ( xr ) f ( xn )

atunci xn+1 se inlocuieste cu xr


(B) expansiune punctului xn+1 fata de centroidul xc

Daca f ( xr ) < f ( x1 )

Reflexia este mai buna decat cel mai bun

punct al simplexului, se incearca o cautare

mai departara pe aceeasi directie

xe = xc + (xr – xc )

Scalarul 1 se numeste factor de expansiune (usual 2.8 3 )

Daca f ( xe ) f ( xr ) atunci xn+1 se inlocuieste cu xe

Altfel ( f ( xe ) > f ( xr ) si f ( xr ) < f ( x1 ))

xn+1 se inlocuieste cu xr


(C) contractia punctului xn+1 fata de centroidul xc

Daca f ( xn+1 ) f ( xr ) f ( xn ) Reflexia este buna, insa se incearca o cautare

pe aceeasi directie intr-o vecinatate mai apropiata

(*) xt = xc – (xn+1 – xc )

Altfel

Daca f ( xr ) f ( xn+1 )

Reflexia nu aduce imbunatatire a simplexului

se incearca o cautare pe aceeasi directie intr-o

vecinatate mai apropiata, insa in partea opusa a

centroidului

(**) xt = xc + (xn+1 – xc )

Scalarul 0 < < 1 se numeste factor de contractie (usual 0.4 0.6 )


Deciziile:

(*) Daca f ( xt ) < f ( xr ) atunci

xn+1 se inlocuieste cu xt

Altfel

xn+1 se inlocuieste cu xr

(**) Daca f ( xt ) < f ( xn+1) atunci

xn+1 se inlocuieste cu xt

Altfel

pas / modificare (D)


(D) Reducerea simplexului

Verificare conditie STOP

Daca NU este verificata cond STOP atunci

se contracta tot simplexul in jurul punctului x1

xi = x1 – (xi – x1 ) pt. i=1,n+1

Scalarul 0 < < 1 se numeste factor de reducere (usual =0.5 )


Conditie STOP (multe posibilitati)

Daca s < atunci STOP

Altfel

Se continua modificarea simplexului

prin reluarea pasilor (A)-(D)

1

1

1 n

iixf

1n

1

1

2))((1 n

ii fxfs

1n

Algoritmi optimizare M-Dim derivativi

Structura algoritmilor este la fel: se determina directii de

descrestere pe care se inainteaza

Teorema: O directie p este o directie de descrestere pentru o

functie obictiv f intr-un punct x daca proiectia gradientului

pe directia p in punctul respectiv este negativa.

Dem.:

Dezv. in serie Taylor:

f( x + p ) = f( x ) + g( x )T p + …

f( x + p ) – f( x ) = g( x )T p

Pentru a avea o directie de descrestere trebuie ca: f( x + p ) < f( x )

Deci: g( x )T p < 0; cum: >0, rezulta: g( x )T p < 0


Met. Southwell, Bromberg, Synge din Tehnici de optimizare.doc !

Metoda gradientului negativ

Se alege directia de descrestere

p = – g(x)

Algoritmul: xk+1 = xk – g(xk )

unde scalarul (0, 1] este constant

Discutie dupa (Tehnici de optimizare.doc pag 87)


Metoda celei mai mari (abrupte) descresteri (Cauchy)

(Steepest descent, Optimal gradient)

Se doreste gasirea celei mai bune metode de descrestere, se aplica o

tehnica de tip Greedy: optimizarea locala a parametrilor:

(a) Directia de descrestere cea mai buna (cea mai mare) este:

p = – g(x) = – f(x)

(b) Pasul de inaintare cel mai bun (care conduce la valoarea cea mai

mica) este dat te optimizarea 1D a functiei obictiv f pe directia de

cautare p:

f(* ) = min f( x + p )

Dem (a): pp. avansare pe o directie de descrestere oarecare d. Atunci viteza de

descrestre in punctul x este data de

dxf

xfdxfdxf )(

)()(lim),('

0



Pentru care trebuie sa gasim optimul (cea mai rapida descrestere, cea mai mare in

modul, este vorba despre un minim)

Inegalitatea lui Schwartz :

Pentru : se obtine:

care este limita inferioara a intervalului anterior, deci val. de minim.

Algoritm:

La fiecare pas k:

Optimizare 1D: f(k* ) = min f( xk – k g(xk ) )

Avansare pe directie: xk+1 = xk – g(xk )

Verificare conditie STOP

)()()( xfdxfdxf

)(

)(

xf

xfd

)(

)(

)()()( xf

xf

xfxfdxf



Lema: Directiile de descrestere consecutive sunt ortogonale.

Dem.: Optimizare 1D a functiei: f( ) = f( x k – g(xk ) )

Adica:

In concluzie: cele 2 directii consecutive sunt ortogonale

0 k

d

df

k

kkk

kkk

kkk

k

kkk

d

d

d

df

d

df

d

df

k

)(

)(

)()( gx

gx

gxgx

0)( 1 k

T

kk

T

kkk

f gggxgxx

01 k

T

k gg



f(x) = 0.5 x12 + 2.5 x2

2



Convergenta:

pp. o functie patratica de forma:

unde: Q este o matrice simetrica pozitiv definita

Functia f are derivata: si, optimul:

Functia f se poate rescrie:

unde s-a definit functie eroare

Obs.: este o constanta pozitiva , deci:

f(x) si E(x) au acelasi optim si f(x) < E(x)

bx x xxT-Qf T

2

1)(

b x1* Q

*T**T***xQ x -x xQ x -x x x x x

2

1

2

1

2

1)( )(E)-(Q)-(f T

*T*xQ x

2

1

b x x)g -Q(

)-(Q)-(E T **x x x x x

2

1)(



Convergenta (cont.):

Optimizarea 1D a functiei f() = f( xk – g(xk) ), unde:

Cond. de optim este:

Care conduce la solutie:

bxgx xgx xgxxgxT

kkkkkkkk ))(())(())((2

1))(( Qf T

)(Q)(

)()(T

T

kk

kkk

xgxg

xgxg

0 k

d

df




Evaluam :

Se aplica teorema (inegalitatea) lui Kantorovich:

Fie Q o matrice simetrica si pozitiv definita care are valorile

proprii: 0 < a = 1 2 … n = A

atunci:

)-(Q)-(E T *

1k

*

1k1k x x x x x2

1)(

)()(

2

1

)()()()(

)()(1

1

2

**

xxxxxgxgxgxg

xgxg

k

T

k

k

T

kk

T

k

k

T

k QQQ

21

2

)(

4

Aa

aA

)Q()Q(

)(TT

T

xxxx

xx




Cum:

Rezulta:

De la aceasta relatie se ajunge la: (TEMA: aratati cum ?)

2

2)(

41

aA

aA

Aa

aA

)()(

2

1 kk EaA

aAE xx

)()(

2

1 kk faA

aAf xx




Concluzie: in cazul functiilor patratice, metoda steepest descent

converge liniar cu o rata de convergenta mai mica de

Obs.: (a) convergenta este cu atat mai lenta cu cat curbele de nivel

constant ale lui f sunt mai excentrice (asimetrice)

(b) pentru cazul in care aceste sunt cercuri (a=A), convergenta

se face intr-un singur pas

(c) chiar daca n - 1 valori proprii sunt egale, dar una singura

este la mare distanta de ele, convergenta este lenta

2

aA

aA

Algoritmi optimizare M-Dim derivativi Metoda celei mai mari (abrupte) descresteri (Cauchy)


Toate aceste concluzii/observatii se aplica doar functiilor patratice.

Cu toate acestea vom extinde aceste proprietati si la functii

nepatratice folosind in locul matricii Q Hessianul functiei obiectiv

evaluat intr-un punct solutie .

Concluzie: Fie f : RnR , f C2 avand un minim local in x*. Pp. ca

Hessianul are cea mai mica valoare proprie a > 0 si cea mai mare

valoare proprie A > 0. Daca { xk } este un sir generat de metoda

celei mai abrupte pante care converge la x*, atunci f(xk) converge

la f(x*) liniar cu o rata de convergenta mai mica sau egala cu 2

aA

aA

Algoritmi optimizare M-Dim derivativi Metoda celei mai mari (abrupte) descresteri (Cauchy)


Viteza de convergenta nu este mare, depinde de forma functiei

obiectiv si de punctul initial.

Principalul dezavantaj este deplasarea

pe directii ortogonale (in zig-zag), ceea

ce face metoda foarte lent convergenta

in vecinatatea punctului de optim.

Generic se accepta ca algoritmul converge suficient de rapid in

zonele departate de punctul de optim.

Algoritmi optimizare M-Dim derivativi Metode de gradient conjugat (Conjugate Gradient Methods)

Se incearca imbunatirea vitezei de convergenta prin inlaturarea

avansarii pe directii ortogonale (zig-zag), utilizand alte directii

de cautare.

Directii conjugate: un set de vectori {di} se numesc conjugate in

raport cu o matrice A (A-conjugate), daca

diT A dj = 0 pentru orice i j

Teorema: Pentru o matrice A simetrica si pozitiv definita, orice set de

n directii A-conjugate dintr-un spatiu n-dim. sunt si liniar

independente

Algoritmi optimizare M-Dim derivativi Metode de gradient conjugat (Conjugate Gradient Methods)

Pentru inceput se considera cazul functiilor patratice:

matricea Q este simetrica si pozitiv definita

Gradientul este:

Optimul respecta ecuatia de anulare a gradientului:

cQf T bx x xxT

2

1)(

b x xx)g Qf( )(

0b *x x*)g Q(

Algoritmi optimizare M-Dim derivativi Metode de gradient conjugat (cont.)

Fiind date: un punct initial x0 si

un set de directii Q-conjugate {d0, d1, …, dn-1},

atunci se pot determina constantele i astfel incat sa se realizeze

descompunerea:

Dem.: relatia de mai sus se inmulteste la stanga cu djTQ, rezulta:

1-n

0ii0 d xx* i

1-n

0ii0 dd xdx*d i

T

j

T

j

T

j QQQ

j

T

j

T

j

T

j QQ dd xdbd j0


De unde rezulta constantele:

Formula demonstrata anterior determina valorea de optim intr-un

singur pas, printr-un calcul “global”, care impune cunoasterea

tuturor directiilor de cautare si a pasilor de avansare pe fiecare

directie in acelasi timp.

Ne intereseaza dezvoltarea unui algoritm iterativ pentru determinarea

optimului folosind directii conjugate, in care sa calculam si sa aplicam

pe rand fiecare directie si pas de inaintare

j

T

j

j

T

j

T

j

jT

jQQ

Qdd

dxg

dd

dxb

0

0

)()(


Astfel, pentru o functie patratica

daca alegem: un punct initial x0 si

un set de directii Q-conjugate {d0, d2, …, dn-1},

se doreste un algoritm interativ in care se fac pasii succesivi de

optimizare: xk+1 = xk + k dk

Pasii de intaintare k se fac prin optimizare 1D pe directia dk a

functiei: f( ) = f( xk + dk)

Prin anularea derivatei in raport cu se obtine:

cbx x xxT Qf T

2

1)(

0)( 1

k

T

k fd

df

k

xd


Tinand cont de:

Si ca: xk+1 = xk + k dk

Rezulta: dkT (b + Q( xk + k dk ) ) = 0

Deci:

Care este legatura intre k si k ???

Reamintim:

bxx 11)( kk Qf

k

k

k

kkk

QQQ(

dd

dg

dd

dxb

T

k

T

k

T

k

)

k

kk

Q dd

dg

T

k

T

0


Astfel, prin cumularea pasilor facuti succesiv la ultimul algoritm, se la

pasul k se obtine deplasarea totala, relativa la punctul initial :

relatia de mai sus se transpune si se inmulteste la dreapta cu Q dk,

rezulta:

Deci: = 0

1-k

0ii0k d xx i

k0

1-k

0ikik0kk dxdd dxdx

QQQQ T

i

TT

dd

dxb

dd

dg

T

k

T

k

T

k

k

kT

k

k

kk

QQ(

Q)

k

k

k

k

kT

QQQ(

dd

dg

dd

dxb

T

k

T

0

T

k

)0


Cum am obtinut ca k = k , rezulta ca dupa n pasi facuti cu

algoritmul iterativ se obine valoarea de optim:

Concluzii: (a) Aplicarea metodelor de gradient conjugat pentru cazul

functiilor obiectiv patratice, conduce la determinarea valorii de optim

in n pasi, daca calculele se fac exact (se spune ca se utilizeaza o

aritmetica exacta = nu se fac erori de rotunjire, erori de reprezentare

numerica, etc.)

(b) Teorema de Expandare a Subspatiilor: Coeficientii

din descompunere in raport cu un set de directii Q-conjugate

corespunde pasilor de inaintare obtinuti prin optimizare 1D pe aceleasi

directii, indiferent de pctul initial x0

*xd xd xx1-n

0ii0

1-n

0ii0n

ii


(c) Se observa ca gkTdi = 0 pentru i < k, ceea ce arata ca

la fiecare pas, gradientul curent este liniar independent fata de

(ortogonal pe) directiile conjugate anterioare. Ceea ce ofera o metoda

de generare a directiilor conjugate in raport cu directiile anterioare:

La pasul k se evalueaza gradientul negativ si se adauga unei

combinatii liniare de directii precedente pentru a obtine o noua

directie conjugata de-a lungul careia se face deplasarea.

Algoritmi optimizare M-Dim derivativi Metoda gradientilor conjugati

Se aplica functiilor patratice

Algoritm:

1. Initializare x0

2. Calculeaza: directia initiala de cautare: d0 = - g( x0 )

Obs.: primul pas este echivalent cu Steepest Descent

3. Pentru k = 0, 1, 2, ….

k

T

k

k

T

k

Q dd

dgk

cbx x xxT Qf T

2

1)(

Algoritmi optimizare M-Dim derivativi Metoda liniara a gradientilor conjugati (cont)

xk+1 = xk + k dk

dk+1 = - gk+1 + k dk

pana la convergenta ( ex. || gk || < )

Varianta (Oara):

2

2

111

k

k

k

T

k

k

T

k

g

g

gg

ggk

k

T

k

k

T

k

Q

Q

dd

dgk

1

Algoritmi optimizare M-Dim derivativi Metoda liniara a gradientilor conjugati

Se doreste eliminarea estimarii gradientului la fiecare pas printr-o

formula de calcul recurent:

Se aplica functiilor patratice

La fiecare pas se caluleaza val. reziduala:

care trebuie sa tinda catre zero.

Algoritm:

1. Initializare x0

2. Calculeaza: reziduul initial:

directia initiala de cautare: d0 = r0

)() xgbx r (Q

cbx x xxT Qf T

2

1)(

)(Q)( bx xgr 000

Algoritmi optimizare M-Dim derivativi Metoda liniara a gradientilor conjugati (cont)

3. Pentru k = 0, 1, 2, ….

xk+1 = xk + k dk

rk+1 = rk - k Q dk

dk+1 = rk+1 + k dk

pana la convergenta ( ex. || rk || < )

2

2

111

k

k

k

T

k

k

T

k

r

r

rr

rrk

k

T

k

k

T

k

Q dd

drk

Algoritmi optimizare M-Dim derivativi Metoda gradientilor conjugati pt functii nepatratice

Aproximarea patratica

La fiecare pas se face o aproximare patratica a functiei obiectiv,

adica matricea Q se inlocuieste cu Hessianul Hk = H( f( xk ) )

Cand se aplica problemelor nepatratice, metodele GC nu se vor

termina dupa n pasi si atunci avem urmatoarele posibilitati:

• Continuam sa gasim directii conform algoritmului G–C pana cand

un anumit criteriu de oprire este indeplinit;

• Algoritmul se opreste dupa n (sau n+1) pasi si se restarteaza cu un

pas de metoda de gradient (cea mai abrupta panta). criteriu de

oprire este indeplinit; se continua pana la convergenta


Aproximarea patratica. ALGORITM

1. Initializare x0

2. Calculeaza: directia initiala de cautare: d0 = - g( x0 )

Obs.: primul pas este echivalent cu Steepest Descent

3. Pentru k = 0, 1, 2, ….

xk+1 = xk + k dk

kk

T

k

k

T

k

H dd

dgk

2

2

111

k

k

k

T

k

k

T

k

g

g

gg

ggk


Aproximarea patratica. ALGORITM

dk+1 = - gk+1 + k dk


Varianta (Oara):

Avantaje: Nu sunt necesare cautari unidimensionale la nici un pas;

Algoritmul converge intr-un numar finit de pasi pentru o problema patratica.

Dezavantaje: Hessianul Hk trebuie evaluata la fiecare pas (O(n2));

Algoritmul nu este global convergent.

kk

T

k

kk

T

k

H

H

dd

dgk

1


Metode care nu se bazeaza pe evaluarea Hessianul

In cazul anterior evaluarea Hesianului este necesara pentru calcularea

pasului k.

Eliminarea acestei operatii se poate face prin obtinerea pasului k

printr-o cautare 1D, echivalenta conform teoriei dem. anterior.

Mai mult, ne asteptam ca prin aceasta tehnica rezultatele sa fie mai

bune, atat timp cat formula era dedusa pentru cazul functiilor patratice

si dorim sa o aplicam pentru functii nepatratice


Metode care nu evaluaza Hessianul. Algoritm general

1. Initializare x0

2. Calculeaza directia initiala de cautare: d0 = - g0

3. Pentru k = 0, 1, 2, ….

Calculeaza k prin optimizarea 1D a functiei f() = f( xk + dk )

xk+1 = xk + k dk

Calculeaza k

dk+1 = - gk+1 + k dk



Metode care nu evaluaza Hessianul. Algoritm general

Exista mai multe formule de calcul a coeficientului k (toate formulele

sunt echivalente pentru functia patratica)

Fletcher-Reeves

Polak–Ribiere

Sorenson Wolfe (Beale, Hestenes, Stiefel)

k

T

k

k

T

k

gg

ggk

11

k

T

k

kk

T

k

gg

gggk

)( 11

)(

)(

1

11

kk

T

k

kk

T

k

ggd

gggk


Metoda Fletcher-Powell

Foloseste o metoda actualizare (iterativa) a unei matrice care in final

converge la inversul Hessianul functiei obiectiv din punctul de optim.

1. Initializare x0, F0 orice matrice pozitiv definita (de ex. In)

2. Pentru k = 0, 1, 2, ….

dk = - Fk g(xk)

Calculeaza k prin opt. 1D a functiei f() = f( xk + dk )

k = k dk

xk+1 = xk + k

Fk+1 = Fk + Ak + Bk


Metoda Fletcher-Powell

unde: yk = g (xk+1 ) - g (xk )

Obs.:

(1) Pentru orice k matricea F este pozitiv definita.

(2) Pentru cazul functiei obiectiv patratice directiile dk sunt F-conjugate , conducand astfel la solutia de optim in n pasi

(3) sirul de matrice { Fk } converge catre inversul matricei Hessiene; pentru cazul patratic, dupa n pasi: Fn = H-1( f( x* ))

k

T

k

T

kkAyσ

σσk

k

T

k

T

kkByFy

FyyF-

k

kkk

Algoritmi optimizare M-Dim derivativi Metode de tip Newton. (Metode de derivata a II-a)

Metoda clasica

Se face aproximarea functiei obiectiv prin seria Taylor trunchiata la

termenul de gradul 2

în care H( xk ) reprezintă hessianul funtiei obiectiv f( xk ) evaluat în xk

Conditia de optim pentru aproximarea pătratică este:

Daca H( xk ) este inversabila, atunci solutia de optim pentru

aproximarea patratica, care devine urmatorul punct de aproximare,

este:

))(()(2

1))(()()()( kkkkkk Hffqf xxxxxxxxxxx

0))(()()( kkk Hfq xxxxx

)()(1

1 kkkk fH xxxx

Algoritmi optimizare M-Dim derivativi Metode de tip Newton. Metoda clasica

Observatii:

1. Daca functia obiectiv este patratica, atunci optimul se gaseste intr-

un singura iteratie (pas)

2. Daca pe parcursul etapelor intermediare procesului de optimizare

apare situatia unei matrice hessien H( xk ) care nu poate fi inversate

atunci procesul de optimuizare se blocheaza. Trebuie gasite alte solutii

pentru continuarea procesului.

3. Complexitatea calculului este O(n3), data de necesitatea inversarii

hessianului, mult mai mare decat in cazul metodelor de gradient

negativ.

4. Volumul de memorie necesat este O(n2), mai mare decat in

majoritate metodelor de gradient negativ

Algoritmi optimizare M-Dim derivativi Metode de tip Newton. Metoda clasica

Observatii:

5. Dacă hessianul este lipschitzian într-o vecinătate a optimului, atunci

metoda Newton are o convergenţă pătratică.

6. Daca hessianul H( xk ) nu este pozitiv definit, atunci directia de

cautare fie nu exista, fie nu este o directie de descrestere. In acest caz

se inlocuieste hessianul cu o aproximare care respecta conditia de

pozitiv definit

7. Domeniul de convergenţă este mai redus faţă de tehnicile de

gradient. Metoda funcţionează mai bine în apropierea punctului de

optim. De aici si ideea combinarii celor e metode: aplicarea metodei

steepest descent in zona departata de optim si aplicarea metodei

Newton in apropierea punctului de optim

Algoritmi optimizare M-Dim derivativi Metoda Newton discreta. (met. Gauss-Newton) !!

Metoda Newton clasica = metoda pur matematica, performantele sala

sunt obtinute teoretic, intr-o aritmetica exacta.

In practica, apar erori de calcul, de aproximari si de reprezentare in

memoria calculatorului, care fac ca metoda sa nu mai aiba aceleasi

performante.

De asemenea, in situatiile in care nu exista acces direct la valorile

gradientilor si a matricelor hessiane, acestea sunt aproximate. Astfel,

de exemplu, coloanele matricei hessiene H( xk ) se aproximeaza:

unde: i = 1 … n, ei versorul in directia i

)()(1~

kiik

i

xgexghi

Algoritmi optimizare M-Dim derivativi Metoda Newton discreta.

Apare problema alegerii intervalului mic i, in urma careia apar 2

tipuri de erori:

(a) eroarea de rotunjire proportionala cu 1/i (calc.impartire)

(b) eroarea de trunchiere proportionala cu i (aprox. derivata)

Avand in vedere ca cele doua tipuri de erori sunt contrarii, o balansare

optima intre cele doua conduce in final la o eroare de estimare a

Hessianului de:

unde: m este eroarea de reprezentare a masinii de calcul.

mO


Alta problema care poate aparea este simetrizarea matricei hessiene,

care in urma erorilor de calcul in timpul estimarii poate rezulta

asimetrica. Astfel daca in urma estimarii se obtine matricea:

Atunci aproximarea simetrica este:

In aceasta situatie, metoda Newton discreta tinde catre o convergenta

patratica pentru i tinzand catre zero. Astfel ca desi valoarea lui i

trebuie sa fie cat mai mica, ea este limitata de eroarea de rontunjire.

]~~~

[~

21 h ... h h k nH

T

kHHH~~

2

1ˆ kk


Alta problema apare cand gradientul are valori foarte mici (inevitabil

in zona de optim el tinde catre zero) cand numaratorul este foarte mic

si apar erori la operatia de impartire a doua valori foarte mici

Concuzie

In situatie calcului numeric, metoda Newton discreta tinde catre o

convergenta patratica pentru I tinzand catre zero, insa performantele

sunt suboptimale. Astfel ca, de exemplu, pentru o functie patratica

este posibila o convergenta in mai mult de 1 pas (cat ar trebui sa fie

teoretic)

Algoritmi optimizare M-Dim derivativi Metode de tip Newton modificate

Metoda Newton nu este neapărat convergentă. Unul dintre motive ar fi

că matricea hessiana H( xk ) estimata local este singulară în xk şi prin

urmare nu poate fi determinata solutia Newton xk+1 cu care sa

continuam algoritmul de optimizare.

O alta situatie (relativ similara) este cand, desi se poate determina H -1

in punctul xk , rezulta f( xk +1) > f( xk ) (TEMA: Explicati cand??)

In astfel de situatii, cand algoritmul Newton clasic are probleme de

continuare, se pot folosi variante MODIFICATE, in se incearca

evitarea problemelor mentionate mai sus (si nu numai).


A. Metoda Newton modificata, cu cautare liniara

In cazul in care functia obiectiv nu este patratica, punctul curent de

aproximare este departe de solutia de optim, ne asteptam ca

aproximarea de gradul doi a functiei obiectiv sa fie grosiera (cu

eroare mare), iar aplicarea unui pas Newton clasic poate conduce la un

urmator punct cu probleme d.p.v. al convergentei. In aceasta situatie, o

solutie care inlatura macar partial problemele posibile este:

a) pastrarea directie de inaintare data de solutia Newton,

b) avansarea cu un pas determinta printr-o optimizare 1D

Astfel:

unde : k se determina prin optimizarea 1-D (line search) a functiei

. obiectiv pe directia

Obs.: In cazul fct. patratice, se va obtine k=1, adica metoda clasica

)(1

1 kkkkk fH xxx

)(1

kk fH x


B. Metoda Newton modificata clasica

Caz particula al metodei anterioare, in care, din motive de micsorare a volumului de calcul, se calculeaza pasii folosind aceeasi matrice hessiana, cea estimata la primul pas:

Astfel:

unde : k se determina prin optimizarea 1-D (line search) a functiei . obiectiv pe directia:

Obs.: Metoda este suficient de buna si eficienta daca hessianul Hk nu variaza prea mult de-a lungul procesului de optimizare.

Cu siguranta algoritmul este bun in vecinatatea pct. optim unde aceasta conditie este valabila.

Daca Hk variaza mult, erorile conduc la o convergenta lenta; alternativa ar fi estimare lui Hk la un nr.de pasi (Discutie, cum alegem nr de pasi, fix, variabil)

)()( 0

1

1 kkkk fH xxxx

)(1

0 kfH x


C. Metoda Newton modificata (Metoda Levenberg-Marquardt).

In cazul in care matricea hessiana H( xk ) estimata local este singulară

în xk şi prin urmare nu poate fi determinata solutia Newton xk+1 cu

care sa continuam algoritmul de optimizare, se inlocuieste matricea

hessiana cu alta care sa poata fi inversabila:

Pe de alta parte ne dorim ca noua matrice sa aproximeze cat se poate

de bine hessianul, pentru a pastra proprietatile de convergenta

Exista mai multe posibilitati de a determina o astfel de matrice Bk, o

posibilitate este:

knk HIB

)(1

1 kkkkk B xgxx

Algoritmi optimizare M-Dim derivativi Metoda Newton modificata.

In cazul in care Hk nu este inversabila, atunci se determina , astfel

incat pentru un > 0 dat, este cea mai mica valoare pozitiva care

face ca cea mai mica valoare proprie a matricei ( In+Hk ) sa fie mai

mare ca .

Metoda Goldfeld calculeaza val proprii ale lui Hk si alege mai

mare decat val. proprie cea mai negativa.

Astfel matricea ( In+Hk ) este simetrica si pozitiv definita, deci

inversabila si se poate demonstra ca directia de cautare -Bk-1

g(xk) este

o directie de descrestere.


Obs.: Am obtinut o familie de posibile directii de descrestere, in

functie de :

Insa interesant este ca aceste directii variaza intre:

• solutia Newton (daca exista) care se obtine pentru = 0

• solutia de gradient negativ (Steepest Descent) pentru >> 0

Poza la tabla !!!

)()( 1

kkn HI xg


Exemplu: Fie f o functie care in punctul ξ = (1,−2)T are parametrii:

Modelul patratic la functiei in punctul curent este (Tema: dem.) :

f(ξ) q( ξ ) = x12 + x2

2

Aplicarea unui pas Newton clasic conduce la solutia (0,0) care

corespunde unei directii de crestere (deci nedorita)

Un calcul rapid arata ca valorile proprii ale hessianului sunt:

{-2, 2}

20

02

4

2Hf

Algoritmi optimizare M-Dim derivativi Metoda Newton modificata. Exemplu (cont.):

Alegerea unei constate

= 3 (>2) conduce la

matricea

obtinand directia de

cautare:

d = −B−1∇ f =

=(−2/5, −4)T

Obs.: este directia obt.

prin metoda

Steepest Descent

10

05B

Algoritmi optimizare M-Dim derivativi Metode de tip Quasi-Newton.

O noua abordare a problemei gasirii unor metode intermediare intre

metoda celei mai abrupte pante si metoda lui Newton. Acestea sunt

din nou motivate de dorinta de a accelera convergenta tipic lenta a

metodei celei mai abrupte pante in paralel cu evitarea evaluarii,

memorarii si inversarii Hessianului cerute de metoda lui Newton.

Ideea principala aici este sa folosim o aproximatie a inversei

Hessianului in locul inversei exacte.

Aceasta metode sunt cele mai sofisticate metode disponibile.

Analiza convergentei este relativ complicata si ne vom rezuma doar la a prezenta

principalele caracteristici.


Se scrie dezvoltarea in serie Taylor pentru gradient:

gk+1 = gk + Hk (xk+1 – xk )

Se noteaza: qk = gk+1 – gk si pk = xk+1 – xk

Rezulta: qk = Hk pk (numita ecuatia secantei)

sau: Hk -1qk = pk

Aceasta relatie arata ca diferenta de gradient dintre 2 puncte

consecutive furnizeaza informatie referitoare la matricea hessiana.

Aceasta informatie va fi folosita pentru determinarea unei relatii

recurente de aproximare succesiva a hessianului SAU a inversei

hessianului in punctul de optim.

Vom presupune sirul de aproximari { Bk } ale inversei Hk -1


Daca matricea hessiana ar fi constanta, atunci ecuatia secantei trebuie

respectata pentru toate directiile anterioare, adica:

Conditiile Quasi-Newton: Bk+1 qi = pi pentru 0 i k

Aceste conditii sunt necesare, insa pentru cazul n-dim NU si suficiente

pentru determinarea matricei de aproximare Bk+1

Sistemul de ecuatii obtinut are mai multe necunoscute decat conditii

impuse, deci este un caz de nedeterminare, prin urmare exista o

infinitate de solutii.

Obs.: numai pentru cazul 1-dim. exista solutie unica, aceasta conducand la metoda

secantei.


In final trebuie sa cautam o relatie de recurenta de tipul:

Bk+1 = Bk + Uk (qk , pk , Bk )

in care: U(qk , pk , Bk ) este o matrice de actualizare/corectare a matricei

Bk de la pasul anterior, si care, confort ecuatiei secantei, depinde de

variatia de gradient qk , deplasarea variabilelor de control pk si matricea

curenta Bk

Reamintim ca matricea hessiana Hk, respectiv inversa sa Hk-1, sunt

matrice simetrice si prin urmare, pornind cu o matrice initiala

simetrica, toate matricele de actualizare Uk trebuie sa fie simetrica.

Avand in vedere situatia de nedeterminare, solutiile se vom detrmina

impunand anumite constrangeri suplimentare:


Metoda matricei simetrice de rang 1 (SR1 - Symmetric Rank 1)

O prima metoda se obtine prin impunerea conditiei ca matricea de

actualizare sa fie de rang 1, adica poate fi scrisa ca produs de doi

vectori:

Uk = uk vkT

din conditia de simetrie, rezulta ca cei doi vectori trebuie sa fie egali:

Uk = k vk vkT

Deci se cauta o formula de recurenta de forma:

Bk+1 = Bk + k vk vkT

Aceasta formula trebuie sa respecte ecuatia secantei:

pk = Bk+1 qk = Bk qk + k vk vkT qk

Cum inca sistemul este nedeterminat, alegem in mod convenabil:


Metoda matricei simetrice de rang 1 (SR1 - Symmetric Rank 1)

Alegem in mod convenabil: k vkT qk = 1 , adica :

Situatie in care ecuatia anterioara se rescrie:

pk = Bk qk + vk

Din care se determina: vk = pk – Bk qk

Astfel relatia de actualizare a metodei SR1 este:

Obs.: Aceasta formula de actualizare pastreaza pozitivitatea doar daca:

qkT (pk – Bk qk ) > 0

k

T

k qv k

1

k

T

kkk

T

kkkkkkk

SR

k)B(

)B()B(BB

qqp

qpqp

1

1


Metoda Davidon –Fletcher–Powell ( DFP )

(Metoda de metrica variabila)

Este o procedura de corectie de rang 2, deci matricea de actualizare va

fi suma a doua matrice de rang1, in plus se tine cont si de conditia de

simetrie, in final obtinandu-se relatia de actualizare:

Bk+1 = Bk + k vk vkT + k uk uk

T

Se verifica ecuatia secantei:

pk = Bk+1 qk = Bk qk + k vk vkT qk + k uk uk

T qk

Fiind inca in situatie de nedeterminare, alegem convenabil:

k vkT qk = 1 si k uk

T qk = – 1

Adica:

k

T

k qv k

1

k

T

k qu k

1



(Metoda de metrica variabila)

Dupa alegerea scalarilor k si k ecuatia secantei se rescrie:

pk = Bk qk + vk – uk

Alegem convenabil: vk = pk

si rezulta: uk = Bk qk

Deci formula de actualizare a metodei DFP :

k

T

k

T

kk

k

T

k

T

kkk

DFP

kB

BBBB

qq

qq

qp

pp

k

kk

1



Proprietatile metodei DFP

• Daca Bk > 0 , atunci Bk+1 > 0

• Daca f este functie patratica, deci Hessianul H este constant, atunci

metoda DFP produce directii pk care sunt H–conjugate. Daca

metoda executa n pasi, atunci Bn = H -1.

• Deoarece pk sunt H–ortogonali si deoarece minimizam f succesiv

de-alungul acestor directii, observam ca procedura este de fapt o

metoda de gradienti conjugati (Fletcher-Powell) si conform

proprietatilor acestei metode, procesul iterativ converge exact in n

pasi.

• p0, p1, ..., pk sunt vectori proprii corespunzatori unor valori proprii unitare

pentru matricea Bk+1H. Acesti vectori proprii sunt liniar independenti deoarece

sunt H–ortogonali si prin urmare Bn = H-1.


Metoda Broyden–Fletcher–Goldfarb–Shanno ( BFGS )

Presupunand ca dorim determinarea unui set de matrice { Hk } care

care sa convearga la hessianul , putem scrie ecuatia secantei:

qk = Hk+1 pk (*)

Sau echivalent: Hk +1-1qk = pk, renotata: Bk+1 qk = pk,

(**)

unde { Bk } este sirul de matrice convergent la inversa hessianului H-1

Se observa ca prima (*) si a treia (**) relatie sunt practic

echivalente cu schimbarile de notatie:

Hk+1 Bk+1

pk qk

qk pk



Prin urmare solutia de aproximare cu matrice de rang 2 a matricei

hessiane inverse (DFP):

Conduce (prin schimbarea de notatie anterioara) la solutia de

aproximare cu matrice de rang 2 a matricei hessiene

k

T

k

T

kk

k

T

k

T

kkk

DFP

kB

BBBB

qq

qq

qp

pp

k

kk

1

k

T

k

T

kk

k

T

k

T

kk

H

HHHH

pp

pp

pq

qq

k

kkk1k



Cum aproximarea hessianului nu este utila in calcularea

solutiei/pasului Newton, se va determina inversa acestei aproximari

folosind formula Sherman–Morrison :

Se obtine astfel o noua formula de aproximare a inveresei

hessianului cu o matrice de corectie de rangul 2, numita formula

Broyden–Fletcher–Goldfarb–Shanno ( BFGS ) (TEMA: calcul

detaliat!)

ab1

baba

1

1111

A

AAAA

T

TT

k

T

k

T

kk

T

kk

k

T

k

T

kk

k

T

k

kk

T

kBFGS

k

BBBBB

pq

pqqp

qp

pp

pq

qq kk

k

11



Proprietati. Observatii.

• Formula BFGS poate fi folosita in mod identic cu formula DFP;

• Cele doua formule sunt teoretic echivalente, fiind formule de

aproximare a inveresi hessianului cu matrice de corectie de

rangul 2

• Experimente numerice au indicat ca performantele BFGS sunt

superioare formulei DFP;


Familia de functii Broyden. Metoda Broyden.

Ambele formule DFP si BFGS contin corectii de rang 2 simetrice ce se

construiesc din vectorii pk si Bk qk .

Prin urmare o combinatie liniara ponderata a acestor formule va fi de

acelasi tip (simetrica, rang 2, construita pe baza lui pk si Bk qk ),

obtinandu-se o colectie de formule de actualizare a inversei

hessianului, numita familia de functii Broyden:

B 1 BDFP + BBFGS


Familia de functii Broyden. Metoda Broyden.

O metoda Broyden este definita ca o metoda quasi–Newton in care la

fiecare iteratie un membru al familiei Broyden este folosit ca formula

de actualizare. In general, parametrul variaza de la o iteratie la alta si

prin urmare trebuie sa specificam sirul 1, 2, … care determina

functia Broyden la fiecare pas.

O metoda Broyden pura foloseste un constant. Deoarece BDFP si

BBFGS satisfac ecuatia sencatei, atunci aceasta relatie este satisfacuta de

toti membrii familiei Broyden.

Obs.: Metodele DFP si BFGS sunt si ele cazuri (particulare) de

metode Broyden pure ( 0 , respectiv 1 )

Algoritmi optimizare M-Dim derivativi Algoritmul Quasi-Newton

1. Initializare x0, B0, matrice simetrica pozitiv definita (usual In )

2. Pentru k = 0,1, 2, …

2.a. Calculeaza directia de inaintare: sk = – Bk gk

2.b. Determina pasul de inaintare prin optimizare 1D a functiei f( ) = f( xk + sk )

2.c. Calculeaza: qk = gk+1 – gk , pk = xk+1 – xk

2.d. Folosind una dintre formulele de actualizare (SR1, DFP, BFGS, Broyden, …) se calculeaza:

Bk+1 = Bk + Uk (qk , pi , Bk )

3. Pana la convergenta (ex.: daca || gk || < atunci STOP)

Obs.: Metodele Quasi-Newton au convergenta superliniara (<N, >SD)

In practica pot aparea probleme de convergenta (de ex. DFP este sensibil la exactitatea determinarii pasului de inaintare din optimizarea 1D)

Algoritmi optimizare M-Dim derivativi Metode partiale de tip Quasi-Newton

Metodele de tip Quasi_Newton pot fi restartate la fiecare m+ 1 < n

pasi, obtinandu-se metode partiale de tip quasi–Newton.

Pentru m mic, acestea necesita memorie modesta intrucat aproximatia

inversei Hessianului poate fi memorata implicit prin memorarea

vectorilor pi si qi, i < m + 1.

In cazul patratic aceasta corespunde exact cu metoda partiala de

gradienti conjugati si are proprietati similare de convergenta.

Algoritmi optimizare M-Dim derivativi Metode Quasi-Newton fara memorie

O simplificare a metodei quasi–Newton (ex. BFGS) este aceea in care

Bk+1 este actualizat folosind In in locul lui aproximarii anterioare Bk.

Astfel Bk+1 este determinat fara referinta la precedentul Bk si prin

urmare actualizarea se numeste fara memorie.

Algoritm:

1. Initializare x0

2. Pentru k = 0, 1, 2,…

2.a. Bk = In

2.b. Calculare directie de inaintare: dk = – Bk gk

2.c. Minimizare 1D a functiei f( xk +dk) in raport cu 0

(trebuie ales k suficient de precis pentru a asigura pkT qk > 0,

unde pk = k dk si qk = gk+1 – gk ).


3. Daca s-a det. optimul (ex.: || gk || < ) atunci STOP, altfel:

3.a. Daca k nu este multiplu de n atunci calculam

k = k +1 salt la pasul 2.b.

3.b. Daca k este multiplu de n atunci salt la pasul 2.a.

k

T

k

T

kk

T

kk

k

T

k

T

kk

k

T

k

k

T

kk IB

pq

pqqp

qp

pp

pq

qq n

11


Daca introducem formula de actualizare de la 3.a. in formula

determinarii directiei de cautare de la 2.b. se obtine:

Daca fiecare cautare unidimensionala este exacta, atunci pkT gk+1 = 0

si prin urmare pkT qk = – pk

T gk si prin urmare formula de mai sus se

poate rescrie:

Cum: pk = k dk

k

T

k

T

kk

T

kk

k

T

k

T

kk

k

T

k

k

T

kk

pq

gpqgqp

qp

gpp

pq

qqgd 1k1k1k

1k

11

k

T

k

T

kk

qp

gqpgd 1kk

1k

1

k1k

1k dqd

gqgd

k

T

k

T

kk 1


Formula se poate rescrie:

unde :

Corespunzand algoritmului de gradienti conjugati Sorenson Wolfe

(Beale, Hestenes, Stiefel), cu care astfel am demonstrat ca este

echivalent metoda Quasi-Newton BFGS fara memorie, in care

optimizarea 1D este exacta

)(

)(

1

11

kk

T

k

kk

T

k

ggd

gggk

k1kkk

1k dgdqd

qggd

k

k

T

k

T

kk 1

1


Se poate extinde aceasta idee si pentru obtinerea unei formule de

actualizare Broyden fara memorie, de forma:

Obs.: Aceasta metoda este echivalenta cu metoda de gradienti

conjugati doar pentru = 1, corespunzand actualizarii BFGS

k1k

k1k

1k ppq

gqq

qq

gqgd

k

T

k

T

k

k

T

k

T

kk )1(1

Algoritmi optimizare M-Dim derivativi Metoda Newton trunchiata.

In cazul functiilor obiectiv nepatratice, metoda Newton se aplica

repetitiv. De aceea, la fiecare pas de aproximare NU este nevoie sa se

determine o solutie Newton exacta (cu eroare foarte mica), atat timp

cat aceasta oricum se calculeaza pe o aproximare patratica (care

implica o eroare) a functiei obiectiv.

Astfel, la cautarea pe directia pk, se introduce o valoare reziduala

rk = || Hk pk + gk ||, care in cazul solutiei optime trebuie sa fie zero, insa

pentru eficientizarea calcului, se accepta o aproximare in limita:

rk = || Hk pk + gk || < || gk ||, cu (0,1]

toppart2

Documents