METODE DE OPTIMIZARE A FUNCTIILOR DE N VARIABILE

METODE DE OPTIMIZARE A FUNCTIILOR DE N VARIABILE

1. Conditii de optimalitate

Fie functie de n variabile, continua si diferentiabila. Caracterizarea punctului de minim atins de F este realizata in termenii vectorului gradient si a matricei Hessian,

, notat in continuare cu g sau cu , respectiv

, matrice notata in continuare cu G sau

Observatie. In cazul in care F este dublu diferentiabila, matricea Hessian G este simetrica.

Definitia 1. Matricea simetrica A este pozitiv definita daca si numai daca, pentru orice , are loc relatia,

.

Definitia 2.Fie functie de n variabile si cu proprietatile,

(1) si este pozitiv definita.

Atunci este punct de minim local al lui F.

Daca o functie F are mai multe minime locale (puncte ce indeplinesc (1)), atunci minimul global este acel minim local pentru care este obtinuta cea mai mica valoare a lui F.

Observatie. Problema RISCMIN0 poate fi rezolvata prin abordare analitica, astfel. Deoarece functia gradient este,

,

valoarea optimala a lui x este obtinuta prin rezolvarea sistemului liniar,

2. Metode directe de cautare a optimului

In general, in problemele de optimizare a portofoliilor, vectorul gradient si matricea Hessian pot fi in general calculate, functiile obiectiv fiind in general dublu diferentiabile. Pentru situatiile de acest gen sunt folosite metode de tip gradient. In cazul in care optimizarea nu poate fi realizata prin utilizarea relatiilor (1), o varianta de rezolvare a problemelor de optimizare o constituie metodele de cautare directa, bazate exclusiv pe analizarea valorile functiei obiectiv.

Cautarea directa a valorii minime a unei functii obiectiv F este realizata prin evaluarea lui F in punctele unei "retele" de valori posibile ale vectorului variabila a functiei. Desi metodele de acest tip nu sunt in general eficiente, exista situatii in care valoarea minima poate fi aproximata prin considerarea unei variante a lui F discretizata pe un set de puncte "aleatoare" si utilizarea unor argumente de natura statistica pentru estimarea probabilitatii de determinare a minimului intr-n anumit numar de incercari.

Cautarea univarianta

Metoda implica utilizarea unei metode directe de cautare (ca, de exemplu, metoda bisectiei) pentru generarea unei secvente de tip minimizarea unidimensionala a lui F astfel incat, la fiecare etapa i, , F este minimazat in raport cu . Cu alte cuvinte, punctul optim este cautat de-a lungul directiilor date de fiecare coordonata pe rand. Desi uneori metoda functioneaza eficient, ea nu poate fi general aplicabila deoarece nu este convergenta.

Metoda Hooke si Jeeves

Tehnica Hooke&Jeeves utilizeaza metoda cautarii univariante si pe baza urmatorului rationament. Daca sunt estimari ale punctelor de minim ale lui la momentul initial, respectiv la momentul final al ciclului de cautare, atunci minimizarea unidimensionala a alui F este realizata pe directia printr-o estimare de tipul

(2),

unde este o constanta scalara. Metoda continua prin efectuarea ciclurilor de cautare univarianta urmate de estimari de forma (2).

Metode de aproximare a derivatelor

Una dintre cele mai uzuale metode de minimizarea a lui exclusiv pe baza valorilor functiei F este prin adaptarea metodelor de tip gradient la estimarile de tip diferenta finita ale derivatelor functiei. De exemplu, pentru derivatele de ordinul I poate fi utilizata estimarea diferenta centrata,

Abordarile care implica estimarea derivatelor functiei obiectiv sunt dezvoltate pe baza presupunerii ca F este diferentiabila. In plus, metodele din aceasta clasa nu sunt in general aplicate problemelor pentru care derivatele functiei F nu sunt functii continue.

3. Metode de tip gradient

Asa cum a fost mentionat in sectiunea 1, in problemele de optimizare a portofoliilor functiile obiectiv sunt dublu diferentiabile si relatiile (1) pot fi verificate. Optimizarea functiilor in n variabile si care indeplinesc proprietatile din definitia 2 poate fi realizata prin metode de tip gradient. Sunt prezentate in continuare metoda celei mai rapide (abrupte) descresteri si metoda Newton. Ambele metode presupun constructia cate unui sir care, in anumite conditii de regularitate impuse functiei obiectiv, converge catre solutia optimala a problemei de optimizare.

Metoda celei mai rapide descresteri

Tehnica celei mai rapide descresteri este justificata geometric astfel. Presupunem ca este functia de minimizat si este punctul construit la momentul curent. Un punct "mai bun" (in sensul ca valoare functiei obiectiv descreste in acel punct fata de punctul curent) poate fi determinat prin deplasarea pe directia de cautare care determina descresterea cea mai rapida a lui F, adica pe directia gradientului negativ.

Metoda celei mai rapide descresteri de tip "perfect line search" este descrisa astfel. (Bartholomeu-Biggs, 2005)

Selecteaza , estimare initiale a punctului de minim al lui si

Repeat for

calculeaza care minimizeaza

aplica regula de actualizare

Until

Observatie. O serie de metode de optimizare utilizeaza in constructia sirului tipare similare celui prezentat in algoritmul de mai sus, si anume fiecare iteratie consta in doua etape: alegerea directiei de cautare (calculul lui ) si respectiv procedura de determinare a demarcatiei (line search) in scopul stabilirii unei valori adecvate a pasului .

Definitia 3. Procedura de determinare a demarcatiei care minimizeaza se numeste perfecta sau exacta.

Definitia 4. O procedura de determinare a demarcatiei prin care este acceptata orice valoare a pasului s care indeplineste,

si este marginita

se numeste inexacta sau slaba.

In continuare este prezentata teorema de convergenta a metodei.

Propozitia 1. Fie o functie dublu diferentiabila, cu derivatele continue si marginita inferior si pentru care este indeplinita proprietatea

pentru orice vector , unde este constanta scalara. Atunci sirul definit prin,

()

este cu proprietatea

cand .

Metoda Newton

Tehnica celei mai abrupt descresteri are inconvenientul ca nu foloseste informatia data de cea de-a doua derivata. Pot fi obtinute metode mai eficiente pe baza proprietatii functiilor patratice, , de a avea matricea Hessian constanta. Fie

(3).

Gradientul este,

.

Punctul stationar rezulta prin rezolvarea sistemului de ecuatii liniare,

(4).

Solutia sistemului (4) este punct de minim daca matricea Hessian, A, este pozitiv definita. Daca A este negativ definita, solutia sistemului (4) este punct de maxim. Daca A este oarecare, solutia lui (4) este punct sea. Daca A este nesingulara, atunci (3) are un unic punct stationar.

Principiile expuse mai sus pot fi aplicate pentru minimizarea unei functii generale, . Fie estimatia punctului de minim al lui F la momentul curent si , . Utilizand dezvoltarea Taylor in jurul lui obtinem,

(5) si

(6)

Rezulta ca, daca este pozitiv definita,

(7)

Este obtinut astfel urmatorul algoritm.

Metoda Newton

Selecteaza , estimare initiale a punctului de minim al lui si

Repeat for

,

If este pozitiv definita, atunci calculeaza

Else

calculeaza astfel incat indeplineste conditiile Wolfe 2 si 3    (Bartholomeu-Biggs, 2005)

aplica regula de actualizare

Until

Exemplul 1 STUDIU DE CAZ

In tabelul 1 este prezentat istoricul randamentelor corespunzatoare actiunilor A1, A2,A3,A4,A5 pe o perioada de 10 saptamani. (Bartholomeu-Biggs, 2005)

Tabelul 1

Problema de rezolvat: determinarea portofoliului de risc minim pentru un randament dat .

Randamentul mediu al portofoliului rezulta,

si matricea de covarianta este,

Problema poate fi modelata in termenii RISCMIN1M,

Minimizeaza .

Prin aplicarea metodelor de tip gradient prezentate, pentru eroarea permisa si , rezulta

portofoliul

riscul minim

randamentul , randamentul dat.

De asemenea, pentru aceeasi eroarea permisa, , testele indica faptul ca numarul de iteratii ale metodei celei mai rapide descresteri este de ordinul sutelor, in timp ce metoda Newton necesita cateva zeci de iteratii.