CATEGORII DOCUMENTE |
Agricultura | Asigurari | Comert | Confectii | Contabilitate | Contracte | Economie |
Transporturi | Turism | Zootehnie |
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)
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
S8 |
S9 |
S10 |
|
A1 | ||||||||||
A2 | ||||||||||
A3 | ||||||||||
A4 | ||||||||||
A5 |
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.
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1596
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2025 . All rights reserved