curs tehnici de optimizare

Tehnici de optimizare- note de curs -

.l.dr.ing. Florin [email protected]

www.ac.tuiasi.ro/~fostafi

Obiectul optimizrii

| Un sistem optim este sinonim cu cel mai bun posibil n general i din toate punctele de vedere?

| n orice problem de optimizare corect formulat z se are n vedere un anumit criteriu, exprimat printr-un indice de

calitate, funcie cost, funcie obiectiv etc. i z se urmrete realizarea celui mai bun sistem din punctul de

vedere al criteriului adoptat. z Sistemul astfel realizat este optim numai cu referire la criteriul

considerat.

Obiectul optimizrii

| Se pot concepe criterii care s nglobeze simultan mai multe performane ale sistemului, fiecare intervenind cu o anumit pondere

| Exist i probleme de optimizare multicriterialez se iau n considerare simultan mai multe funcii obiectivz i n aceste cazuri, sistemul este optimizat dintr-un anumit punct de

vedere prestabilit

| Un sistem astfel optimizat nu poate fi cel mai bun posibil din punctul de vedere al fiecrei performane pariale n partez dac criteriul ar fi luat n considerare o singur performan, din

punctul de vedere respectiv s-ar fi obinut un sistem mai bun dect n cazul unui criteriu global, care are n vedere mai multe performane.

Obiectul optimizrii

| Criterii de performan (indici de calitate)z cheltuielile totale z consumul de combustibil sau energie z eroarea de funcionare z timpul de rspunsz distana parcurs etc.

| Criteriile de performan se exprim de obicei prin intermediul unor funcii sau funcionale care depind de o serie de variabile de stare, de comand, parametri constructivi ai sistemului etc.

| Optimizarea const n determinarea acelor variabile sau parametri care conduc la extremizarea (maximizarea sau minimizarea) funciei sau funcionalei adoptate drept criteriu, n condiiile considerrii restriciilor la care este supus sistemul.

Obiectul optimizrii

| Un aspect important n formularea unei probleme de optimizare este adoptarea indicelui de calitate.

z n cazul n care exist interes pentru eficiena economic - se adopt un indice care s conduc final la cheltuieli minime de investiii i exploatare

z n cazul sistemelor tehnice - optimizarea consumului de combustibil sau energie / a productivitii / a calitii produciei

z Se pot lua n considerare indici economici, care nglobeaz i indicatori tehnici de tipul celor menionai.

n astfel de cazuri, punerea i rezolvarea teoretic i practic a problemei de optimizare conduce la avantaje incontestabile.

Optimizare staionar / Optimizare dinamic

| Problemele n care intervine minimizarea unei funcii sunt probleme de programare matematic. z n conducerea proceselor tehnologice, aceste probleme se refer la

regimurile staionare de funcionare (deci cnd nu intervine variabila timp) i mai sunt numite probleme de optimizare staionar

| Problemele n care intervine minimizarea unei funcionalese numesc probleme de optimizare dinamic deoarece se aplic sistemelor dinamice, cu o anumit evoluie n timp z Se mai numesc probleme de conducere sau de control optimal

z Din punct de vedere matematic, sunt probleme variaionale

Optimizare staionar / Optimizare dinamic

| n general problemele de optimizare dinamic sunt separate de problemele de optimizare staionar.

| Exist situaii n care problemele de optimizare dinamic sunt subordonate celor de optimizare staionar. z Motivaie: n conducerea unui sistem tehnico-economic sunt

prioritare aspectele decizionale fa de cele executorii.

z Exemplu: este prioritar stabilirea valorilor de regim staionar n funcie de cerinele procesului,

modalitatea de realizare a regimurilor dinamice n diverse subsisteme devine o problem secundar (dei se soluioneaz mai dificil).

Formularea problemelor de optimizare staionar

| Optimizarea staionar presupune extremizarea unei funcii scalare, dependent de una sau mai multe variabile.

| Problemele de extrem pot fi de maxim sau de minim | Vom considera, de regul, probleme de minim, avnd n vedere

faptul c orice problem de maxim poate fi transformat ntr-una de minim prin inversarea semnului funciei

| S se determine

f - funcie obiectiv (funcie cost, cost, criteriu) X - domeniul maxim pe care funcia este definit n mod natural

cu respectarea unor restricii de tip egalitate sau inegalitate de forma

1 2 nmin f ( ) min f (x ,x ,..., x ),=x nX , R f R,X,x

i

j

h (x) 0, i 1,..., l, l ng (x) 0, j 1,...,m

= = =

Exemple de probleme de optimizare staionar

| Probleme de planificare a producieiz Trei tipuri de produse n cantitile x1, x2, x3z Se folosesc resursele b1 i b2z aij - cantitatea din resursa i pentru realizarea produsului j

Cerin: s se planifice producia (x1, x2, x3) astfel nct s se maximizeze ctigul total

ci, i = 1,2,3 reprezint preurile de vnzare ale celor trei produse.

11 1 12 2 13 3 1

21 1 22 2 23 3 2

a x a x a x ba x a x a x b ,

+ + + + 1 2 3x 0, x 0, x 0.

1 1 2 2 3 3f c x c x c x= + +


| Dimensionarea grosimii izolaiei unei instalaii termice

T I OC C C ,= + I i aC A c r ,= O tC Qhc ,=

z CT - cheltuieli totalez CI - cheltuieli de investiiiz CO cheltuieli de operare

(energia termic pierdut)z ra - rata anual de amortizarez A - suprafaa izolaiei z grosimea izolaieiz densitatea materialuluiz ci costul unitii de mas a

materialului izolant

z Q - cldura pierdutz h - este numrul de ore mediu anual de

funcionare a instalaiei z ct - costul unitar al energiei termicez / - temperaturile medii considerate

pentru interiorul / exteriorul instalaieiz - conductivitatea termic a materialului - coeficientul parial de transfer al stratului limit de aer

( )c eAQ ,/ 1/ = +

c e


| Dimensionarea unei reele electricez Se impune minimizarea cheltuielilor de investiii prin

alegerea seciunii Sz Soluia trivial (S ct mai mic) conduce la cderi de tensiune i

pierderi de putere inadmisibile, care trebuie limitate

z ntr-o problem de proiectare se impun valorile medii pentru puterea activ i reactiv a

consumatorului I i cos au valori precizate; lungimea L a tronsonului este precizat; seciunea S a conductorului este necunoscut - se deduce din condiia

de minim pentru CI cu respectarea restriciilor asupra U i P.

( )IC a bS L= +

aLU RIcos Icos U ,S

= = 2 2 aLP RI I PS = =


| Minimizarea pierderilor n regim staionar la motoarele de inducie

z Pierderile variabile de energie n cupru -pierderi Joule

n fier - datorit histerzisului i curenilor turbionari

z Ambele tipuri de pierderi depind de frecvena i amplitudinea tensiunii de alimentare (sau, echivalent, de fluxul din ntrefier).

z Frecvena i amplitudinea tensiunii de alimentare sunt folosite pentru realizarea reglajului de vitez.

z Exist deci posibilitatea ca, prin alegerea convenabil a acestor mrimi de comand, s se asigure viteza de rotaie dorit i un randament maxim.

Formularea problemelor variaionale

| O problem variaional propriu-zis va fi considerat sub forma: s se determine funcia vectorial (avnd derivate de ordinul unu continue) care minimizeaz funcionala

unde L este o funcie scalar suficient de neted (de obicei se impune ca L s aib derivatele de ordinul doi continue n raport cu toate argumentele).

| Vectorul poate s fie precizat sau nu la cele dou capete (la t0 i la tf).

n0 f( ) , t [t , t ] Rx t

f

0

t

tI L( (t), (t), t)dt= x x

(t)x

Formularea problemelor de conducere optimal

| Indicele de performan:

| Problemele de control optimal sunt ntotdeauna probleme variaionale cu legturi - ecuaia sistemului:

| Pot s apar restricii suplimentare privitoare la variabilele de stare sau de comand.

| Se cere determinarea comenzii optimale u(t) care transfer sistemul din condiiile iniiale specificate n anumite condiii finale specificate, cu respectarea restriciilor impuse variabilelor de stare i de comand astfel nct s fie extremizat un indice de calitate.

f

0

t

0 f 0 ft

I M( (t ), (t ), t , t ) L( (t), (t), t)dt= + x x x u

(t) = ( (t), (t), t)(t) = g( (t), (t), t)x f x uy x u

Exemple de probleme variaionale propriu-zise

| Problema celei mai scurte curbe plane

z Se impune determinarea unei curbe de lungime minim care unete dou puncte din plan A(x0, y0), B(x1, y1).

z Trebuie minimizat integrala care exprim lungimea unei curbe plane

z Soluionarea problemei va conduce la ecuaia unei drepte y(x) pentru care se va impune condiia s treac prin punctele A i B.

1

0

x2

xI = 1 (dy / dx) dx+


| Problema izoperimetric presupune determinarea unei curbe simple nchise din plan, de lungime dat, care delimiteaz o arie maxim

z S se maximizeze

cu condiia izoperimetric

i condiiile de capt

z Soluia acestei probleme este un arc de cerc care trece prin punctele de capt

1

0

x

xA y(x)dx=

1

0

x2

x1 (dy / dx) dx+ = A

0 0 1 1y(x ) y , y(x ) y= =


| Problema brahistocroneiz S se uneasc printr-o curb y(x) punctele A(x0, y0) i B(x1, y1)

situate ntr-un plan vertical xOy, dar nu pe aceeai vertical (x0x1, y0>y1) a.. un punct material s se deplaseze n timp minim din A n B prin alunecare n lungul acestei curbe, sub aciunea forei de gravitaie (pentru simplificare, se poate neglija frecarea).

z Reformulare: s se determine curba y(x) care satisface condiiile terminale y(x0) = y0, y(x1) = y1, astfel nct s se minimizeze

1 1

0 0

s x 2

s x

ds 1 1 (dy / dx)T dx.v 2g y

+= = 2 2

0 0v v 2g(y y ), = 2

0 02g 2gy v =

1

0

x 2

x

1 (dy / dx)I dxy

+=

Exemple de probleme de control optimal

| Problem de timp minim pentru un sistem de acionare

z Ecuaia de micare (pentru cuplu rezistent nul):

z Comanda este restricionat:

z Variabile de stare i comand:

z Ecuaia sistemului se rescrie:

z Restricia asupra comenzii devine

z Problema se enun astfel: s se determine comanda u(t) care transfer sistemul (3) din starea iniial x(t0) = x(0) = x0 n starea final x(t1) = 0, cu respectarea restriciei (4), n timp minim.

z Soluie: timpul de frnare este minim dac se adopt u(t)=-sgnx(t), adic cuplul de frnare este maxim posibil cnd i se anuleaz pentru

J (t) m(t) =max maxm m(t) m

max maxJ / m x, m / m u = =0 0 maxx(t) u(t), x(0) x J / m= = =

u(t) 1(3)

(1)

(2)

(4)

0 0.=


| Problem de timp minim pentru un sistem de poziionare

z Ecuaia sistemului:

z Restricie:

z Se introduc variabilele de stare i comand sub forma

z Sistemul de ecuaii de stare se scrie

z Restricia asupra comenzii devine

z S se determine comanda optimal u(t), t[t0,tf], care transfer n timp minim sistemul (4) din condiiile iniiale n condiiile finale , cu respectarea (5).

z Soluie: deplasarea trebuie s se fac cu o acceleraie maxim, urmat de o deceleraie maxim (u=-sgn x2(t)). Calculele urmeaz s stabileasc momentul comutrii valorii comenzii u(t).

(3)

(1)

(2)

(4)

mx(t) f (t)=maxf (t) f

f1 max maxx (t) m(x(t) x ) / f , u(t) f (t) / f= =

1 2 2x (t) x (t), x (t) u(t)= = u(t) 1 (5)

0 01 0 1 2 0 2x (t ) x , x (t ) x= =

f f1 f 1 2 f 2x (t ) x , x (t ) x 0= = =


| Conducerea optimal a unui sistem electric de poziionare

z Ecuaia de micare:

z Mrimi normalizate:

z Ecuaia de regim staionar ptr. valorile nominale:

z Ecuaia normalizat a sistemului:

z Unghiul de rotaie normalizat pe intervalul [0, T]:

z Energia disipat normalizat pe intervalul [0, T]:

md (t)k I(t) J M(t)

dt = +

N N N

N N N N N

i I / N , / , / ,m M / M , t / T , unde T J / M= = = = = =

(1)

(2)

N m N NM k I= (3)i d ( ) / d m= +

T

T0

( )d = T

2T

0w i ( )d=

(4)

(5)

(6)


| Se pot formula urmtoarele probleme de control optimal:z problem de consum minim de energie: s se determine comanda i(T) i

starea (T) care determin o deplasare unghiular impus T ntr-un timp precizat T, astfel nct s se asigure minimul energiei disipate, pentru (0) i (T) fixai, adic s se minimizeze funcionala (6) pentru o valoare impus a funcionalei (5) (condiie izoperimetric);

z problem de timp minim: s se determine i(T) i (T) care minimizeaz durata T a transferului din starea iniial (0) n starea final (T) dat, pentru T i wT impui;

indicele de calitate se poate exprima sub forma iar minimizarea acestuia

se realizeaz cu respectarea condiiilor izoperimetrice (5) i (6);

z problem de eficien (stare final) maxim: s se determine i(T) i (T), astfel nct s se realizeze o deplasare unghiular T maxim, pentru T, (0) i (T) precizai i wT impus; cu alte cuvinte, se cere extremizarea funcionalei (5) cu condiia izoperimetric (6).

T

0T d=

OPTIMIZAREA STAIONAR

1. ASPECTE GENERALE PRIVIND OPTIMIZAREA STAIONAR

1.1. Formularea i clasificarea problemelor de optimizare staionarz O problem de optimizare staionar este o problem de

programare matematic:

{ }miglihf ii ,...,1,0)(;,...,1,0)()(min === xxxRR nf : funcia obiectiv

lih ni ,...,1,: =RR restricii de tip egalitate (legturi)mig ni ,...,1,: =RR restricii de tip inegalitate

1.1. Formularea i clasificarea problemelor de optimizare staionar

Clasificri

| problem fr restricii - extrem liber| problema cu restricii extrem legat

| problem de programare liniar| problem de programare neliniar

z programarea convex z programarea ptratic z programarea geometric


Definiii| Un punct x* se numete minim global pentru f dac

pentru toate punctele admisibile x (adic pentru toate punctele ce satisfac restriciile problemei).

| Dac pentru orice x x* are loc inegalitatea strict, minimul este unic.

| Dac inegalitatea are loc pentru toi x dintr-o vecintate admisibil a lui x*, atunci x* se numete minim local.

Observaii| Orice minim global este i minim local, dar reciproca nu este

ntotdeauna adevrat| Extremele unei funcii pot fi netede sau unghiulare. | Extremele se pot afla ntr-un punct din interiorul domeniului admisibil,

pe frontiera domeniului, sau intr-un punct de discontinuitate.

( *) ( )f fx x

1.2. Chestiuni preliminare

Reprezentarea graficz funcii de o singur variabil - analiz matematicz funcii de dou sau mai multe variabile - reprezentrile grafice se

complic - sunt rareori folosite n problemele de extremz pentru funcii de dou variabile - reprezentri bazate pe curbe de

nivel (curbe de contur sau de valoare constant a funciei)

x2

x1

f(x)=c1

f(x)=c2


Funcii obiectiv ptratice f(x): RnR ,Q = QT - matrice simetric, bRn, - scalar

| importana n studiul problemelor de extrem:z se ntlnesc frecvent n practic, mai ales n probleme cu restricii,

cnd ns rezolvarea este considerabil mai dificil;z foarte multe funcii se aproximeaz destul de bine cu funcii

ptratice, prin dezvoltare n serie Taylor i diverse metode apeleaz la o succesiune de aproximri cu astfel de funcii;

z exist o serie de proprieti ale unor algoritmi care au fost demonstrate numai pentru funcii ptratice, ele fiind "extinse" i la funcii mai generale, n baza a numeroase testri, care le-au validat;

z funciile ptratice sunt folosite ca un prim test pentru diverse proceduri de optimizare.

++= xbQxxx TTf21)(


Aproximarea funciilor| aproximarea pe baza dezvoltrii n serie Taylor

z f(x):RnR este de dou ori derivabil n raport cu toate argumentele ntr-o vecintate a punctului x0

z e(x,x0)0 pentru xx0

z dac derivatele de ordinul 2 sunt continue, H este simetric

20 0 T 0 0 T 0 0 0 01f( ) f( ) ( ) f( ) ( ) ( )( ) e( , )2

= + + + x x x x x x x H x x x x x x x

1

n

f xf ( )f ( ) ;

f x

= = #xx

x

2 2

21 n12

22 2

2n 1 n

f fx xx

f ( )( )

f fx x x

= =

xH xx

""

" "" "

""


Aproximarea funciilor0 0 T 0 0 T 0 0 0 0 21f ( ) f ( ) ( ) f ( ) ( ) ( )( ) e( ) || ||

2= + + + x x x x x x x H x x x x x x x

0 2, cu , || || 1 = =nx x h h R hz notm h vector de lungime unitar care indic direcia de deplasare - lungimea pasului pe direcia h

z Aproximarea Taylor de ordinul 2

z Aproximarea Taylor de ordinul 1

20 2f ( ) f ( ) f ( ) ( ) e( , )

2+ = + + + x h x h x h H x h x h, ,

f ( ) f ( ) f ( ) o( ),+ = + + x h x h x, 0

o( )lim 0 =


Criterii de evaluare a calitii algoritmilor

| Convergenaz exist algoritmi care au o eficien ridicat, dar nu au asigurat

convergena n condiii suficient de largiz pentru a preveni rezultate eronate:

stabilirea unui numr limit de iteraii; introducerea unor testri periodice, care asigur continuarea corect a

programului; combinarea procedurilor respective cu altele care au convergena

garantat, dar i o eficien mai sczut.


Criterii de evaluare a calitii algoritmilor| Viteza de convergen

z ofer informaii asupra numrului de iteraii necesarz ordinul de convergen - apreciaz cantitativ viteza de convergen

dac f(x*) = 0:

dac f(x*) 0:z = 1 convergena liniar f(xk+1)af(xk), a0 scderea

valorii funciei se face n progresie geometricz = 2 convergen ptratic f(xk+1)[f(xk)]2, la fiecare

iteraie se dubleaz numrul de zerouri dup virgulz 1< < 2 convergena supraliniar

k

k 1k

ln f (x )limln f (x )+

=k *

k 1 *k

ln[f (x ) f (x )]limln[f (x ) f (x )]+

=


Criterii de evaluare a calitii algoritmilor| Volumul total de calcule

z unul din criteriile cele mai importante privind eficiena

z poate fi apreciat prin

numrul total de operaii

timpul total de rulare pe calculator

z acest criteriu nu este decisiv n aprecierea unei metode

volumul total de calcule depinde de

calitatea programului ntocmit

tipul calculatorului utilizat

operaiile pregtitoare care se efectueaz .a.


Criterii de evaluare a calitii algoritmilor| Generalitatea metodei

z se refer la posibilitatea aplicrii acesteia pentru categorii ct mai largi de probleme

z n multe cazuri sunt preferai algoritmi specifici unor clase de probleme

sunt mai eficieni dect procedurile cu mare generalitate

z De regul generalitatea este apreciat drept o calitate important a procedurilor


| Criterii de evaluare specifice metodelor numerice de calculz uurina n utilizare i simplitatea;z sigurana n funcionare;z precizia;z stabilitatea numeric

algoritmul nu induce o cretere a sensibilitii problemelor la perturbaii de date;

un algoritm instabil poate da rezultate eronate chiar i pentru probleme bine condiionate;

z fiabilitatea robusteea - evitarea excepiilor aritmetice i minimizarea erorilor de

rotunjire; invariana la scalare; alegerea corespunztoare a criteriului de terminare (stop);

z portabilitatea - posibilitatea utilizrii pe diferite echipamente de calcul, fr nici o modificare.

2. METODE DE REZOLVARE A PROBLEMELOR DE OPTIMIZARE STAIONAR FR RESTRICII

| Funcia scalar f(x) este definit pe ntreg spaiul Rn (sau pe un domeniu maxim din Rn pe care este definit funcia n mod natural)

| Se cere determinarea punctului de minim global x*, adic a punctului pentru care

| Diverse metode impun ca funcia s ndeplineasc anumite condiii z continuitate z derivabilitatez convexitate

f ( *) f ( ), nx x x R

2. METODE DE REZOLVARE A PROBLEMELOR DE OPTIMIZARE STAIONAR FR RESTRICII

| Clasificare din punct de vedere al valorilor calculatez metode directe - se calculeaz doar valorile funciei obiectivz metode indirecte se folosesc i derivate ale funciei

| Clasificare din punct de vedere al principiului folositz metode de explorarez metode de eliminarez metode analitice

metode generale ce stau la baza majoritii procedurilor de cutare sunt mai rar folosite n calculul numeric

z metode de cutare

proceduri iterative - se pornete de la o iniializare oarecare x0 i se

stabilete un ir de iteraii {xk}, astfel ca adic

- greoaie n cazul funciilor de mai multe variabile - se folosesc, de regul, pentru stabilirea grosier a domeniului n care se afl minimul

}

*lim xx =k

k)(...)(...)()()( *210 xxxxx fffff k >>>>>>

2.1. Metode de explorare i de eliminare

| Pentru un numr de variabile 3 proceduri greoaie| Se utilizeaz frecvent n cazul extremizrilor

unidimensionale| Precizia este destul de redus n cazul utilizrii unui

numr rezonabil de iteraii| Sunt folosite pentru stabilirea iniial a domeniului n

care se afl extremul z Determinarea mai precis a extremului se face prin alte

proceduri| Se pleac de la un anumit domeniu pe care este

definit funcia. z Probleme fr restricii - rezolvarea pornete cu stabilirea

domeniului respectiv (ntr-un anumit mod) z Probleme cu restricii - se pornete de la domeniul definit de

restricii.

2.1.1. Metode de explorare

| n interiorul domeniului iniial se stabilesc puncte n care se calculeaz valoarea funciei obiectiv

| Se alege punctul n care funcia are valoarea cea mai micz astfel se stabilete un subdomeniu n jurul acestui punct, n

interiorul cruia se afl minimul funciei.

| Acest subdomeniu alctuiete domeniul de incertitudine n care se afl minimul.

| Avantaj: n majoritatea cazurilor se evit punctele de minim local

| Clasificarez explorare exhaustiv z explorare aleatoare


Metode de explorare exhaustiv| Principiu

z domeniul considerat se mparte pe fiecare ax ntr-un numr de subintervale o reea multidimensional (rectangular)

nu este obligatoriu s se adopte acelai pas de divizare pe direcia fiecrei axe

z se calculeaz f(x) n nodurile reelei i se selecteaz cel pentru care s-a obinut cea mai mic valoare pentru f(x)

z domeniul de incertitudine n care se afl minimul este fixat de nodurile vecine celui selectat.

| Dezavantajul principal z numrul mare de evaluri necesar pentru a obine o precizie

acceptabil, numrul de evaluri crete cu creterea numrului de variabile


Metode de explorare exhaustiv| Algoritm pentru funcii unidimensionale

z se stabilete un punct iniial x0, se adopt un pas i se calculeaz f(x0)

z se calculeaz f(x0+) i f(x0), stabilind sensul deplasriiz se calculeaz f(x0+k), kZ

dac f[x0+(k1)] > f(x0+k), se repet aceast etap pentru k modificat cu o unitate

dac f[x0+(k1)] < f(x0+k), a fost depit punctul de minim i se consider c noul interval de incertitudine este

[x0+(k2), x0+k]z pentru diminuarea acestui interval, se prefer aplicarea unor

metode mai precise


Metode de explorare aleatoare| Principiu

z testarea funciei obiectiv se face n mai multe puncte, stabilite pe baz de numere aleatoare se obine o zon n care, cu o mare probabilitate, se afl minimul funciei

| Avantaje z volumul de calcule este dependent doar n mic msur de ordinul

sistemului z pot fi folosite i n cazul problemelor cu variabile discrete

| Domeniu de aplicarez rezolvarea unor probleme specifice de mari dimensiuni - mai ales

din domeniul economicz sunt utilizate adeseori pentru stabilirea iniial a domeniului sau a

punctului de start

2.1.2. Metode de eliminare

| Funcia obiectiv trebuie s satisfac ipoteza de unimodalitatez unimodalitate - pe domeniul de definiie exist un singur punct de extrem

| Principiuz domeniul considerat se mparte n dou pri printr-un plan (dreapt) de

separare z se testeaz valoarea funciei n cele dou subdomenii printr-o procedur

specific i se elimin acela care nu prezint interesz pentru domeniul rmas se continu procedura, prin mprirea cu un plan

de separare etc., pn se ajunge la un domeniu suficient de mic, funcie de precizia impus

| Exist diverse variante n ceea ce privete modul de mprire n subdomenii i al celui de efectuare a testrii

| Metodele de eliminare multidimensionale sunt mai rar folosite datorit eficienei sczute.

| n cazul extremizrilor unidimensionale, metodele de eliminare sunt eficiente

2.2. Metode analitice

| Sunt metodele cele mai puternice i care stau la baza unui mare numr de metode de cutare

| Dac se dispune de expresiile analitice ale derivatelor funciei obiectiv n raport cu toate variabilele, problema se reduce la rezolvarea unui sistem de ecuaii

| Transpunerea metodelor analitice n proceduri numerice este mai rar folosit, fiind preferai algoritmii de cutarez algoritmii de cutare sunt mai direct adaptai problemelor de

optimizare staionar, chiar i n cazurile n care se dispune de expresiile analitice ale derivatelor

2.2.1. Proprieti ale gradientului

a. n orice punct al suprafeei f(x) = const., vectorul gradient este ortogonal la aceast suprafa

DemonstraieTn

ii 1 if ( ),df fdf ( ) dx d

=

= = x xx x =x x

const. df ( ) f ( ) 0= =x x} f ( ),d 0=x x


b. Aproximarea Taylor de ordinul 1

z Presupunem c exist

f ( ) f ( ) f ( ) o( ),+ = + + x h x h x, 0

o( )lim 0 =

f ( ) f ( ) o( )f ( ),+ = + x h x x h

0

f ( ) f ( ) flim+ = x h x

0

o( )lim 0 =

f f ( ), = x h


c. Inegalitatea Cauchy-Schwarz , x,yRnz egalitatea se obine dac x i y au aceeai direcie

dac i

egalitatea se obine atunci cnd vectorii i h au aceeai direcie| ntr-o vecintate a punctului x, creterea maxim a funciei

f(x) are loc pe direcia gradientului, respectiv scderea cea mai rapid se face pe direcia invers gradientului

yyxxyx ,,, 2 =

2f ( ), , f ( ), f ( )x h h h x x 1, =hh f ( ) f ( ) o( )f ( ),+ = +

x h x x h

1/2f ( ) f ( ) o( )f ( ), f ( )+ + x x x xh

f ( )x


d. Fie x* un punct precizat i h o direcie oarecare fixat f(x*+h) se modific doar n funcie de parametrul scalar .

Punctele n care se anuleaz gradientul se numesc staionare (critice)

Condiia necesar ca un punct x* s fie extrem (maxim sau minim) este ca acest punct s fie staionar.

df ( * ) 0d+ =

x h

f f ( ), = x h} f ( * ), 0+ =x h h

h este oarecare} f ( *) 0=x


e. Presupunem aleas o direcie h astfel nct

Dac deplasarea din x se face pe o direcie h care face un unghi mai mare de 90o cu direcia gradientului atunci, ntr-o vecintate a punctului x, se va obine o descretere a valorii funciei f(x)

n cadrul problemelor de minim, direciile de deplasare h care ndeplinesc condiia se numesc admisibile

} f ( ), 0


| n orice punct al suprafeei f(x) = const., vectorul gradient este ortogonal la aceast suprafa

| ntr-o vecintate a punctului x, creterea maxim a funciei f(x) are loc pe direcia gradientului, respectiv scderea cea mai rapid se face pe direcia invers gradientului

| Condiia necesar ca un punct x* s fie extrem (maxim sau minim) este ca acest punct s fie staionar

| Dac deplasarea din x se face pe o direcie h care face un unghi mai mare de 90o cu direcia gradientului atunci, ntr-o vecintate a punctului x, se va obine o descretere a valorii funciei f(x)

2.2.2. Condiii necesare i suficiente de extrem liber

Condiii necesare

| Fie f(x):RnR continuu derivabil n raport cu toate argumentele. Condiia de minim local este condiia de punct critic (staionar):

z generalizeaz condiia cunoscut (anularea derivatei) din cazul funciilor de o singur variabil

f ( *) =x 0


Condiii suficiente| Fie f(x):RnR, avnd derivatele de ordin doi continue; condiia

suficient ca x* s fie punct de minim local este ca n acest punct s fie ndeplinit condiia f(x*)=0 i matricea hessian s fie pozitiv definit (H(x*)>0).

| Fie f(x):RnR, continuu derivabil i convex. Atunci relaia f(x*)=0este condiie de minim global.

* * T * * T * * * * 21f( ) f( ) ( ) f( ) ( ) ( )( ) e( ) || ||2

= + + + x x x x x x x H x x x x x x x*( ) 0>H x * T * *( ) ( )( ) 0 >x x H x x x

*f( ) 0=x

*f( ) f( ) 0 >x x - x* este punct de minim local tare


| Dac este ndeplinit condiia f(x*)=0 i H(x*) < 0, atunci x* este punct de maxim local tare.

| Dac n punctul staionar H(x*) este de semn nedefinit, atunci x* este punct ea (prezint maxim n raport cu anumite variabile i minim n raport cu altele), numai dac detH(x*) 0.

| Dac n x* matricea H(x*) este semidefinit ca semn (H(x*) 0 sau H(x*)0), nu se pot face aprecieri asupra naturii punctului critic pe aceast cale.

2. METODE DE REZOLVARE A PROBLEMELOR DE

OPTIMIZARE STAIONAR FR RESTRICII

2.2. Metode analitice

Sunt metodele cele mai puternice i care stau la baza unui mare numr de metode de cutare

Dac se dispune de expresiile analitice ale derivatelor funciei obiectiv n raport cu toate variabilele, problema se reduce la rezolvarea unui sistem de ecuaii

Transpunerea metodelor analitice n proceduri numerice este mai rar folosit, fiind preferai algoritmii de cutare algoritmii de cutare sunt mai direct adaptai problemelor de

optimizare staionar, chiar i n cazurile n care se dispune de expresiile analitice ale derivatelor

2.2.1. Proprieti ale gradientuluia. n orice punct al suprafeei f(x) = const., vectorul gradient

este ortogonal la aceast suprafa

DemonstraieT

n

ii 1 if ( ),df fdf ( ) dx d

=

= = x xx x =x x

const. df ( ) f ( ) 0= =x x} f ( ),d 0=x x

2.2.1. Proprieti ale gradientuluib. Aproximarea Taylor de ordinul 1

Presupunem c exist

f ( ) f ( ) f ( ) o( ),+ = + + x h x h x, , , , 0

o( )lim 0

=

f ( ) f ( ) o( )f ( ),+ = +

x h xx h

0

f ( ) f ( ) flim

+ =

x h x

0

o( )lim 0

=

f f ( ), =

x h

2.2.1. Proprieti ale gradientuluic. Inegalitatea Cauchy-Schwarz , x,yRn

egalitatea se obine dac x i y au aceeai direcie

dac i

egalitatea se obine atunci cnd vectorii i h au aceeai direcie ntr-o vecintate a punctului x, creterea maxim a funciei

f(x) are loc pe direcia gradientului, respectiv scderea cea mai rapid se face pe direcia invers gradientului

yyxxyx ,,, 2 =

2f ( ), , f ( ), f ( )x h h h x x 1, =hh f ( ) f ( ) o( )f ( ),+ = +

x h x

x h

1/2f ( ) f ( ) o( )f ( ), f ( )+ +

x xx x

h

f ( )x

2.2.1. Proprieti ale gradientuluid. Fie x* un punct precizat i h o direcie oarecare fixat f(x*+h) se

modific doar n funcie de parametrul scalar .

Punctele n care se anuleaz gradientul se numesc staionare (critice)

Condiia necesar ca un punct x* s fie extrem (maxim sau minim) este ca acest punct s fie staionar.

df ( * ) 0d

+=

x h

f f ( ), =

x h } f ( * ), 0+ =x h hh este oarecare

} f ( *) 0=x

2.2.1. Proprieti ale gradientuluie. Presupunem aleas o direcie h astfel nct


n cadrul problemelor de minim, direciile de deplasare h care ndeplinesc condiia se numesc admisibile

} f ( ), 0


n orice punct al suprafeei f(x) = const., vectorul gradient este ortogonal la aceast suprafa

ntr-o vecintate a punctului x, creterea maxim a funciei f(x) are loc pe direcia gradientului, respectiv scderea cea mai rapid se face pe direcia invers gradientului

Condiia necesar ca un punct x* s fie extrem (maxim sau minim) este ca acest punct s fie staionar



Condiii necesare

Fie f(x):RnR continuu derivabil n raport cu toate argumentele. Condiia de minim local este condiia de punct critic (staionar):

generalizeaz condiia cunoscut (anularea derivatei) din cazul funciilor de o singur variabil

f ( *) =x 0


Condiii suficiente Fie f(x):RnR, avnd derivatele de ordin doi continue; condiia

suficient ca x* s fie punct de minim local este ca n acest punct s fie ndeplinit condiia f(x*)=0 i matricea hessian s fie pozitiv definit (H(x*)>0).

Fie f(x):RnR, continuu derivabil i convex. Atunci relaia f(x*)=0este condiie de minim global.

* * T * * T * * * * 21f( ) f( ) ( ) f( ) ( ) ( )( ) e( ) || ||2

= + + + x x x x x x x H x x x x x x x

*( ) 0>H x * T * *( ) ( )( ) 0 >x x H x x x

*f( ) 0=x }

*f( ) f( ) 0 >x x - x* este punct de minim local tare


Dac este ndeplinit condiia f(x*)=0 i H(x*) < 0, atunci x* este punct de maxim local tare.

Dac n punctul staionar H(x*) este de semn nedefinit, atunci x* este punct ea (prezint maxim n raport cu anumite variabile i minim n raport cu altele), numai dac det H(x*) 0.

Dac n x* matricea H(x*) este semidefinit (H(x*) 0 sau H(x*) 0), nu se pot face aprecieri asupra naturii punctului critic.

2.3. Metode de cutare2.3.1. Aspecte generale privitoare la metodele de cutare

Prezentare general Cele mai eficiente i folosite metode de rezolvare a problemelor de

extremizare fr restricii n cazul problemelor de minim - metode de coborre

Se pornete de la un punct iniial oarecare x0 care poate fi ales la ntmplare n domeniul de definiie al funciei, ntr-un domeniu n care se bnuiete c se afl minimul ntr-un domeniu stabilit printr-o procedur oarecare (ex. explorare)i se stabilesc iterativ aproximaii din ce n ce mai bune ale minimului x*, procedura ncheindu-se cnd este ndeplinit un criteriu de stop (de convergen).

2.3.1. Aspecte generale privitoare la metodele de cutare

Formula de calcul

Metodele difer ntre ele prin modul n care se face alegerea direciei de deplasare pasului de deplasare

La majoritatea metodelor, la fiecare iteraie se stabilete mai nti direcia de deplasare i apoi lungimea pasului pe direcia respectiv

kk

kk hxx +=+1


Alegerea direciei de deplasare Clasificare

metode de ordinul I (directe): se calculeaz numai valorile funciei obiectiv

metode de ordinul II: se calculeaz i derivatele de ordinul unu metode de ordinul al III-lea: se calculeaz i derivatele de ordinul al

doilea Utilizarea derivatelor

Avantaj: vitez de convergen crescut Dezavantaj: efort de calcul suplimentar

Calculul derivatelor Dac derivatele pot fi exprimate analitic fr un efort prea mare, se

specific expresiile analitice ale derivatelor Dac nu dispunem de expresiile analitice ale derivatelor, acestea

trebuie evaluate numeric creterea timpului de calcul introducerea de erori suplimentare


Alegerea lungimii pasului la fiecare iteraie pas constant pas variabil

de regul este din ce n ce mai mic, pe msur ce ne apropiem de punctul staionar

pas optim deplasarea pe direcia respectiv se face pn cnd se atinge

minimul pe aceast direcie determinarea pasului optim crete volumul de calcule la fiecare

iteraie exist metode care impun utilizarea pasului optim la fiecare

iteraie determinarea pasului optim pe o anumit direcie se mai

numete cutare liniar exact determinarea pasului optim const n a stabili k kmin f ( )

+ x h


Interpretarea geometric a pasului optim

hk f(x)=c1 f(x)=c2

xk

xk+1


Calcularea pasului optim

Minimizez

valoare aproximativ a pasului optim pentru cutarea liniar exact se folosesc proceduri mai precise -

metode de eliminare i de interpolare n cazul funciilor ptratice formula este exact

2k 1 k k k k k

kf ( ) f ( ) f ( ), ,2+

= + +x x x h h H h

))(( 1 +kf x

0))((1

=

+

ddf kx k k k k

kf ( ), , 0+ =x h h H hk k

k k k

f ( ),*

, ( ) =

x h

h H x h


Convergena procedurilor de cutare Teorem

Fie un ir de iteraii de forma n care direciile hk sunt admisibile ( ). Dac n punctele xk ale irului gradientul este continuu i Hk > 0, atunci este posibil s alegem paii de deplasare k la fiecare iteraie astfel nct s obinem convergena irului xk ctre punctul staionar x*.

Observaii Dac H(x*)>0, atunci x* este punct de minim. Conform proprietii anterioare, convergena este legat de semnul

matricei Hessian, putnd fi asigurat atunci cnd aceasta este pozitiv definit n punctele irului de iteraii.

k 1 k kk

+= + x x h

f ( ), 0


Criterii de stop n cadrul metodelor iterative de cutare trebuie introdus un

criteriu se stop (de oprire a calculelor sau de convergen) Alegerea criteriului de stop este funcie de particularitile

problemei i este dictat de o serie de consideraii: dac exist dubii privind convergena procedurii iterative, se

recomand limitarea numrului de iteraii, n afara introducerii criteriului de stop propriu-zis;

la metodele care apeleaz la calcularea gradientului f(x) al funciei obiectiv, pentru problemele fr restricii se poate folosi:

kf ( ) x


Criterii de stop criterii absolute de stop bazate pe variaia argumentului sau a

funciei:

n locul criteriilor absolute sunt preferate criteriile relative:

dac ||x*|| sau f(x*) sunt foarte apropiate de zero, atunci criteriile relative nu sunt utilizabile i se folosesc:

sau

k k 1

k

x x

x

k k 1

kf ( ) f ( )

f ( )

x xx

k k 1

k1

+

x x

x

k k 1

k

f ( ) f ( )1 f ( )

+

x x

xsau

k k 1 x x sau k k 1f ( ) f ( ) x x


Criterii de stop folosirea exclusiv a unui criteriu bazat pe variaia argumentului sau

a funciei poate conduce la rezultate eronate

aceste situaii pot fi prentmpinate prin utilizarea combinat, n cadrul aceluiai program, a ambelor criterii

f

f(x)

x

x

(a) (b) x

f(x) f

x

2.3.2. Proceduri de determinare a lungimii pasului

Utilizarea pailor constani are multe dezavantaje de regul nu este folosit exist proceduri la care nu apare n mod explicit (altfel zis, =1),

distana pe care se face deplasarea fiind dictat de lungimea vectorului h

Utilizarea pasului optim (cutare liniar exact) pare a fi cea mai atrgtoare numr mare de evaluri ale funciilor obiectiv se prefer

procedurile de cutare liniar aproximativ (mai economice) exist metode de cutare care impun cutri liniare exacte la

fiecare iteraie, pentru a preveni euarea algoritmului

2.3.2.1. Proceduri de extremizare unidimensional

Metode de eliminare unidimensional trebuie determinat minimul funciei unimodale f(x) pe [xm,xM]

xm x1 x2 xM

xm x1 x2 xM

xm x1 x2 xM

Eficiena metodei se poate aprecia prin indicele:

Este de dorit ca procedura s se desfoare astfel nct s se minimizeze k i atunci se ia

mMkkk

kxx

xxR

=

=

12

0

)(max 21

= jj

kjkxx

=

mM

jj

kjkxxk

xx

xxR2

1,...,

1maxmin

Metode de eliminare unidimensional

Procedura perechilor secveniale

Se recomand ca la fiecare iteraie s se aleag o distan = x2 x1 destul de mic unul din puncte s fie mijlocul intervalului

k - numrul de evaluri ale funciei f(x) (cte dou evaluri la fiecare iteraie)

k k/21R

2=


Procedura bazat pe calculul derivatei

Se alege un singur punct n centrul intervalului

i se calculeaz , eliminndu-se acea jumtate a intervalului la capetele cruia derivata are acelai semn.

, k - numrul de iteraii (de evaluri ale derivatei)

M m0 x xx

2+

=

0x x

dfdx

=

kkR 21

=


Creterea eficienei metodelor de eliminare unidimensional micorarea numrului de evaluri ale funciei pentru obinerea aceleiai precizii la fiecare nou iteraie se folosete unul din punctele x1 sau x2 de la

iteraia precedent; n felul acesta, la fiecare iteraie (cu excepia primeia) se face o singur evaluare a funciei

alegerea punctelor x1 i x2 trebuie s se fac dup o regul care s conduc la o scdere ct mai rapid a intervalului de incertitudine

Acestor deziderate le corespund metoda Fibonacci metoda seciunii de aur

2. METODE DE REZOLVARE APROBLEMELOR DE

OPTIMIZARE STAIONAR FR RESTRICII

2.3 Metode de cutare


2.3.2. Proceduri de determinare a lungimii pasului

Utilizarea pailor constani are multe dezavantaje de regul nu este folosit exist proceduri la care nu apare n mod explicit (altfel zis, =1),

distana pe care se face deplasarea fiind dictat de lungimea vectorului h

Utilizarea pasului optim (cutare liniar exact) pare a fi cea mai atrgtoare numr mare de evaluri ale funciilor obiectiv se prefer

procedurile de cutare liniar aproximativ (mai economice) exist metode de cutare care impun cutri liniare exacte la

fiecare iteraie, pentru a preveni euarea algoritmului


Metode de eliminare unidimensional trebuie determinat minimul funciei unimodale f(x) pe [xm,xM]

xm x1 x2 xM

xm x1 x2 xM

xm x1 x2 xM

Eficiena metodei se poate aprecia prin indicele:

Este de dorit ca procedura s se desfoare astfel nct s se minimizeze k i atunci se ia

mMkkk

kxx

xxR

=

=

12

0

)(max 21

= jj

kjkxx

=

mM

jj

kjkxxk

xx

xxR2

1,...,

1maxmin


Procedura perechilor secveniale

Se recomand ca la fiecare iteraie s se aleag o distan = x2 x1 destul de mic unul din puncte s fie mijlocul intervalului

k - numrul de evaluri ale funciei f(x) (cte dou evaluri la fiecare iteraie)

k k/21R

2=


Procedura bazat pe calculul derivatei

Se alege un singur punct n centrul intervalului

i se calculeaz , eliminndu-se acea jumtate a intervalului la capetele cruia derivata are acelai semn.

, k - numrul de iteraii (de evaluri ale derivatei)

M m0 x xx

2+

=

0x x

dfdx

=

kkR 21

=


Creterea eficienei metodelor de eliminare unidimensional micorarea numrului de evaluri ale funciei pentru obinerea aceleiai precizii la fiecare nou iteraie se folosete unul din punctele x1 sau x2 de la

iteraia precedent; n felul acesta, la fiecare iteraie (cu excepia primeia) se face o singur evaluare a funciei

alegerea punctelor x1 i x2 trebuie s se fac dup o regul care s conduc la o scdere ct mai rapid a intervalului de incertitudine

Acestor deziderate le corespund metoda Fibonacci metoda seciunii de aur


Metoda Fibonacci

j j j j-1

xm

xM x

1j x2j

j+1 j

xm

xM x

1j+1 x2j+1

j+1 j+1

j+1

xm

xM

j j 1 j = j j j 1+ = +

Notmj

jj 1

=

j 1

jj 1

12

+

+

=

,

Pentru ca procedura s fie de tip min-max, trebuie ca la ultimele evaluri punctul de testare s fie ct mai aproape de centrul intervalului:

N 112

=

Se arat c

N ( j 1)j

N ( j 1)

FF

+

=Se demonstreaz c

N - numrul de evaluri, N-1 - numrul etapelor


Indicele de eficien

N-1=N-2=N-2/2 - la ultimele dou etape se ajunge practic n acelai punct (la jumtatea penultimului interval);

n felul acesta, ultima etap este de fapt inoperant, cci ea conduce n mod eronat la un punct, n loc de un interval de incertitudine.

Pentru a aplica algoritmul, trebuie cunoscut N i acesta se stabilete n funcie de lungimea intervalului de incertitudine final sau de RN n funcie de precizia dorit

Se adopt numrul Fibonacci cel mai apropiat astfel nct Rk Rki N

Algoritmul presupune stabilirea aprioric a lui FN, dar k= 0FN-k/FN nu poate fi ntotdeauna precizat de la nceput, ceea ce constituie un inconvenient al metodei.

1 22 1 1 1

1 1 22 1 1 1

dac ( ) ( )2 dac ( ) ( )

j j j jj

j j j j

f x f xf x f x

= =

kk

kk FF

FR 10

0==

=


Metoda seciunii de aur

j j j j-1

xm

xM x

1j x2j

j+1 j

xm

xM x

1j+1 x2j+1

j+1 j+1

j+1

xm

xM

La pasul j se alege j j 1+ =

j 1 j j = +

j j 1+ = j 1 j j 1 + = +}

1

1

11

+

+

=

jj

jj

jj

sj

j=

1} 21 s s= +

5 1s 0,6182

=


Metoda seciunii de aur are un interval de incertitudine cu circa 17% mai mare dect metoda Fibonacci

Dac se face o evaluare n plus, intervalele de incertitudine sunt aproximativ egale

17,1kF

ksARR


Metode de interpolare

Se pune problema determinarea pasului optim * astfel nct

se aproximeaz g cu o funcie mai simpl, al crei minim se poate calcula uor i se utilizeaz iterativ o estimaie a minimului lui g

pentru aproximaie se alege o funcie polinomial de grad doi sau trei, metoda fiind de interpolare polinomial (ptratic sau cubic)

k k

0 0min g( ) min f ( )

= + x h


Interpolarea ptratic

Pentru determinarea coeficienilor lui sunt necesare trei valori ale funciei g n punctele k, k-1, k-2.

Aceast valoare se va considera ca o nou aproximare k+1 a minimului funciei g, procedura repetndu-se pn la convergen.

La fiecare iteraie, (exceptnd prima) se face o singur evaluare a valorii funciei obiectiv

22 1 0 2g c c c , c 0= + + >

1 2* c / 2c = Minimul:

2 2 2 2 2 2* 2 1 1 2 1 2

2 1 1 2 1 2

( )( ) ( )( ) ( )( )1

2 ( )( ) ( )( ) ( )( )k k k k k k k k k

k k k k k k k k k

g g gg g g

+ + =

+ +

g


Alegerea punctelor de la iteraia urmtoare Notm i val. inf., m val. medie, s val. sup pentru mrimile

de la o anumit iteraie Notm noua valoare n = dac n m, atunci

dac g(m) g(n), atunci minimul funciei este n intervalul (i, m) i la noua iteraie se vor utiliza punctele i, n, m

dac g(m) < g(n), se aleg ca noi puncte n, m, s dac n > m, atunci

dac g(m) g(n), atunci noile puncte vor fi m, n, s dac g(m) < g(n), atunci noile puncte vor fi i, m, n

O alegere neconvenabil a punctelor iniiale poate conduce la anularea numitorului expresiei

*

*


Procedur de alegere a punctelor iniiale1. se alege pasul iniial ; se alege i=0, 1= i se calculeaz g(i) i

g(1);2. dac g(1)>g(i), minimul se afl ntr-un punct mai mic ca 1; se

alege s=1 i m=/2, se calculeaz g(1) i g(i) i se trece la pasul (6);

3. dac g(1)g(i), minimul se afl n dreapta punctului 1 i alege m=1 i 2=s=2 i se calculeaz g(1) i g(s) i se continu cu

4. dac g(2)>g(1), cel de al treilea punct a fost ales convenabil i se trece la (6);

5. dac g(2)2g(m), alegerea punctelor iniiale este realizat; n caz contrar, se pune =2, 1=, se calculeaz g(1) i se revine la (2).


Interpolarea cubic Dac derivata lui g, respectiv gradientul lui f, se pot evalua relativ

simplu, se recomand interpolarea cubic

cu minimul

Determinarea coeficienilor lui necesit dou valori ale funciei i ale derivatei n punctele k i k-1, expresia minimului fiind

, 012

23

3 ccccg +++=

( )

+= 331222 33* ccccc

)(2)(')('

)('* 1

1

+

+= kk

kk

kk

wggzwg

)(')(')()(3 11

1kk

kk

kk gggg

z

++

=

)(')(' 12 kk ggzw =


Determinarea analitic a pasului optim

Pasul optim se determin din condiiile de minim

k kdg( ) 0d+

=

x h

2

2d g 0d

>

n *

2.3.2.2. Proceduri de cutare liniar aproximativ

Dezavantaj proceduri de cutare liniar exact (de determinare a pasului optim) - numr mare de evaluri ale funciei obiectiv la fiecare iteraie

De multe ori se prefer alegerea unui pas care s asigure doar scderea funciei, fr a implica atingerea minimului pe direcia aleas regula lui Armijo: este acceptabil valoarea pasului care satisface

condiiile

< 1; obinuit se folosesc valorile = 0,2 i = 2

' 'g() g(0) +g (0) g() g(0) + g (0) si k kg() = f( + )x h


g(0)

g(0)

g(0)

g

g(0)

b

a u

Funcia g() are un minim pentru >0 panta curbei n g(0) este negativ.

Condiiile anterioare definesc o condiie acceptabil ntre a i b.


Algoritm se iniializeaz o valoare oarecare > 0; se calculeaz g() i dac g() g(0)+ g(0), se crete punnd

; se repet procedura pn cnd inegalitatea este satisfcut, adoptnd valoarea precedent pentru ;

dac g() = g(0)+ g(0) nu este ndeplinit pentru valoarea iniial , se micoreaz aceasta punnd / i se repet procedura pn cnd se gsete un care satisface condiia.

2.3.3. Metode de gradient Metodele sunt aplicabile n cazul n care f(x) este

derivabil n raport cu toate argumentele Metodele de gradient sunt metode de ordinul al II-lea, la

care se folosesc derivatele de ordinul I ale funciei Formula iterativ

Metoda mai este denumit a celei mai abrupte coborri Direcia de cutare nu conduce, de regul, ctre minimul

funciei i chiar folosirea ei n cadrul unei proceduri iterative nu este prea avantajoas

kk

kk rxx =+1

k kf ( )=r x

2.3.3. Metode de gradientMetoda gradientului optimal

k se determin printr-o procedur de extremizare unidimensional (de eliminare sau interpolare) dac funcia f(x) poate fi aproximat suficient de bine cu o funcie

ptratic, atunci poate fi utilizat i formula de calcul aproximativ

k kf ( ) = r xk - pasul optim pe direcia -rk

- direcia de deplasarek 1 k kk ,+ = x x r

k k

k k k

f ( ),*

, ( ) =

x h

h H x h

k k= h r

} k kk kk,* , = r rr H r

2.3.3. Metode de gradientObservaii Direciile succesive de deplasare sunt ortogonale

Modul de deplasare zig-zagat dezavantaj Deoarece f(x) este foarte mic n apropierea optimului, paii de

deplasare sunt mici apropierea este foarte lent Minimul este atins dup un numr infinit de pai Convergen liniar (=1) descretere n progresie geometric

Tk 1 k 1k 1 T k k k 1 T k

k 1df( ( )) df d d0 ( ) ( ) ( )

d d dd

+ ++ +

+

= = = =

x xr x r r r

x k k 1, 0+ =r r

-r1

x1

f(x)=const.

x0

x2

(b) x

1

x0

x2

x3

x4

-r0

-r1

-r2

-r3

(a)

2.3.3. Metode de gradientAplicaii pentru funcii ptratice

Condiia de extrem r* = 0 x* = 0 Dac Q > 0, x* = 0 este punct de minim n general, minimul se obine dup un numr infinit de pai. Atingerea minimului dintr-un singur pas se realizeaz numai n cazul n care

deplasarea se face pe direcia unui vector propriu al matricei Q

T1f ( ) , ,2

= nx x Qx x R f ( )= =r x Qx

*ry

x

-1r

suprafeele f(x) = const. sunt elipsoizi cu centrul n origine, direciile axelor corespunznd vectorilor proprii ai matricei Q

dac punctul de start se afl pe o astfel de ax, atunci minimul este atins dintr-un singur pas

din oricare alte puncte, atingerea minimului se face dup un numr infinit de pai

minimul poate fi atins dintr-un singur pas din orice punct dac deplasarea se face pe direcia Q-1r cu =1

dac Q = I, elipsoizii se transform n sfere i minimul este atins din orice punct prin deplasare pe direcia invers gradientului (r=Q-1r)

2.3.4. Metode bazate pe direcii conjugate

Principiu fie x0 punctul de start al algoritmului i x* punctul final de minim

x* = x0 + xs

xs Rn - vector necunoscut xs poate fi exprimat ntr-o baz oarecare n funcie de cele n

componente ale sale alegnd o baz convenabil i fcnd deplasarea din x0 succesiv n lungul axelor acestei baze, exist posibilitatea ca din n pai s ajungem n x*

evident este necesar o regul pentru stabilirea lungimilor pailor pe fiecare direcie

O posibilitate de a determina o astfel de baz convenabil este utilizarea direciilor conjugate

Atingerea minimului n n pai se obine numai la funciile ptratice


Direcii conjugate Doi vectori x,yRn se numesc conjugai (sau Q-conjugai,

sau Q-ortogonali) dac

Construirea unui set de vectori Q- conjugai (proceduri de tip Gram-Schmidt) fie setul de vectori liniar independeni v1,...,vn

se construiesc vectorii u1,...,un conjugai

se impune condiia ca uk+1 s fie conjugat cu toi vectorii uj, j= 1,...,k

n n, 0, = x Qy Q R

kk 1 k 1 jkjj 1

a+ +

=

= +u u

k 1 j k 1 j j jkj0 , , a ,

+ += = +u Qu Qu u Qu

jk 1

j jkj,

,

a+

=

Quu Qu


Direcii conjugate

Se demonstreaz c n vectori n - dimensionali conjugai sunt liniar independeni i deci pot forma o baz

Folosind vectorii Q-conjugai, se poate exprima matricea Q-1

i iTn 11

i ii 0 ,

=

=p pQ

p Qp


Metoda direciilor conjugate

pk sunt vectorii care dau direciile de deplasare i se aleg Q-conjugai

Paii de deplasare se aleg optimi pe direciile respective Precizia de stabilire a direciilor conjugate este

dependent de cea cu care se calculeaz paii optimi metoda impune o precizie ridicat n aplicarea procedurii de cutare liniar exact

k+1 k kk= + x x p

Metoda direciilor conjugateAlgoritm

1. se alege un punct iniial x0 i o direcie iniial p0 oarecare admisibil, eventual

2. se calculeaz punctul urmtor cu 3. se calculeaz noua direcie de deplasare pk+1, conjugat cu

direciile de deplasare precedente4. se repet etapele (2) i (3) pn la ndeplinirea unui criteriu

de stop

0 0f ( )= p xk

kkk pxx +=+1

Metoda direciilor conjugate

n cazul funciilor obiectiv ptratice, minimul se atinge dup n pai, deci algoritmul se oprete dup n iteraii

Dac funcia este oarecare (neptratic), minimul nu este atins dup n pai convergena este destul de rapid, mai ales dac funcia respectiv

se aproximeaz suficient de bine cu una ptratic

Pentru a evita o serie de erori de aproximare, se recomand ca dup iteraia a n-a algoritmul s se reia de la capt, reiniializndu-l din punctul atins la a n-a iteraie

Metoda direciilor conjugate n cazul funciilor ptratice metoda direciilor conjugate

conduce n n pai n punctul de minim Demonstraie

0* ,

s = +x x x

=

+=1

0

0*

n

i

iipxx

T T1f ( )2

= + + x x Qx b x

f ( ) = +x Qx b 0 0f ( ) = +x Qx bf ( *) *= + =x Qx b 0

} 0 1 0* f ( )= x x Q xi iTn 1

1i i

i 0 ,

=

=p pQ

p Qp }

i 0i iTn 1 n 10 0 0 i

i i i ii 0 i 0

f ( )* f ( )

, ,

= =

= = p , xp p

x x x x pp Qp p Qp

0 i

i i i

f ( ),,

= x p

p Qp

Metoda direciilor conjugate0 i 0 1 1 i i if ( ), f ( ) f ( ) f ( ) ... f ( ) f ( ),= + +x p x x x x x p

i+1 i ii= +x x p i 1 i iif ( ) f ( )+ = x x Qp

}0 i 0 1 i 1 i i

0 1 i 1f ( ), ... f ( ),= +x p Qp Qp Qp x p

0 i i if ( ), f ( ),=x p x p

}pi Q-conjugai

0 i

i i i

f ( ),,

= x p

p Qp } i ii i if ( ),, = x pp Qp

Metoda direciilor conjugate Observaii

calcularea direciilor conjugate n cadrul acestei proceduri se realizeaz pe baza algoritmului de tip Gram-Schmidt

formula

prezint neajunsul prezenei matricei Q n problemele de minim, aceasta corespunde matricei Hessian i

utilizarea ei ar prezenta o complicaie major (procedura nu apeleaz la derivatele de ordinul doi).

Eliminarea acestui neajuns se poate realiza printr-o transformare a formulei

jk 1

j jkj,

,

a+

=

Quu Qu

Metoda direciilor conjugate Eliminarea neajunsului prezenei matricei Q se poate

realiza printr-o transformare a formulei de calcul a coeficienilor akj

jk 1

j jkj,

,

a+

=

Quu Qu

j j=u p

( )( )

Tj 1 j k 1k 1 j jT k 1kj jT j Tj j j 1 j j

,

,

+ ++ +

+

= = =

x x QQp p Qp Qpp Qp x x Qp

} j j 1 j

.

+= y r r

}

Notez La funcii ptratice j j 1 j( )+= y Q x xjT k 1

kj j j

+

=y

y p


Metoda gradienilor conjugai Metod derivat din metoda direciilor conjugate Varianta Fletcher Reeves:

pk sunt direcii conjugate, iar k sunt pai optimi pe aceste direcii prima direcie se alege celelalte direcii se aleg k-1 se stabilesc din condiia ca pk i pk-1 s fie conjugai

dezavantaj - impune cunoaterea hessianului Q

k+1 k kk= + x x p

0 0 0f ( )= = p x rk k k-1

k-1= - +p r p

k k 1 k k 1 k 1 k 1k 10 , , ,

= = + p Qp -r Qp p Qpk k 1

k 1 k 1 k 1

,

,

=r Qp

p Qp

Metoda gradienilor conjugai

k k-1, 0,=r r

k k-1k

k k k k-1k-1

k-1 k k-1 k-1 k k-1 k-1k-1

k-1

-

,

, - , = =

- , - ,

,

r rr

r r r r

r r p r p rpi 1 i iif ( ) f ( )+ = x x Qp

k k 1

k 1 k 1 k 1

,

,

=r Qp

p Qp }k k

k-1 k-1 k-1

,

=- ,

r r

p r

k-1 k, 0=p r

k-1 k-1 k-1 k-1 k-2 k-1 k-1k-2, = ,- + = - ,-p r r r p r r

} k kk-1 k-1 k-1, = ,r rr r minimul se atinge dup n pai pentru funcii ptratice n cazul funciilor oarecare se recomand o reiniializare

dup fiecare n iteraii

2.3.5. Metode de tip Newton-Raphson

Metode de ordinul al III-lea apeleaz i la calculul derivatelor de ordinul al doilea ale funciei

obiectiv (se presupune c aceste derivate exist i sunt continue) Efectuarea calculelor suplimentare este compensat de o

rapiditate mare a convergenei La baza tuturor procedurilor din aceast categorie st

metoda Newton-Raphson


Metoda Newton-Raphson Denumirea procedurii vine de la metoda de rezolvare a sistemelor

de ecuaii, care aici se aplic referitor la condiia de anulare a gradientului

Aproximarea gradientului prin dezvoltare n serie Taylor

Considerm c noul punct este chiar punctul staionar

Dac notm

Soluia pk pentru se numete direcie Newton

k 1 k k k 1 kf ( ) f ( ) ( )( )+ += + x x H x x x

k 1f ( )+ =x 0 k 1 k 1 k k( ) f ( )+ = x x H x xk 1 k 1 k+ +

=p x -x } k kkH p r=


Metoda Newton-Raphson n cazul funciilor ptratice, din orice punct s-ar porni, se ajunge n

punctul staionar (minim dac Q>0) dintr-un singur pas

Conform procedurii N-R

n cazul altor funcii obiectiv, minimul nu este atins dintr-un singur pas, ns convergena este rapid

Se demonstreaz c metoda are o convergen ptratic (ordin de convergen 2) metoda cu cea mai rapid convergen

Dezavantaje convergena nu este asigurat dect n cazurile n care H(x)>0 calcularea matricei Hessian i a inversei acesteia conduce la creterea

volumului de calcule

T T1f ( ) ,2

= + x x Qx b x+ f ( ) = +x Qx b ( ) =H x Q* 1= x Q b,

1 0 1 0 1 1 *( )= + = x x Q Qx b x Q b=x


ncercri de ameliorare a metodei N-R

Modificri ale metodei N-R urmresc asigurarea convergenei i apeleaz fie la un pas 1 n

formula iterativ, fie la utilizarea unei matrice pozitiv definite n locul matricei H

Metode de tip regiune de ncredere constau n aproximarea secvenial a funciei obiectiv cu o funcie

ptratic i utilizarea procedurii N-R pentru aceast aproximare aceast aproximare este acceptabil doar ntr-un domeniu restrns

(regiunea de ncredere) din jurul punctului considerat Metode combinate

utilizeaz tehnici de tip N-R i proceduri cu convergen sigur, dar mai lente


ncercri de ameliorare a metodei N-R

Metode cvasi Newton merg pe ideea de a aproxima matricea H sau inversa acesteia,

aproximare care s asigure i condiia de pozitivitate la aceste proceduri nu se calculeaz derivatele de ordin doi ale

funciei obiectiv din acest punct de vedere, metodele respective sunt de ordinul al II-lea totui ele sunt strns legate de metoda N-R din care provin


Modificri ale metodei Newton-Raphson Metoda Newton modificat - procedur care asigura

convergena, pstrnd totodat direcia Newton Direcia de deplasare Nu folosete pasul unitar pe aceast direcie, ci un pas oarecare

care s asigure descreterea funciei n de obicei se calculeaz k ca pas optim pe direcia hk prin aceasta se asigur convergena procedurii i se menine viteza de

convergen foarte ridicat rmne dezavantajul necesitii de a calcula matricea Hessian

k 1 k k= - ) f )h H x x( (( (( (( (

k 1 k kk

+= + x x h


Modificri ale metodei Newton-Raphson Alte metode Newton modificate - proceduri a cror idee

este de a nlocui matricea Hk = H(xk) cu o matrice Gk care s fie legat de Hk i s ndeplineasc condiia Gk > 0 determinarea la fiecare iteraie a pozitivitii matricei Hk se

realizeaz de obicei pe baza unei factorizri a matricei (LDLT )

L este o matrice inferior triunghiular cu elementele lij, iar D este matrice diagonal (D=diag(d1,...,d2));

se demonstreaz c toi di > 0 dac i numai dac Gk > 0 factorizarea LDLT este posibil numai dac Gk este pozitiv definit Ek se ia o matrice diagonal, cu elemente nenegative pe diagonal,

alese astfel ca Gk > 0

Tk k k= = +G LDL H E


Modificri ale metodei Newton-Raphson O alt cale de a modifica metoda N-R este de a nlocui

matricea Hk cu Gk= Hk+kI, cu k>0 i suficient de mare pentru a obine Gk > 0. dezavantaj; se modific i acele elemente de pe diagonala lui Hk ce

puteau fi pstrate Un alt tip de modificare se bazeaz pe descompunerea

Se nlocuiete cu , unde , >0 i atunci

se obine o inversare a direciilor de cutare necorespunztoare dezavantaj - necesitatea calculrii valorilor proprii i

Tk k k k ,=H P P k 1 ndiag( ,..., ),= i , i = 1,n - valori proprii ale Hk

Pk - matrice ortogonal; coloanele sunt vectorii proprii pentru Hkidiag( )= { }i i = max ,

Tk k k k=G P P


Metode combinate O prim posibilitate - la primele iteraii se folosete metoda

gradientului (convergent pentru categorii foarte largi de funcii, dar lent), iar ulterior se trece la metoda N-R De regul, n apropierea punctului de minim, metoda N-R este

convergent, ns n punctele mai deprtate este posibil ca s nu fie asigurat aceast proprietate

este realizat convergena local, dar nu i cea global). Dezavantaj - comutarea de la un algoritm la altul,

este dificil de stabilit un criteriu precis care s determine comutarea O alt modalitate de a combina metoda gradientului

optimal (Cauchy) i metoda N-R este de a realiza un pas care s reprezinte o combinaie ntre pasul Cauchy pC i pasul Newton pN Exist algoritmi, cum ar fi Levenberg-Marquard, la care pasul

rezultat este mai apropiat iniial de pC, iar apoi de pN

2.3.6. Metode de tip cvasi-Newton

Principiu Se aproximeaz succesiv matricea Hessian sau inversa ei,

cutndu-se totodat s se asigure pozitivitatea acestor aproximaii Relaia de baz a algoritmilor din aceast categorie

k - se stabilete printr-o cutare liniar exact Gk este aproximarea la iteraia k pentru inversa H-1

pk=-Gkrk - direcia de cutare schimbarea gradientului se poate aproxima cu formula

notm

k 1 k kk kx x G r+ =

k 1 k k 1 kk 1( )+ ++ = r r H x x

k k+1 k= -p x x

k k+1 k= -y r r

} k kk 1G y p+ = - condiie cvasi-Newton

2.3.6. Metode de tip cvasi-Newton Primele metode din aceast categorie s-au bazat pe aproximrile i

relaiile anterioare Implementrile ulterioare au apelat i la aproximarea succesiv Bk a

matricei Hessian, direcia de cutare pk determinndu-se ca soluie a sistemului liniar

Condiia cvasi-Newton devine n acest caz Principalul avantaj

aproximrile matricei Hessian sau ale inversei acesteia nu se obin prin calcularea derivatelor de ordinul doi, ci se bazeaz doar pe cunoaterea valorilor funciei i gradientului metodele cvasi-Newton sunt metode de ordinul II

Avantajul menionat conduce la reducerea substanial a volumului de calcule la fiecare iteraie, dar prin aceasta se diminueaz i viteza de convergen, care aici este supraliniar

k kkB p r=

k kk 1B p y+ =


Metoda DFP (Davidon-Fletcher-Powell) dac dispunem de o aproximare G'k a matricei simetrice Q-1 pe

subspaiul corespunztor bazei date de vectorii Q-conjugaid0,d1,...,dk-1

se poate obine aproximarea pe un subspaiu k+1 dimensional

se aleg ca direcii conjugate direciile pk=xk+1-xk Observaie: pentru o funcie obiectiv oarecare, hessianul se

modific de la o iteraie la alta nu se poate asigura Q-conjugareavectorilor;

raionamentul se va limita la funcii ptratice, procedura extinzndu-se i la alte funcii

i iTk 1

k i ii 0' ,

,

=

= d dG

d Qd

k kT

k 1 k k k' ',

+ = +d dG G

d Qd

Metoda DFP

Se impune condiia de conjugare a direciilor pk sub forma

Ck - matrice de corecie care s asigure Q-conjugarea vectorilor pk Dac vectorii pk sunt conjugai

la funcii ptratice

soluie posibil pentru (*) este

k 1 k k k ,+ = + +G G D Ck kT

k kT kp pD

p Qp=

1k 1

+Q = G k 1+G Q = I k kk 1G Qp p+ = ( ) kk kG C Qp 0+ =k k 1 k k+

= =y r r Qp( ) kk kG C y 0+ =

} (*)( )( )Tk kk k

k kT kk

G y G yC

y G y=

Metoda DFP

Este util ca n formulele care se obin s nu apar matricea Q (care corespunde, n fond, matricei Hessian)

k kT

k kT kp pD

p Qp=

k ky Qp= } k kTk kT kp pD y p=

Metoda DFP

Algoritm1. se realizeaz iniializarea x0, G0>0 (se recomand G0=I, prima

direcie fiind atunci direcia gradientului), se pune 0=1 (sau se poate determina 0 prin cutare liniar exact); se calculeaz r0;

2. dac criteriul de stop nu este satisfcut se trece la etapa (3);3. se determin pasul optim k pe direcia Gkrk;

4. se calculeaz ; se determin rk+1,

i ;

5. se determin

6. se pune k k+1 i se revine la (2).

k 1 k kk kx x G r+ =

k k+1 k= -p x x

k k+1 k= -y r r ( )( )Tk kk k

k kT kk

,=

G y G yC

y G y

k kT

k kT k ,=p pDy p k 1 k k k

G G D C+ = + +

Metoda DFP

Proprieti ale algoritmului DFP Dac G0>0 simetric, irul {Gk} este format din matrice

simetrice pozitiv definite Dac G0=I i funcia obiectiv este ptratic cu matricea

Hessian Q, atunci vectorii p0,p1,p2,...., determinai prin algoritmul DFP sunt Q-conjugai i matricea Gk stabilit n subspaiul determinat de p0,p1,...,pk-1 este egal cu Q-1

Matricele care intervin n calcule au urmtoarele proprieti:

termenii Ck tind s corecteze iniializarea G0, iar termenii Dk tind ctre Q-1

n 1

k 0k 0

,

=

= C Gn 1 1

kk 0

=

= D Q

Metoda DFP

Proprietile menionate ale algoritmului DFP sunt valabile numai pentru funcii obiectiv ptratice

Pentru funcii obiectiv generale aceste proprieti nu mai sunt valabile, dar algoritmul prezentat asigur o bun convergen (supraliniar) dac sunt ndeplinite anumite condiii: se calculeaz exact la fiecare pas gradienii i mai ales lungimile

pailor optimi; matricea Gk nu devine singular; pentru a preveni aceast situaie:

se reiniializeaz algoritmul (se face Gk=G0=I) aceast reiniializare se recomand a fi fcut dup fiecare n pai o bun scalare poate evita tendina de singularizare a matricei G,

recomandndu-se n acest sens s se adopte0 0|| p || || y ||

Metoda DFP

Algoritmul DFP:

i. Satisface condiia cvasi-Newton ii. Genereaz o secven de matrice pozitiv definiteiii. Genereaz un set de direcii conjugate care aproximeaz

Q-1(x), astfel ca pentru funcii ptratice n felul acesta, pentru astfel de funcii, dup n iteraii, direcia calculat

coincide cu direcia Newton, ceea ce garanteaz convergena metodei n n+1 iteraii

k kk 1G y p+ =

1 1nG H Q = =


Alte proceduri cvasi-Newton Broyden: formula DFP face parte dintr-o familie

dependent de un parametru [0,1], care are aceleai proprieti (i)(iii) ca i metoda DFP

k = 0 DFP k=1 algoritmul BFGS (Broyden, Fletcher, Goldfarb, Shanno)

TTT

T T T T T T

Tk k k kk k k k

k kk k k kk 1 k k kk k k k k k k k k k k k

k k k+

= + +

G y y G G y G yp p p pG G y G yp y y G y p y y G y p y y G y

T

T T T

k k

k k k k 1 k k k 2k k

( )( )( ) ( )

>

p yy G y p G p p y

asigur meninerea pozitivitii secvenelor Gk

Alte proceduri cvasi-Newton

Dixon a demonstrat proprietatea:iv. genereaz aceeai secven de puncte {xk} care

minimizeaz f(x) teste multiple indicaser c algoritmul DFP i mai ales BFGS sunt

superiori altor algoritmi din familia Broyden diferenele care apar de obicei se datoreaz inacurateei cutrii

liniare i erorilor de rotunjire se pare c algoritmul BFGS este mai puin sensibil la aceti

factori i, ca atare, la acesta apare mai rar tendina de pierdere a pozitivitii matricei G

Alte proceduri cvasi-Newton Se pot formula algoritmi suimilari care realizeaz aproximarea

succesiv Bk a matricei H, la care direcia de cutare pk este soluie a ecuaiei

metodele care aprox. H-1 - O(n2); metodele care aprox. H - O(n3) dac n locul hassianului se actualizeaz factorii Cholesky sau ai

descompunerii LDLT ai lui B O(n2) apare avantajul verificrii relativ simple a pozitivitii matricelor Bk i al

posibilitii de corijare n cazuri nefavorabile

pentru k = 0 BFGS; pentru k =1 DFP pozitivitatea B se menine dac (ntotdeauna satisfcut n

cazul cutrii liniare exacte) i dac

k kkB p r=

TTT T

T T

k kk kk k k kk k

k 1 k k kk k k kk

,+ = + + B p p By yB B p B p b b

p y p B pT T

kkk

k k k kk

,=

B pybp y p B p

k [0,1]

Tk k > 0p y

T

T T T

k k 2

k k k k 1 k k k 2k k

( )( )( ) ( )

>

p yy B y y B y p y


S-au fcut cercetri pentru stabilirea unor algoritmi din aceast clas care s nu impun determinarea exact a pasului optim n acest sens, Powell a propus formula Este satisfcut condiia cvasi-Newton Formula impune ca vectorii p0,p1,...,pn-1 s fie liniar independeni i

nu conjugai calcul cu precizie mai sczut a pasului de deplasare

Pentru algoritmii din familia Broyden se poate renuna la cutarea liniar exact, asigurndu-se totui o convergen a matricelor Bk spre H Se pierde proprietatea Bn = H, dar se obine un ctig de eficien Deplasrile pe direciile pk trebuie realizate astfel nct s se

asigure scderea funciei i aceast scdere s fie semnificativ

( )( )( )

Tk k k k

k 1 k Tk k k

k k

k

p -G y p -G yG G

p -G y y+ = +


Convergena acestor proceduri a fost demonstrat iniial pentru funcii ptratice

Powell a demonstrat: convergena algoritmului DFP pentru funcii convexe n cazul

utilizrii pailor optimi n cazul cutrii liniare aproximative, secvenele fk tind spre f(x*) n

aceleai condiii ca i n cazul cutrii liniare exacte Convergena algoritmilor din familia Broyden a fost

demonstrat n condiia c x0 este suficient de apropiat de x* (convergen local)

Rata de convergen a algoritmilor din aceast categorie este supraliniar

2.3.7. Metode de cutare directe

Se apeleaz doar la calculul valorilor funciei obiectiv Convergena lent, calcule simple la fiecare iteraie Metodele se pot aplica i n cazul funciilor nederivabile,

sau atunci cnd derivatele se calculeaz cu mare dificultate Clasificare

metode iterative - se stabilesc puncte din ce n ce mai apropiate de minim:

algoritmul Gauss-Seidel, algoritmul Hooke i Jeeves, algoritmul Rosenbrock, algoritmul Powell

metode iterative folosind poliedre: algoritmii SIMPLEX i COMPLEX

2.3.7. Metode de cutare directe

Algoritmul Gauss-Seidel

dk sunt vectorii unitari corespunztor axelor de coordonate

dup ce se ncheie un ciclu n care s-au fcut deplasri dup toate axele, acesta se reia cu dn = d0, dn+1 = d1,...

pasul k - pas de descretere a funciei obiectiv sau pas optim

k+1 k kk= + x x d

j-1 T= [0...0 1 0...0] , j = 1,...,n

( j)d

Algoritmul Gauss-Seidel Exemplu de eec - se atinge direcia principal a "vii" i

orice deplasare ulterioar n lungul oricrei axe nu mai conduce la scderea valorii funciei

x2

x1

f(x)=ct.x*

Evitare deplasrile n lungul axelor se combin cu deplasri diagonale;

exemplu: dup fiecare ciclu de n deplasri n lungul axelor, se execut o deplasare pe direcia care unete primul cu ultimul punct al ciclului

2.3.7. Metode de cutare directeAlgoritmul Rosenbrock

Deplasrile se fac dup direcii ortogonale. La fiecare ciclu:a) Se pornete de la x0 al ciclului i se stabilesc direciile formate din n vectori

unitari ortogonali d1,...,dn; la primul ciclu, d1,...,dn corespund axelor; la ciclurile urmtoare se stabilesc prin procedeu Gram-Schmidt.

b) Se calculeaz dac pasul este considerat succes i , dac pasul este considerat insucces, se revine la xj i se efectueaz

un pas n sens invers, punnd , Obs.: ntr-o alt variant a procedurii se stabilesc noile puncte prin deplasri cu pai

optimi pe direciile respective c) Se repet etapa (b) pentru toate direciile j = 1,2,...,n, considernd succes

pasul n care d) Se reiau etapele (b) i (c) pn cnd, pe fiecare direcie, un succes este urmat

de un insucces sau Ultimul punct al ciclului xc devine punct iniial pentru ciclul urmtor, la care

prima direcie este cea care unete x0 cu xc Avantajul: la fiecare ciclu, direciile de deplasare tind s se orienteze spre

direcia principal a "vii"

j j-1 jj= + x x dj+1 jf( ) < f( )x x j j >1j+1 jf( ) > f( )x x

j j 1 < < 0

j 1 j j 1jf ( ) f ( ) +

2.3.7. Metode de cutare directeAlgoritmul Powell Direciile de deplasare n cadrul unui ciclu sunt conjugate

se demonstreaz c, pentru funcii ptratice, dup n cicluri direciile obinute sunt conjugate

Algoritmul: Se alege punctul iniial x0 i direciile de deplasare dj=ej, j=1,2,...,n,

cu , deci paralele cu axele Se determin pasul optim *j pe direciile dj, j=1,...,n i se

calculeaz Se ia noua direcie d=xnx0 i se nlocuiesc direciile d1,...,dn cu

d2,...,dn,d, care apoi se renoteaz ca d1,...,dn Se determin care asigur i se nlocuiete x0 cu

Cu acest nou x0, se revine la etapa (c), ncepnd astfel un nou ciclu

Rata de convergen este apropiat de cea ptratic, mai ales n apropierea punctului de minim

j T=[0,...0,1,0...,0]e

j j-1 * jj= + , j=1,...,nx x d

n n

min ( + )x d

n n+ .x d

2.3.7. Metode de cutare directeAlgoritmul SIMPLEX Se pornete de la o configuraie de puncte numit simplex

sub denumirea de SIMPLEX este mult mai cunoscut metoda de rezolvare a problemelor de programare liniar

Se pornete de la n+1 puncte care alctuiesc vrfurile unui hiperpoliedru regulat, de obicei avnd un vrf (x1) n origine. Coordonatele celorlalte puncte sunt

Se calculeaz f(xj), j=1,...,n+1 i se noteaz cu xm i xM punctele n care f(x) are cea mai mic i respectiv cea mai mare valoare

Se nlocuiete la fiecare iteraie xM cu un punct mai favorabil, obinndu-se o alt configuraie de n+1 puncte, pentru care se repet procedura, pn la ndeplinirea unui criteriu de stop

[ ] [ ]T T2 n 11 2 2 2 2 2 2 1c c c ... c ,..., c c c ... c+= =x x( )1 ac n 1 n 1 ,

n 2= + + ( )2 ac n 1 1

n 2= +

Algoritmul SIMPLEXAlgoritm: Se calculeaz

Se face o reflectare a punctului xM prin xG: Dac f(xR)f(xm), exist premise ca direcia reflexiei s fie favorabil

i se ncearc a extindere a acesteia Dac f(xE)f(xm), extinderea este favorabil i se nlocuiete xM cu xE i

se reiau calculele pentru noul poliedru Dac f(xE)>f(xm), se nlocuiete xM cu xR i se reiau calculele

Dac f(xR)>f(xm) Dac exist cel puin un xk astfel nct f(xR) 0-x x x x

E R R G= +( - ), >1x x x x

c G M G= +( - ), (0,1)x x x x

j m j m+0,5( - ), j=1,...,n+1x x x x

Algoritmul SIMPLEX Pentru coeficieni se pot adopta valorile:

= 1, = 0,5 , = 2 Dac =1, ct timp se fac doar extinderi sau contractri,

poliedrul se menine regulat; n caz contrar, el i pierde forma regulat.

Drept criteriu de stop se poate folosi i criteriul specific acestui algoritm

+

+

=

1

1)()(

11 n

jGj ff

nxx

METODE ANALITICE DE REZOLVARE A

PROBLEMELOR DE OPTIMIZARE STAIONAR

CU RESTRICII

2. METODE ANALITICE DE REZOLVARE A PROBL. DE OPT. STA. CU RESTRICII

Fiind dat funcia , se cere determinarea punctului x* pentru care se obine cu respectarea restriciilor

unde hi(x) i gj(x) sunt funcii scalare dependente de variabila vectorial x

Problema enunat este o problem de programare matematic, numit i problem de optimizare staionar

Problemele cu restricii inegalitate sunt reductibile la cele cu restricii egalitate, dac se introduc variabilele suplimentare vj cu relaiile Procedeul nu este des folosit deoarece presupune o complicare a

calculelor datorit variabilelor suplimentare

nf ( ) : X x R Rmin f( ),

xx

ih ( ) 0, i 1, , n,= =

CLASIFICARE Metode de substituie Metode de explorare i eliminare

asemntoare cu cele de la problemele fr restricii Metode analitice

bazate pe metoda multiplicrilor Lagrange pentru probleme cu restricii egalitate i pe extinderea acesteia la metoda Kuhn-Tucker n cazul restriciilor inegalitate

procedurile cele mai generale - stau la baza altor tipuri de proceduri introducerea multiplicatorilor Lagrange-Kuhn-Tucker permite

transformarea problemelor respective n probleme fr legturi Metode de cutare

proceduri iterative, n care se stabilesc aproximri tot mai bune pentru minimul x*

apeleaz la metodele de cutare a extremului liber i la rezultatele metodelor analitice

3.1. Metode analitice pentru probleme cu restricii de tip egalitate

Principiu Se introduc unele variabile suplimentare - multiplicatori

Lagrange - i problema se reduce la una de extrem liber Se va presupune c toate funciile care intervin au derivate

de ordinul unu continue pe ntregul domeniu care prezint interes

3.1. Metode analitice pentru probleme cu restricii de tip egalitate

Teorema multiplicatorilor Lagrange T1. Fie funciile scalare f(x), hi(x), i = 1,...,,

3.1.1. Teorema multiplicatorilor Lagrange

Se introduce funcia sintetic Lagrange (lagrangeanul)

Condiia de extrem se poate exprima prin

Restriciile se pot exprima ca

De asemenea

i ii 1

( ) f ( ) h ( )=

= + x, x x

T( ) f ( ) ( ), = +x, x h x [ ]T1 l= ... , T1( ) h ( ) ...h ( ) = h x x x

* * * **

i ii 1

( , ) f ( ) h ( )=

= + =x x x x 0

* * *( , ) ( ) = =x h x 0

*

1i i

ih ( ) 0

=

= x

* *f( ) = ( )x x

(2)

(3)

(4)

3.1.1. Teorema multiplicatorilor Lagrange

Observaii Folosind multiplicatorii Lagrange, problema de extrem cu

legturi se transform ntr-o problem cu extrem liber, dar nu pentru funcia obiectiv f(x), ci pentru funcia sintetic (x)

Rezolvarea problemei impune soluionarea unui sistem de n+ ecuaii cu n necunoscute x plus necunoscute din ecuaiile (3) se exprim xj n funcie de multiplicatorii i xj se introduc n (4) se obine un sistem de ecuaii cu

necunoscutele iRezolvarea analitic este posibil doar ntr-un numr limitat de cazuri

se apeleaz la proceduri numerice

3.1.3. Condiii suficiente de extrem

Satisfacerea condiiilor suficiente asigur c punctul x* este minim

Comparativ cu necesitatea, suficiena impune i satisfacerea unor condiii suplimentare relativ la derivatele de ordin doi i de convexitate

Se introduce mulimea vectorilor y ortogonali pe vectorii hi(x*)

Se noteaz cu Hx(x,) - matricea Hessian a funciei (x,) n raport cu variabilele x

{ }T *iY h ( ) 0, i 1,..., , 0= = = y y x y (5)

3.1.3. Condiii suficiente de extrem T2. Fie funciile scalare f(x) i hi(x), i = 1,..., definite pe

XRn i care au derivate de ordinul doi continue n x* i mulimea SX definit de relaiile

Dac exist *R care satisface

i

pentru orice yY definit de (5) atunci x* este un punct de minim local tare a lui f pe S.

* * * **

i ii 1

( , ) f ( ) h ( )=

= + =x x x x 0

T * *( , ) 0, >xy H x y

ih ( ) 0, i 1, , n= =

3.1.3. Condiii suficiente de extrem

T3. Considerm c funciile f i hi ndeplinesc condiiile din T1 i funcia sintetic (x,*) definit de

este pseudo-convex n x*. Atunci condiia

este suficient pentru ca x* s fie punct de minim global al lui f pe S.

funcia f este pseudo-convex (p-convex) n x0 X dac este difereniabil n x0 i

i ii 1

( ) f ( ) h ( )=

= + x, x x

* * * **

i ii 1

( , ) f ( ) h ( )=

= + =x x x x 0

( ) 0 0 T 0X f( ) < f( ) ( - ) f( ) < 0 x x x x x x

3.2. Metode analitice pentru probleme cu restricii de tip inegalitate

P1. Se consider funciile scalare f(x), gi(x), i = 1,...,m, definite pe Rn, avnd derivatele de ordinul unu continue pe XRn i fie mulimea SX definit prin inegalitile

Se cere determinarea punctului x* pentru care se obine

Se noteaz cu I mulimea indicilor restriciilor active, adic a restriciilor care sunt satisfcute ca egalitate n punctul x

{ }iS ; X, g ( ) 0, i 1,..., m= =x x x

Smin f ( )

xx

curs tehnici de optimizare

Documents