METODE DE OPTIMIZARE A FUNCTIILOR DE O VARIABILA

METODE DE OPTIMIZARE A FUNCTIILOR DE O VARIABILA

1. Introducere. Conditii de optimalitate

Definitia 1. Fie F o functie continua si diferentiabila in variabila scalara x si, pentru au loc relatiile,

(1) si .

Atunci functia F are ca minim local punctul .

Definitia 2 Fie F o functie continua si diferentiabila in variabila scalara x. Daca relatiile (1) au loc pentru si daca pentru orice x, atunci este punct de minim global al lui F.

Relatiile (1) sunt numite conditii de optimalitate. In problemele de interes practic, determinarea unui minim global este in general foarte dificila; in majoritatea situatiilor este aplicata o procedura de determinare a unui set de puncte minim local.

Abordarea analitica in rezolvarea problemelor de minimizare este utila cand forma F' poate fi calculata usor si, de asemenea, cand problema poate fi rezolvata intr-o maniera relativ simpla. In multe situatii practice, spre exemplu in problema RANDAMENTMAX1M, problema de optim nu poate fi tratata de maniera prezentata mai sus. In general, tehnicile de rezolvare a problemelor de optim sunt iterative si sunt

tehnici de cautare directa, care utilizeaza comparatii ale valorilor functiei de optimizat in puncte de test, sau

metode gradient, care utilizeaza derivatele functiei obiectiv si rezolva iterativ ecuatia neliniara

Metodele de tip gradient au in general o convergenta mai rapida comparativ cu metodele de cautare directa. De asemenea, metodele gradient au avantajul ca permit definirea unui test de convergenta evident, si anume algoritmul este incheiat cand gradientul este apropiat de 0, dar nu pot fi aplicate in orice situatie (de exemplu cand F(x) are derivate discontinue, cum este cazul functiilor liniare pe portiuni).

2. Metoda bisectiei

Metoda bisectiei pentru determinarea minimului lui F(x) pe intervalul este descrisa astfel. (Bartholomeu-Biggs, 2005)

Seteaza ,

Calculeaza

Repeat

,

Calculeaza ,

Calculeaza

If sau , seteaza ,

Else If seteaza ,

Else If sau seteaza ,

Until

Procedura urmatoare este aplicata pentru calculul unui interval care sa contina un punct de minim al functiei F.

Este selectat un punct initial si un pas

Repeat for k=0,1,2,.

Unitl

If k=0,

If k>0,

3. Metoda secantei

Este prezentata in continuare o metoda iterativa pentru rezolvarea . Aceasta metoda permite in continuare calculul unui minim local al lui pentru a fi utilizat intr-o regiune in care este pozitiva. Abordarea are la baza interpolarea liniara. Daca F' este evaluat in punctele , atunci

(2)

este o estimatie a punctului in care F se anuleaza.

In situatia in care F este functie polinomiala de gradul 2 (patratica), relatia (2) este aplicata o singura data pentru calculul exact al punctului in care F' se anuleaza. In caz contrar, formula de interpolare (2) este aplicata iterativ. Algoritmul este descris astfel. (Bartholomeu-Biggs, 2005)

Selecteaza estimari initiale ale minimului functiei F(x) si

Repeat for k=0,1,2,

Unitl

4. Metoda Newton

Metoda determina minimul functiei F(x) prin utilizarea primelor doua derivate ale functiei F. Algoritmul este derivat prin dezvoltarea lui F(x) in serie Taylor in jurul unui punct ,

(3)

Prin derivarea (3) in raport cu h este obtinuta seria Taylor pentru F (x)

Daca presupunem ca valoarea lui h este suficient de mica pentru ca termenul din (4) sa poata fi neglijat, atunci pasul determina .

Algoritmul pentru implementarea metodei Newton este descris astfel. (Bartholomeu-Biggs, 2005)

Selecteaza estimare initiala a minimului functiei F(x) si

Repeat for k=0,1,2,

Unitl

Rezolvarea problemei RANDAMENTMAX1M pentru portofolii cu 2 actiuni prin metodele bisectiei, secantei si Newton

In sectiunea aceasta sectiune vom exemplifica aplicarea metodelor descrise in 2, 3 si 4 pe problema RANDAMENTMAX1M in urmatorul caz particular.

Exemplul 1. STUDIU DE CAZ

In tabelul 1 este prezentat istoricul randamentelor corespunzatoare actiunilor A1 si A2 pe primele 6 luni ale anului.

Tabelul 1

Problema RANDAMENTMAX1M este descrisa prin

Minimizeaza

cu restrictia

In sitatia din tabelul 1, rezulta

Minimizeaza , unde

Pentru stabilirea unei valori acceptabile a riscului, , rezolvam problema primara RISCMIN0, cu obtinerea valorii riscului minim, .

Procedura RISCMIN0 este echivalenta cu,

Minimizeaza

Functia obiectiv este,

Obtinem,

,

si

Deoarece pentru relatiile (1) sunt indeplinite, rezulta ca functia V are un minim local (deoarece V este patratica, este minimul global), . Valoarea acceptabila a riscului poate fi considerata . Vom considera in continuare .

Pentru rezolvarea problemei RANDAMENTMAX1M, functia de minimizat este,

, unde

Consideram in continuare ca parametrul care semnifica relatia randament risc este 1 ().

2

Obtinem,

In continuare prezentam sursa C pentru minimizarea lui F prin metoda bisectiei, insotita de procedura de determinare a intervalului in care se gaseste minimul, asa cum au fost prezentate in sectiunea 2.

#include <stdio.h>

#include<math.h>

float f(float);

void genereaza(float (*)(float),float,float,float *,float *);

float bisectiemin(float,float,float, float (*)(float), float *);

void main()

float f(float x)

void genereaza(float (*f)(float),float x,float alpha,float *a,float *b)

*a=x0;*b=x2;

float bisectiemin(float x0,float x1,float eps, float (* f)(float), float *x2)

float minim=Fa;

for(int i=1;i<5;i++)

if(minim>ff[i])minim=ff[i];

if((minim==Fa)||(minim==Fl))

else if(minim==Fm)

else if((minim==Fr)||(minim==Fb))

if(fabs(xa-xb)<eps)

return (*f)(*x2);

Au fost folosite constantele: (punctul de la care se pleaca in determinarea intervalului, F'(0)<0),, .

Solutia optima obtinuta este , valoarea minima a functiei obiectiv . Interpretarea datelor este urmatoarea.

Randamentul asteptat, in procente, este

Riscul este

Prin utilizarea metodelor secantei si Newton sunt obtinute rezultate similare metodei bisectiei.