Feltételes optimalizálás

Ebben a szakaszban azt vizsgáljuk, hogyan kell olyan optimalizációs problémát megoldani, melyben a változókra különböző feltételek vannak kiróva.

Egyenletekkel adott feltételek

Tegyük fel, hogy f( x 1 , x 2 ,, x d ) minimumát kell megkeresni úgy, hogy a változókra

g i (x)=0,  i=1,2,,p

jellegű kényszerek vannak megadva. A megoldást szolgáltató eljárást Lagrange-féle multiplikátor-módszernek nevezzük. Ez a következő lépéseket foglalja magában:

  1. Definiáljuk az ún. Lagrange függvényt L(x,λ)=f(x)+ i=1 p λ i g i (x) módon, ahol λ i -k a Lagrange-féle multiplikátoroknak nevezett segédváltozók.

  2. A Lagrange függvény x és λ i szerinti elsőrendű deriváltjait tegyük nullává:

    1. L x i =0,    i=1,2,,d,

és

    1. L λ i =0,    i=1,2,,p.

  1. Oldjuk meg a (d+p) számú egyenletet az x * stacionárius pont és a hozzá tartozó λ i multiplikátorok megtalálására.

Az alábbi példa szemlélteti, hogy hogyan működik a Lagrange-féle multiplikátor-módszer.

E.2. Példa.

Legyen f(x,y)=x+2y . Tegyük fel, hogy az f(x,y) függvényt az x 2 + y 2 4=0 feltételre nézve szeretnénk minimalizálni. A Lagrange-féle multiplikátor-módszer a következő módon használható ennek a kényszerfeltétel melletti optimalizációs feladatnak a megoldására.

Először vezessük be az

L(x,y,λ)=x+2y+λ( x 2 + y 2 4)

Lagrange-függvényt, ahol most λ az egyetlen Lagrange-féle multiplikátor. A minimumhely meghatározásához a Lagrange-függvényt kell differenciálnunk a változói szerint:

L x =1+2λx=0, (E.10)

L y =2+2λy=0, (E.11)

L λ = x 2 + y 2 4=0.

Ezen egyenletek megoldása a λ=± 5 /4 , x=2/ 5 és y=4/ 5 megoldást szolgáltatja. Ha λ= 5 /4 , akkor f(2/ 5 ,4/ 5 )=10/ 5 . Hasonlóan λ= 5 /4 esetén f(2/ 5 ,4/ 5 )=10/ 5 . Így f(x,y) minimuma az x=2/ 5 , y=4/ 5 pontban van.

Egyenlőtlenségekkel adott feltételek

Tegyük fel, hogy f( x 1 , x 2 ,, x d ) minimumát kell megkeresni úgy, hogy a feltételeink most

h i (x)0,  i=1,2,,q,

alakú egyenlőtlenségek. A módszer itt is hasonló, mint a fent leírt Lagrange-módszer. A különbség annyi, hogy további megkötések lépnek fel. Az optimalizációs probléma most a következő Lagrange-függvényhez és feltételekhez vezet:

L=f(x)+ i=1 q λ i h i (x), (E.12)

L x i =0,    i=1,2,,d, (E.13)

h i (x)0,    i=1,2,,q, (E.14)

λ i 0,    i=1,2,,q, (E.15)

λ i h i (x)=0,    i=1,2,,q. (E.16)

Az egyenlőségekkel és egyenletekkel adott feltételeket együttesen Karush-Kuhn-Tucker (KKT) feltételeknek nevezzük. Megjegyezzük, hogy a Lagrange multiplikátorok most már korlátozva vannak (alulról).

E.3. Példa.

Tegyük fel, hogy az f(x,y)= (x1) 2 + (y3) 2 függvényt akarjuk minimalizálni az

x+y2,    és    yx

feltételekre nézve.

A probléma Lagrange-függvénye L= (x1) 2 + (y3) 2 + λ 1 (x+y2)+ λ 2 (xy) az alábbi KKT-féle megkötésekkel:

L x =2(x1)+ λ 1 + λ 2 =0, (E.17)

L y =2(y3)+ λ 1 λ 2 =0, (E.18)

λ 1 (x+y2)=0, (E.19)

λ 2 (xy)=0, (E.20)

λ 1 0,   λ 2 0,  x+y2,  yx. (E.21)

A fentiek megoldásához először az (E.19) és (E.20) egyenletek összes lehetőségét kell számba venni.

1. eset:

λ 1  = 0 λ 2  = 0. Ebben az esetben a következő egyenleteket kapjuk:

2(x1)=0    és    2(y3)=0,

melynek megoldása x=1 és y=3 . Mivel x+y=4 , ez nem elfogadható megoldás, hiszen megsérti az x+y2 feltételt.

2. eset:

λ 1  = 0 λ 2   0. Most a következő egyenletek adódnak:

xy=0,  2(x1)+ λ 2 =0,  2(y3) λ 2 =0,

melynek megoldása x=2 , y=2 és λ 2 =2 , mely megint csak elfogadhatatlan a λ 2 0 és x+y2 feltételek miatt.

3. eset:

λ 1   0 λ 2  = 0. Ez az eset a következő egyenleteket implikálja:

x+y2=0,  2(x1)+ λ 1 =0,  2(x+1)+ λ 1 =0,

a megoldás pedig x=0 , y=2 és λ 1 =2 , ami már megfelelő.

4. eset:

λ 1   0 λ 2   0. Ebben az esetben a következő egyenleteket kapjuk:

x+y2=0,  xy=0,  2(x1)+ λ 1 + λ 2 =0,  2(y3)+ λ 1 λ 2 =0,

és a megoldás x=1 , y=1 , λ 1 =2 , λ 2 =2 , ez ismét csak nem megfelelő.

A fentiek miatt az egyetlen, minden feltételt kielégítő megoldás x=0 és y=2 .

A KKT-feltételekkel adott egyenlet- és egyenlőtlenségrendszer megoldása gyakran igen fáradságos, különösen, ha a feltételek száma nagy. Ilyen esetekben többnyire nem is lehetséges zárt alakban felírni a megoldást, lineáris és kvadratikus programozási módszereket kell igénybe vennünk.