Metode de calcul pentru optimizarea cu restricii

n cazul existenei unor restricii se folosesc att metode de calcul bazate pe transformri ale problemelor cu restricii n probleme far restricii, ct i metode specifice; n cadrul ambelor categorii de metode, o importan deosebit o au condiiile Kuhn-Tucker.Folosirea multiplicatorilor Lagrange pentru rezolvarea problemelor cu restricii de tip egalitate este ilustrat n paragraful 1.1, condiiile Kuhn-Tucker sunt enunate n paragraful 1.2, utilizarea funciilor de penalizare pentru rezolvarea problemelor cu restricii de tip egalitate i inegalitate este prezentat n paragraful 1.3, iar cele mai utilizate metode specifice de rezolvare a problemelor cu restricii sunt ilustrate n paragraful 1.4.

3.1. Folosirea multiplicatorilor Lagrange pentru rezolvarea problemelor de optim cu restricii de tip egalitaten cazul cutrii extremului (de exemplu, a maximului) unei funcii criteriu de nvariabile

f (x)

f (x1 , x2 ,K, xn )

(1.1)

cu m restricii de tip egalitatehi (x) hi (x1 , x2 ,K, xn ) 0 ,(1.2)

i = 1, 2, ..., m (cu m < n), se demonstreaz c punctul

x* , x* ,K, x*

care maximizeaz

12nfuncia criteriu (1.1), cu respectarea restriciilor (1.2), poate fi obinut prin optimizarea (maximizarea) fr restricii a funciei

L (x, ) L (x1 , x2 ,K, xn , 1 , 2 ,K, m )

mf (x1 , x2 ,K, xn ) i hi (x1 , x2 ,K, xn ) (1.3)i1

FunciaL (x1 , x2 ,K, xn , 1 , 2 ,K, m )

estedenumitfuncieLagrange(sau

lagrangean), iar scalarii 1, 2, ... m sunt numii multiplicatorii Lagrange .Extremul (n exemplul considerat n continuare, extremul este un maxim) funciei Lagrange se obine prin intermediul condiiilor (2.12) aplicate acestei funcii, respectivL / x1 0

L / x2 0....................L / xn 0

(1.4)

Condiiile (2.12) rmn valabile, ntruct se caut extremul fr restricii al funciei L (x, ) .Metoda multiplicatorilor Lagrange rezolv deci probleme de optim cu restricii de tip egalitate prin transformarea lor n probleme de optim fr restricii, deci printr-o transformare TRE, menionat n paragraful 1.2.3.Pentru ilustrare, se consider maximizarea funciei criteriu din (1.29)

f (x1 , x2 )

f (r, l) r 2l ,(1.5)

2- reprezentnd volumul unui rezervor cilindric - n condiiile restriciei care rezult din (1.30) respectiv

h1 (x1 , x2 ) h1 (r, l) 2 r l rAplicnd (1.1) se obine

l S0 0.

(1.6)

L (x1, x2 , 1 )

L (r,l, 1 )

f (x1 , x2 ) 1h1 (x1 , x2 )

1 11f (r, l) h (r, l) r 2l (2 r l 2 r 2

S0 ) .(1.7)

Pentru gsirea valorilor optime ropt i lopt se anuleaz derivatele pariale ale funcieiL (x1, x2 ,1 ) n raport cu x1 i x2, conform cu (1.4), rezultnd din (1.7):

L / x1 L / r 2 r l 1 (2 l 4 r) 02

(1.8)

L / x2 L / l rDin (1.9) se obiner 2 1

1 2 r 0

(1.9)

(1.10)

iar din (1.8) rezult: r l 1l 21r 0 , respectivl 2 1rr 1nlocuind (1.10) n (1.11) se obine2

(1.11)

l 4 11

4 1

,(1.12)

din (1.10) i (1.12) rezultndl 2 r ,(1.13)expresie care verific i relaia (1.33) dintre valorile optime. nlocuind (1.10) i (1.12) n restricia (1.6) se obine22161 81 S0 ,de unde rezult valoarea multiplicatorului Lagrange:

1

S024

(1.14)

ntruct raza r i nalimea l trebuie s satisfac i condiiile de pozitivitate (1.31) i (1.32), din (1.10) i (1.12) rezult c n (1.14) trebuie adoptat valoarea

1

S024

(1.15)

care - prin nlocuire n (1.10) i (1.12) - asigur obinerea valorilor optime pozitive:

ropt 2

S0 ,24

lopt 4

S024

(1.16)

Metoda multiplicatorilor Lagrange poate fi utilizat i n cazul restriciilor de tip inegalitate, cu condiia ca acestea s fie n prealabil aduse la forma unor restricii de tip egalitate; o asemenea schimbare a formei restriciilor poate fi obinut prin intermediul unor variabile auxiliare.

Astfel, presupunnd c se urmrete maximizarea funciei criteriu restriciile inegalitate de forma (1.36)

f (x1 , x2 ,K, xn ) cu

g j (x1 , x2 ,K, xn ) 0

j = 1, 2, ..., p,(1.17)

aceste restricii pot fi transformate n restricii egalitate prin introducerea unor variabile auxiliare kj (j = 1, 2, ..., p), scriind p egaliti de forma

jjg k 2 0 ,(1.18)acestea reprezentnd restriciile egalitate corespunztoare restriciilor inegalitate din (1.17).

Din (1.17) i (1.18) se constat c satisfacerea egalitilor (1.18) asigur i satisfacerea

jinegalitilor (1.17), ntruct k 2 0

dac k j

0 .

Restriciile egalitate (1.18) permit folosirea metodei multiplicatorilor Lagrange pentru gsirea optimului funciei criteriu.3.2. Condiiile Kuhn-TuckerCondiiile Kuhn-Tucker au o importan deosebit n cazul optimizrii cu restricii de tip inegalitate. n prezena acestui tip de restricii, relaia (2.12) nu mai este valabil, dup cum va rezulta i din exemplul care urmeaz (Fig. 1.1); presupunnd c extremul este un

minim, condiiile Kuhn-Tucker afirm c prin deplasare din punctul de optim

x* n orice

direcie admisibil - respectiv n orice direcie care nu determin nclcarea vreunei restricii - funcia criteriu nu poate descrete.

Evident, dac din

x* ar exista vreo direcie admisibil n care funcia criteriu ar

descrete, atunci

x* nu ar mai fi punctul de minim.

2Presupunnd c se cere minimizarea funciei criteriu

f (x) cu restriciile

f (x1 , x2 ) (x1 2)

22

(x2 1)

(1.19)

g1 (x1, x2 ) x1 x2 0i

(1.20)

g2 (x1, x2 ) x1 x2 2 0 ,(1.21)

n Fig. 1.1 sunt reprezentate n planul

(x1 , x2 )

curbele circulare de nivel - obinute ca n Fig.

1.2 - precum i parabola P i dreapta D, corespunztoare cazurilor limit ale restriciilor (1.20)i (1.21), respectiv corespunztoare egalitilor2

x1 x2 0

(1.22)

x1 x2 2 0 ,(1.23)care pot fi puse sub forma

21x x 2 ,(1.24)x2 x1 2 .(1.25)

Dreapta D este determinat de intersecia dintre planul reprezentat n 3 funcia

(x1 , x2 )

i planul prin care este

g2 (x1, x2 ) x1 x2 2 ,(1.26)

iar parabola P este determinat de intersecia dintre planul reprezentat n 3 funcia2

(x1 , x2 )

i suprafaa prin care este

g1 (x1, x2 ) x1 x2 .(1.27)Din (1.20) rezult c punctele care corespund condiiei2

x2 x1

(1.28)

constitute domeniul admisibil n planul (x1 , x2 ) , iar punctele care corespund condiiei

21x x 2

(1.29)

corespund domeniului interzis, ntruct ncalc restricia (1.20); n Fig. 1.1, domeniul interzis este domeniul din afara domeniului admisibil. n mod analog este haurat domeniul x2 x1 2 , reprezentnd domeniul interzis de restricia (1.21).

x22x2 = -x1 + 2D

f (x* )E1

C1

C2 C3C4

2g ' (x* )C5C6f (x* )M

'*

Domeniul admisibil

g1 (x )

21x x2

PT

x2 = 2x1 - 1

012x1Fig. 1.1

Rezult c, din punct de vedere al respectrii ambelor restricii (1.20) i (1.21), domeniul admisibil din Fig. 1.1, include i poriunile aferente din parabola P i dreapta D.

ntruct valorile funciei criteriu

f (x1 , x2 ) scad dinspre curba circular, de nivel C1 spre

curba C6, pentru a atinge valoarea zero n punctul de minim M, cu coordonatele x1 = 2, x2 = 1, se constat, c - n condiiile respectrii restriciilor - punctul care asigur cea mai mic valoare a funciei criteriu este punctul E, cu coordonatele x1 = 1, x2 = 1 (de la interseca

dreptei D cu parabola P), acesta reprezentnd soluia restricii.

x* a problemei de optimizare cu

Dup cum s-a menionat i la nceputul acestui paragraf, se constat c n E nu are loc relaia (2.12), care este valabil numai n punctul M, ns acesta nu aparine domeniului admisibil.

n Fig. 1.1 sunt reprezentai vectorul gradientului

f (x* )

n punctul E (vector

perpendicular pe tangenta la curba circular, de nivel C2, deci avnd direcia razei cercului i sensul spre curbele de nivel cu valori descresctoare C1) i vectorul - f (x* ) , de sens opus, prelungirea acestui vector trecnd prin punctul M.Observaie. Din orice punct considerat (fcnd abstracie de existena restriciilor)

prelungirea oricrui vector - f (x* )

trece prin minimul fr restricii M, datorit faptului c

curbele de nivel sunt circulare. Acest considerent conduce la concluzia c n cazul unor curbe

de nivel circulare, metoda celei mai mari pante, cu alegerea direciei iniiale p = - f (x)

din

(2.26), conduce ntr-un singur pas pn la minimul fr restricii, ntruct prin deplasarea pe aceast direcie se ajunge n minim i nu trebuie cutat o alt direcie. Pe aceast baz a fost elaborat metoda gradientului conjugat scalat, care este indicat atunci cnd prin

operaii de modificare a scalei - de scalare - curbele de nivel de anumite forme (de exemplu, elipse) pot fi transformate n cercuri.

Tot n Fig. 1.1 sunt reprezentai i vectorii gradient ai restriciilor

g ' (x* ) i

g ' (x* ) ,

12ultimul fiind perpendicular n E pe dreapta D i avnd sensul spre zona interzis (deci sensul

creterii valorilor funciei

g2 (x1 , x2 ) x1 x2 2 ), iar primul fiind perpendicular n E pe

tangenta T la parabola P (ecuaia tangentei T n E la curba

x x 2

fiind x

2x

1) avnd

21212

sensul spre zona interzis, respectiv sensul creerii funciei

g1 (x1, x2 ) x1 x2 .

Esena condiiilor Kuhn-Tucker const n exprimarea faptului c vectorul - f (x* )

trebuie s se gseasca ntre vectorii

g ' (x* ) i

g ' (x* ) - folosind o formulare mai riguroas:

12trebuie s se gseasc n conul convex generat de vectorii

g ' (x* ) i

g ' (x* )

- respectiv

12trebuie s reprezinte o combinaie liniar a acestor vectori, de forma

f (x* ) g ' (x* )

g ' (x* )

(1.30)

1 12 2

unde 1 0, 2 0

reprezint multiplicatori Lagrange ai restriciilor.

1ntr-adevr, din punct de vedere al restriciei g1(x), direciile admisibile p sunt cele care

fac unghiuri mai mari de 90 cu vectorul

g ' (x* ) , iar din punct de vedere al restriciilor g2(x),

direciile admisibile p sunt cele care fac unghiuri mai mari de 90 cu vectorul

g ' (x* ) ,

2ntruct aceti vectori sunt perpendiculari pe tangenta T i dreapta D i deci orice direcie care

face unghiuri pn la 90 cu vectorii

g ' (x* )

sau

g ' (x* )

conduce la deplasri spre zona

12interzis; ca urmare, numai direciile p care fac unghiuri mai mari de 90 cu ambii vectori

1g ' (x* ) i

g ' (x* )

reprezint direcii admisibile.

2Conform cu (2.13), pentru ca vectorul direciei admisibile p s fac unghiuri mai mari

de 90 cu vectorii

g ' (x* ) i

g ' (x* )

sunt necesare condiiile

121g ' (x* )T p 0 ;

g ' (x* )T p 0 .(1.11)

2xPe de alt parte, din relaia (2.13) a rezultat c pentru ca o direcie p s asigure descreterea funciei criteriu f(x) este necesar ca vectorul p s fac un unghi mai mic de 90 cu vectorul gradient f ' .

Ca urmare, dac sunt respectate condiiile Kuhn-Tucker i vectorul - f (x* )

se gsete

ntre vectorii

g ' (x* ) i

g ' (x* ) conform relaiei (1.30) i Fig. 1.1 - atunci nu va exista nici o

12direcie p care s fac un unghi de pn la 90 cu vectorul - f (x* )

i n acelai timp s poat

face unghiuri de peste 90 cu ambii vectori

g ' (x* ) i

g ' (x* )

(deoarece orice direcie p care

12face unghiuri mai mari de 90 cu ambii vectori

g ' (x* ) i

g ' (x* )

va face un unghi mai mare

12de 90 i cu vectorul - f (x* ) , aflat ntre cei doi vectori), deci nu va exista nici o direcie admisibil care s conduc la descreterea funciei criteriu: n consecin, punctul E reprezint punctul de optim (minim) cu restricii.Trecnd la cazul general n-dimensional n prezena a r restricii, condiia (1.30) captaspectul

f (x*

r

'*) i gi (x )

(1.32)

cu i 0 .

i1

Condiia ca vectorul - f (x* ) s se gseasc ntre vectorii

g ' (x* ) i

g ' (x* )

este evident

12echivalent cu condiia ca vectorul

f (x* )

s se gseasc ntre vectorii - g ' (x* )

i - g ' (x* ) ,

12deci condiia general (1.32) poate fi pus i sub forma

Pe lng relaia (1.32) sau (1.33), formularea condiiilor Kuhn-Tucker include i o relaie de forma

g (x* ) 0

(1.34)

i i

Condiiile Kuhn-Tucker sunt folosite n numeroase metode de optimizare cu restricii pentru generarea de direcii de deplasare spre optim (de exemplu, n metoda proieciei gradientului, menionat n paragraful 1.4) sau pentru stabilirea unor criterii de oprire a cutrii atunci cnd verificarea condiiilor Kuhn-Tucker atest atingerea optimului.

3.3. Folosirea funciilor de penalizare pentru optimizarea cu restricii

Metoda funciilor de penalizare permite transformarea problemelor de optimizare cu restricii egalitate i inegalitate n probleme de optimizare fr restricii. Astfel, presupunnd c se urmrete minimizarea funciei criteriu f(x), cu restriciilehi (x) 0 ,i = 1, 2, ..., m(1.35)ig j (x) 0 ,j = 1, 2, ..., r(1.36) restricii de tipul (1.84) i (1.86) - se poate obine o variant a funciilor de penalizare transformnd n prealabil restriciile inegalitate (1.36) n restricii egalitate cu ajutorul unor variabile auxiliare kj, scriind restriciile egalitate echivalente

jl j (x) g

(x) k 2 0 ,(1.37)

j(transformare analoag cu cea din (1.18), intervenind ns semnul minus datorit deosebirii dintre (1.17) i (1.36), respectiv dintre caracterul restriciilor inegalitate) i cautnd apoi minimul fr restricii al funcieimr

(x, c)

f (x) ci [hi (x)] c j [li (x)] .(1.38)

i1

j 1

unde funciile [hi (x)] i [li (x)] sunt funcii de penalizare, care trebuie s satisfac anumite

condiii, iar ci 0

i c j

0 sunt factori de ponderare. n cel mai simplu caz se poate adopta

[h (x)] [h (x)]2

(1.39)

i[l j

(x)] [l

i

j(x)]2

(1.40)

i relaia (1.38) capt formamii

rj i

(x, c)

f (x)

i1

c [h (x)]2

cj 1

[l (x)]2

(1.41)

Din (1.41) se constat c dac restriciile (1.35) i (1.37) sunt satisfcute - ceea ce

nseamn c sunt satisfcute restriciile iniiate (1.35) i (1.36) - atunci funciile

(x, c) i

f(x) devin egale i deci minimizarea funciei (x, c)

asigur minimul funciei criteriu f(x).

Dac unele din restriciile (1.35) sau (1.37) sunt nclcate i dac sunt alese valori suficient de mari pentru factorii de ponderare ci i cj atunci, chiar la abateri mici ale funciilor

hi (x)

i li (x)

de la valoarea zero rezult creteri mari ale valorii funciei (x, c)

- deci nu se

poate obine un minim al acestei funcii - i prin urmare procesul de cutare este forat s

revin n domeniul n care restriciile sunt respectate.O variant a funciilor de penalizare utilizat relativ frecvent a fost elaborat de Fiaccoi McCormick . Considernd minimizarea funciei criteriu f(x), cu restriciilegi (x) 0 ,(1.42)se caut printr-un proces secvenial minimizarea fr restricii a funciei

(x, )

m1f (x)

(1.43)

i1 gi (x)unde procesul de minimizare se repet pentru diferite valori descresctoare ale factorului

(1 2 L k

0) .

Din (1.43) se constat ca minimul functiei

(x, )

va rezulta n interiorul domeniului

admisibil delimitat de restriciile (1.42), ntruct pe frontiera acestui domeniu se obine

gi (x) 0

i funcia (x, )

tinde s creasc spre infinit, deci nu poate rezulta un minim.

ntruct metoda presupune apropierea de optim din interiorul domeniului admisibil delimitat de restricii, punctul iniial al procesului secvenial trebuie s se gseasc n interiorul domeniului admisibil.Datorit caracterului secvenial, metoda a fost denumit "tehnica de minimizare secven- ial fr restricii" (n limba engleza: sequential unconstrained minimization technique SUMT).n ultimii ani, metoda funciilor de penalizare a fost combinat cu metoda multiplicatorilor Lagrange n cadrul metodei lagrangeanului extins [Cl79]; pentru minimizarea unei funcii criteriu f(x) cu restriciileg j (x) 0 ,j = 1, 2, ..., r(1.44)se folosesc variabile auxiliare i se transform, problema dat, ntr-o problem de minimizare a functiei f(x) cu restriciile echivalente

jl j (x) g

(x) k 2 0 ,(1.45)

joptimul fiind obinut prin minimizarea fr restricii a funcieirr

L (x, k, , c)

f (x) jl j (x) c[lj (x)]

rjj

j 1

j

j 1rjj

f (x)

[gj 1

(x) k 2 ] c

j 1

[g

(x) k 2 ]

(1.46)

aceast funcie reprezentnd lagrangeanul extins. Functia este o funcie de penalizare i din (1.46) se constat c n expresia lagrangeanului extins intervin att termeni corespunztori metodei multiplicatorilor Lagrange - de tipul celor din (1.3) - ct si termeni corespunztori funciilor de penalizare, de tipul celor din (1.38).

3.4. Metode specifice de optimizare cu restricii

Metodele de optimizare cu restricii menionate n acest paragraf sunt denumite specifice n sensul c nu fac apel la transformri ale problemelor de optimizare cu restricii n probleme de optimizare fr restricii.Principalele metode specifice se bazeaz pe generarea direciilor admisibile, respectiv a direciilor caracterizate de faptul c efectuarea unor deplasri mici nu ncalc restriciile. Dac o astfel de deplasare asigur i o apropiere de extrem (de exemplu, asigur micorarea funciei criteriu n cazul cutrii unui minim), atunci direcia admisibil este o direcie admisibil i

utilizabil.Cele mai frecvent folosite metode bazate pe generarea direciilor admisibile sunt cele elaborate de Zoutendijk i de Rosen.n cadrul metodei Zoutendijk , pentru minimizarea funciei criteriu f(x) cu restricii de formag j (x) 0 ,j = 1, 2, ..., r(1.47)

ise genereaz direcii admisibile p, care - conform celor menionate n paragraful 1.2 - trebuie

s fac unghiuri mai mari de 90 cu toi gradienii restriciilor satisfac relaii de forma (1.31):

g ' (x) , respectiv trebuie s

ig ' (x)T p 0 ,i = 1, 2, ..., r.(1.48)Pe de alt parte, pentru ca direciile admisibile s fie i utilizabile, ele trebuie s asigure descreterea funciei criteriu f(x), deci trebuie s satisfac o condiie de forma (2.13)

xf T p

f (x)T p 0 .(1.49)

Ca urmare, metoda include un algoritm care la fiecare iteraie selecteaz o direcie admisibil i utilizabil, asigurnd satisfacerea ambelor relaii (1.48) i (1.49), deci conducnd totodat la descreterea funciei criteriu i la deprtarea de graniele domeniilor interzise, fixate prin restriciile (1.47).n cadrul metodei Rosel, direciile admisibile sunt obinute prin intermediul utilizrii condiiilor Kuhn-Tucker, care intervin i n criteriul de oprire a procesului de cutare la atingerea optimului. Metoda este indicat ndeosebi pentru cazul restriciilor liniareg j (x) 0 ,j = 1, 2, ..., r,(1.50)care pot fi puse sub forma

jjaT x b 0 ,(1.51)

respectiv

jjaT x b .(1.52)

Ecuaiile care corespund limitei domeniilor admisibile definite de restriciile (1.52) auT

aspectul a j x b j

i corespund unor hiperplane.

Direciile de cutare sunt generate iterativ prin proiecia vectorului - f (xk ) peintersecia hiperplanelor care trec prin punctul curent xk, iar dac prin xk nu trec asemenea hiperplane (cnd punctul x se gsete n interiorul domeniului admisibil) direcia deplasrii este constituit chiar de gradientul cu semn schimbat - f (xk ) .Datorit procedeului de generare a direciilor, metoda este denumit metoda proieciei gradientului.

3.5. Folosirea condiiilor Karush-Kuhn-Tucker pentru optimizarea cu restricii

Pentru rezolvarea problemelor de optimizare convexe cu restricii de tip inegalitate se poate folosi metoda Karush-Kuhn-Tucker (KKT). Aceast metod aparine metodelor de programare neliniar i ofer un optim global n domeniul admisibil al funciei criteriu corespunztoare problemei formulate.

Formularea problemei. Fiexun punct din spaiul ni

fi :Un

(x, ) ,

i 0,1,K, m , funcii continue de n variabile definite pe o sfer deschis cu centrul n x , astfel

nct

fi (x) 0 ,

i 1,K, m . S se determine minimul funciei f, cu restriciile

fi (x) 0 ,

i 1,K, m .

Soluia problemei utilizeaz metoda multiplicatorilor Lagrange i este dat de:Teorema Karush-Kuhn-Tucker. Se definete funciaL (x, ) L (x1, x2 ,K, xn , 0 , 1, 2 ,K, m )m

i fi (x) , cu (0 ,1, 2 ,K, m )i 0numit funcie Lagrange ataat problemei formulate, n care

i ,

(1.53)i 0,1,K, m

sunt

multiplicatorii Lagrange. Presupunem c toate funciile

fi (x) ,

i 1,K, m

sunt difereniabile

n x . Condiiile Karush-Kuhn-Tucker rmn valabile n punctul x pentru o selecie nenul a multiplicatorilor Lagrange , cu 0 0 , dac sunt ndeplinite urmtoarele condiii:

(a) xL

(x, ) 0T

(condiia Lagrange de staionatitate);

n(b)(c)

i 0 , i 1,K, m (condiiile de nenegativitate);i fi (x) 0 , i 1,K, m (condiiile de staionatitate complementar lips de energie)

Observaie. Diferena esenial fa de condiiile Lagrange const n ne-negativitatea multiplicatorilor Lagrange. Pentru o condiie de staionatitate complementar, de exemplu a i-m

a condiie, presupune dou cazuri: fiecazuri.

i 0 , fie

fi (x) 0 . Rezult astfel un total de 2

nainte de a prezenta suficiena condiiilor KKT formulate mai sus, precizm c un

punct

x n

se numete punct Slater dac

fi (x) 0 , i 1,K, m .

Suficiena condiiilor KKT. (i) Condiiile KKT sunt suficiente pentru optimalitate, cu

condiia ca

0 1. Mai exact, dac condiiile KKT sunt valabile ntr-un punct x pentru o

selecie a multiplicatorilor Lagrange , cu

0 1, atunci x este un punct de minim. (ii)

Presupunem c exist un punct Slater. Dac condiiile KKT sunt valabile pentru o selecie a multiplicatorilor Lagrange , atunci 0 nu poate fi zero.Pentru claritate, n cele ce urmeaz vom prezenta cteva exemple de aplicare a teoremei

KKT.

Exemplul 1.1. S se gseasc punctul

(x1, x2 )

cel mai apropiat de punctul (2, 3) cu

condiiile ca: (a) suma coodonalelor acestuia s nu depeasc valoarea 2, (b) valoarea absolut a primei coordonate s nu depeasc valoarea 2.

2Soluie. Problema poate fi modelat ca o problem de minimizare cu restricii de tip

inegalitate, astfel: s se minimizeze funcia

11221h (x) x x 2 0 , h (x) x2 4 0 .

f (x) (x1

2)2 (x

3)2

cu restriciile

Pentru rezolvarea problemei utilizm teorema KKT. Definim funcia Lagrange

L (x, )

(x

2)2 (x

3)2 (x x

2)

(x2 4)

(1.54)

012

11221

n care vom considera 0 1 (Atenie, punctul (0, 0) este un punct Slater).Condiiile KKT:L / x1 2(x1 2) 1 22 x1 0L / x2 2(x2 3) 1 01, 2 01 (x1 x2 2) 0

(1.55)(1.56)(1.57)(1.58)

12(x2 4) 0

(1.59)2

Cazul 1: constrngerile impuse nu sunt etane, adic

x1 x2 2 0 i

x1 4 0 . n

aceast situaie condiiile KKT anterioare se rescriu sub forma:1 2 0 , 2(x1 2) 0 , 2 (x2 3) 0

din care rezult punctul

x1 2 , x2 3

care ns nu este un punct admisibil, ntruct nu

satisface condiia

x1 x2 2 0 .2

Cazul 2: numai a doua constrngere este etan, adic

x1 x2 2 0 i

x1 4 0 . n

aceast situaie condiiile KKT definite mai sus se rescriu sub forma:2

1 0 , 2 0 ,

x1 4 0 , 2(x2 3) 0 , 2 (x1 2) 2 2 x1 0

din care rezult punctul

x1 2 , x2 3 care ns, ca i n cazul 1, nu este un punct admisibil.2

Cazul 3: numai prima constrngere este etan, adic

x1 x2 2 0 i

x1 4 0 . n

aceast situaie condiiile KKT definite mai sus se rescriu sub forma:

1 0 , 2 0 ,

x1 x2 2 0 , 2 (x1 2) 1 0 , 2(x2 3) 1 0 ,

din care rezult punctul

x1 1/ 2 , x2 3 / 2 , cu 1 3 . Acesta este un punct admisibil (satiface

restriciile impuse) i reprezint un punct de optim global. Deci,

x* 1/ 2 , x* 3 / 2 , pentru

care

12fmin f (1/ 2, 3 / 2) 9 / 2. ,

La acest pas ne putem opri, deoarece am gsit o soluie care este unic. Unicitatea soluiei rezult din convexitatea strict a funciei obiectiv.Condiiile KKT sunt satisfcute pentru urmtoarele valori ale multiplicatorilor Lagrange: 0 1, 1 3 , 2 0 .

Exemplul 3.2. S se gseasc punctul

(x1, x2 )

care este cel mai apropiat de punctul de

coordonare (2, 3) cu condiiile ca: (a) valoarea primei coordonate

x1 s fie cel puin 1, (b)

punctul (x1, x2 )

se afl pe un cerc cu centrul n origine i de raz 2.

Soluie. Problema poate fi modelat ca o problem de minimizare cu restricii de tip

inegalitate, astfel: s se minimizeze funcia

f (x) (x1

2)2 (x

3)2

cu restriciile

2h (x) x2 x2 4 0 , h (x) 1 x

0 .

11221Pentru rezolvarea problemei utilizm Teorema KKT. Definim funcia Lagrange

L (x, )

(x

2)2 (x

3)2 (x2 x2 4)

(1 x )

(1.60)

012

11221

n care vom considera 0 1 (Atenie, punctul (3/2, 0) este un punct Slater).Condiiile KKT:L / x1 2 (x1 2) 21x1 2 0L / x2 2(x2 3) 2 1x2 01, 2 0(x2 x2 4) 0

(1.61)(1.62)(1.63)(1.64)

112

2 (1 x1 ) 0Cazul 1: constrngerile impuse nu sunt etane, adic

x2 x2 4 0

(1.65)i 1 x

0 . n

121aceast situaie condiiile KKT anterioare se rescriu sub forma:1 2 0 , 2(x1 2) 0 , 2 (x2 3) 0

din care rezult punctul

x1 2 ,

x2 3

care ns nu este un punct admisibil, ntruct nu

satisface restricia

x2 x2 4 0 .

12

Cazul 2: numai a doua constrngere este etan, adic

x2 x2 4 0

i 1 x

0 . n

121aceast situaie, condiiile KKT definite mai sus se rescriu sub forma:

1 0 , 2 0 , 1 x1 0 , 2 (x2 3) 0 , 2 (x1 2) 2 0

din care rezult punctul

x1 1, x2 3 ,

2 2

care ns, ca i n cazul 1, nu este un punct

admisibil i mai mult, 2 2 0 .Cazul 3: numai prima constrngere este etan, adic

x2 x2 4 0

i 1 x

0 . n

121aceast situaie condiiile KKT definite mai sus se rescriu sub forma:22

1 0 , 2 0 ,

x1 x2 4 0 , 2 (x1 2) 2 1x1 0 , 2 (x2 3) 21x2 0 ,

din care rezult punctul

x1 4 /

13 , x2 6 /

13 , cu

1 (

13 2) / 2 0 . Acesta este un

punct admisibil (satiface restriciile impuse) i reprezint un punct de optim global. Deci,

1x* 4 /

13 ,

x* 6 /

13 , pentru care

fmin

f (4 /

13, 6 /

13) (

13 2)2 .

2Condiiile KKT sunt satisfcute pentru urmtoarele valori ale multiplicatorilor

Lagrange: 0 1, 1 (

13 2) / 2 0 , 2 0 .

Observaie. Se putea merge i pe intuiie, n sensul c punctul cutat trebuie s se

gseasc pe cercul

x2 x2 4 0 , iar coordonata

x s satisfac condiia 1 x

0 , care de

1211fapt reprezint cazul 3 prezentat mai anterior.