2The method of Lagrange multipliers
IB Optimisation
2.1 Complementary Slackness
If we introduce a slack variable
z
, we note that changing the value of
z
j
does not
affect our objective function, and we are allowed to pick any positive
z
. Hence if
the corresponding Lagrange multiplier is
λ
j
, then we must have (
z
∗
(
λ
))
j
λ
j
= 0.
This is since by definition
z
∗
(
λ
)
j
minimizes
z
j
λ
j
. Hence if
z
j
λ
j
6
= 0, we can
tweak the values of z
j
to make a smaller z
j
λ
j
.
This makes our life easier since our search space is smaller.
Example. Consider the following problem:
maximize x
1
− 3x
2
subject to
x
2
1
+ x
2
2
+ z
1
= 4
x
1
+ x
2
+ z
2
+ z
2
= 2
z
1
, z
2
≥ 0.
where z
1
, z
2
are slack variables.
The Lagrangian is
L(x, z, λ) = ((1−λ
2
)x
1
−λ
1
x
2
1
)+ ((−3−λ
2
)x
2
−λ
1
x
2
2
)−λ
1
z
1
−λ
2
z
2
+4 λ
1
+2 λ
2
.
To ensure finite minimum, we need λ
1
, λ
2
≤ 0.
By complementary slackness,
λ
1
z
1
=
λ
2
z
2
= 0. We can then consider the
cases λ
1
= 0 and z
1
= 0 separately, and save a lot of algebra.