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= + +
Exemple de probleme de optimizare staionar
| 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
Exemple de probleme de optimizare staionar
| 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 = =
Exemple de probleme de optimizare staionar
| 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+
Exemple de probleme variaionale propriu-zise
| 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= =
Exemple de probleme variaionale propriu-zise
| 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.=
Exemple de probleme de control optimal
| 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= = =
Exemple de probleme de control optimal
| 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)
Exemple de probleme de control optimal
| 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=
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
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
1.1. Formularea i clasificarea problemelor de optimizare staionar
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.1. Formularea i clasificarea problemelor de optimizare staionar
x1 x2 x3 x4 x5 x6 x7 x8 x9
f(x)
x
| x6 - maxim global pe intervalul [x1,x9];| x8 - minim global pe acelai interval; | x1, x8 - minime locale unice; | toate punctele intervalului [x3,x4] - minime locale neunice; | x2, x5, x6, x9, - maxime locale; | x7 - punct de inflexiune (nu este punct de extrem local); | x6 - extrem unghiular.
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
1.2. Chestiuni preliminare
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)(
1.2. Chestiuni preliminare
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
""
" "" "
""
1.2. Chestiuni preliminare
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 =
1.2. Chestiuni preliminare
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.
1.2. Chestiuni preliminare
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 )]+
=
1.2. Chestiuni preliminare
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.
1.2. Chestiuni preliminare
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
1.2. Chestiuni preliminare
| 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
2.1.1. Metode de explorare
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
2.1.1. Metode de explorare
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
2.1.1. Metode de explorare
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
2.2.1. Proprieti ale gradientului
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
2.2.1. Proprieti ale gradientului
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
2.2.1. Proprieti ale gradientului
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
2.2.1. Proprieti ale gradientului
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
2.2.1. Proprieti ale gradientului
| 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
2.2.2. Condiii necesare i suficiente de extrem liber
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
2.2.2. Condiii necesare i suficiente de extrem liber
| 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.
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
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
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
2.2.1. Proprieti ale gradientului
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):
generalizeaz condiia cunoscut (anularea derivatei) din cazul funciilor de o singur variabil
f ( *) =x 0
2.2.2. Condiii necesare i suficiente de extrem liber
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
2.2.2. Condiii necesare i suficiente de extrem liber
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
Interpretarea geometric a pasului optim
hk f(x)=c1 f(x)=c2
xk
xk+1
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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
2.3.1. Aspecte generale privitoare la metodele de cutare
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=
Metode de eliminare unidimensional
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
=
Metode de eliminare unidimensional
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
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
2. METODE DE REZOLVARE APROBLEMELOR DE
OPTIMIZARE STAIONAR FR RESTRICII
2.3 Metode de cutare
2.3.1. Aspecte generale privitoare la metodele 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
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=
Metode de eliminare unidimensional
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
=
Metode de eliminare unidimensional
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
Metode de eliminare unidimensional
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
Metode de eliminare unidimensional
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==
=
Metode de eliminare unidimensional
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
=
Metode de eliminare unidimensional
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
2.3.2.1. Proceduri de extremizare unidimensional
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
Metode de interpolare
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
Metode de interpolare
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
*
*
Metode de interpolare
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).
Metode de interpolare
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 =
2.3.2.1. Proceduri de extremizare unidimensional
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
2.3.2.2. Proceduri de cutare liniar aproximativ
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.
2.3.2.2. Proceduri de cutare liniar aproximativ
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)
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
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
2.3.4. Metode bazate pe direcii conjugate
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
2.3.4. Metode bazate pe direcii conjugate
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
2.3.4. Metode bazate pe direcii conjugate
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
2.3.4. Metode bazate pe direcii conjugate
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
2.3.5. Metode de tip 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=
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
2.3.5. Metode de tip Newton-Raphson
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
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
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+ =
2.3.6. Metode de tip cvasi-Newton
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 = =
2.3.6. Metode de tip cvasi-Newton
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
Alte proceduri cvasi-Newton
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+ = +
Alte proceduri cvasi-Newton
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
Tehnici de optimizare- note de curs -
.l.dr.ing. Florin [email protected]
www.ac.tuiasi.ro/~fostafi
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