METODE DE CALCUL
PENTRU OPTIMIZAREA CU RESTRICŢII
CONDIŢIILE KUHN-TUCKER
În cazul optimizǎrii cu restricţii de tip inegalitate, relaţia
*
'( ) ( )ff x x 0
nu mai este valabilǎ
Exemplu:
22
1 2 1 2
( ) ( , ) ( 2) ( 1)f x f x x x x
cu restricţiile
2
1 1 2 1 2
( , ) 0g x x x x
2 1 2 1 2
( , ) 2 0g x x x x
corespunzǎtare egalitǎţilor
2
12
0xx
12
2 20xx
se cere minimizarea funcţiei criteriu
care pot fi puse sub forma
2
21
xx
21
2xx
Avem
.
Avem dreapta D, determinatǎ de intersecţia dintre planul x1,x2şi
suprafaţa prin care este reprezentatǎ în R3 funcţia
2 1 2 1 2
( , ) 2g x x x x
parabola P, determinatǎ de intersecţia dintre planul x1,x2şi
suprafaţa prin care este reprezentatǎ în R3 funcţia
2
1 1 2 1 2
( , )g x x x x
Din punct de vedere al respectǎrii ambelor restricţii, domeniul
admisibil este cel nehaşurat în figură, incluzând şi porţiunile
aferente din parabola P şi dreapta D.
Valorile funcţiei criteriu
12
( , )f x x
scad dinspre curba circularǎ de nivel C1spre curba C13
pentru a atinge valoarea zero în punctul de minim M, cu
coordonatele
12x
21x
punctul care asigurǎ cea mai micǎ valoare a funcţiei criteriu
este punctul E, cu coordonatele
11x
21x
(de la intersecţia dreptei D cu parabola P), aceasta reprezentând
soluţia x*a problemei de optimizare cu restricţii
se constatǎ cǎ în punctul E nu are loc relaţia
*
'( ) ( )ff x x 0
care este valabilǎ numai în punctul M, însǎ acesta nu
aparţine domeniului admisibil
În figură sunt reprezentaţi vectorul gradientului
*
'( )fx
în punctul E (vector perpendicular pe tangenta la curba
circularǎ de nivel C8, deci având direcţia razei cercului şi sensul
spre curbele de nivel cu valori crescǎtoare C7, C6, C5etc.) şi
vectorul
*
'( )fx
de sens opus, prelungirea acestui vector trecând prin punctul M
Din orice punct considerat (fǎcând abstracţie de existenţa
restricţiilor) prelungirea oricǎrui vector
*
'( )fx
trece prin minimul fǎrǎ restricţii M, deoarece curbele de nivel
sunt circulare
In cazul unor curbe de nivel circulare, metoda celei mai mari
pante, cu alegerea direcţiei iniţiale
'( )p f x
conduce într-un singur pas pânǎ la minimul fǎrǎ restricţii,
întrucât prin deplasarea pe aceastǎ direcţie se ajunge în minim
şi nu trebuie cǎutatǎ o altǎ direcţie
Pe aceastǎ bazǎ a fost elaboratǎ metoda gradientului conjugat
scalat, care este indicatǎ atunci când prin operaţii de
modificare a scalei –de scalare –curbele de nivel de anumite
forme (de exemplu elipse) pot fi transformate în cercuri
în figură sunt reprezentaţi şi vectorii gradienţi ai restricţiilor:
'*
1()gx
'*
2()gx
perpendicular în E pe tangenta T la parabola P
(ecuaţia tangentei T în E la curba
2
21
xx
fiind
21
21xx
având sensul spre zona haşuratǎ, respectiv sensul creşterii
funcţiei
2
1 1 2 1 2
( , )g x x x x
perpendicular în E pe dreapta D şi având sensul
spre zona haşuratǎ (deci sensul creşterii valorilor
funcţiei
2 1 2 1 2
( , ) 2g x x x x
)
*
'( )fx
trebuie sǎ se gǎseascǎ între vectorii
'*
1()gx
şi
'*
2()gx
* ' * ' *
1 1 2 2
'( ) ( ) ( )x
f x g g x
aceşti vectori sunt perpendiculari pe tangenta T şi dreapta D şi
deci orice direcţie care face unghiuri pânǎ la 900cu vectorii
'*
1()gx
sau
'*
2()gx
conduce la deplasǎri spre zona interzisǎ, hasuratǎ
Ca urmare, sunt admise numai direcţiile p care fac unghiuri
mai mari de 900cu ambii vectori şi
'*
1()gx
'*
2()gx
Conform cu
0, pfpf T
xx
pentru ca vectorul direcţiei admisibile p sǎ facǎ unghiuri mai
mari de 900cu vectorii
i
sunt necesare condiţiile
' * ' *
12
( ) 0; ( ) 0
TT
g x p g x p
Pe de altǎ parte, tot din relaţia
0, pfpf T
xx
a rezultat cǎ pentru ca o direcţie p sǎ asigure descreşterea
funcţiei criteriu f(x) este necesar ca vectorul p sǎ facǎ un
unghi mai mic de 900cu vectorul gradient
'
x
f
şi
'*
1()gx
'*
2()gx
în cazul general n-dimensional în prezenţa a r restricţii
* ' *
1
'( ) ( )
r
ii
i
f x g x
0
i
* ' *
1
'( ) [ ( )]
r
ii
i
f x g x
Condiţiile Kuhn-Tucker afirmǎ cǎ prin deplasarea din punctul
de optim x*în orice direcţie admisibilă – respectiv în orice
direcţie care nu determinǎ încǎlcarea vreunei restricţii –
funcţia criteriu nu poate descreşte
Condiţiile Kuhn-Tucker sunt folosite în numeroase metode de
optimizare cu restricţii pentru generarea de direcţii de
deplasare spre optim (de exemplu, în metoda proiecţiei
gradientului, sau pentru stabilirea unor criterii de oprire a
cǎutǎrii atunci când verificarea condiţiilor Kuhn-Tucker atestǎ
atingerea optimului
