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.