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:

és

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.

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)= (x−1) 2 + (y−3) 2 függvényt akarjuk minimalizálni az

x+y≤2,    és    y≥x

feltételekre nézve.

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

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

∂L ∂y =2(y−3)+ λ 1 − λ 2 =0, (E.18)

λ 1 (x+y−2)=0, (E.19)

λ 2 (x−y)=0, (E.20)

λ 1 ≥0,   λ 2 ≥0,  x+y≤2,  y≥x. (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(x−1)=0    és    2(y−3)=0,

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

2. eset:

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

x−y=0,  2(x−1)+ λ 2 =0,  2(y−3)− λ 2 =0,

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

3. eset:

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

x+y−2=0,  2(x−1)+ λ 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+y−2=0,  x−y=0,  2(x−1)+ λ 1 + λ 2 =0,  2(y−3)+ λ 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.