Computer Aided Engineering Design

OPTIMIZATION 355

12.3.4 Karush-Kuhn-Tucker (KKT) Necessary Conditions for Optimality

We may realize from above that the slack variables act as switching mediators between the constraint
and the corresponding Lagrange multiplier, that is, for yi = 0 which is when the corresponding
constraint is active or gi(X 0 ) = 0, the multiplier λi need not be zero. On then other hand, if yi≠ 0
(gi(X 0 ) < 0, i.e., ≠ 0), the corresponding multiplier has to be zero. Since it is not important to
determine the slack variables, we may eliminate them by restating Eqs. (12.22) as

∂

∂

∂

∂

∂

∂

L(, )

=

()

+

()

(^0) =
=1
X 0
X
X
X
X
X
ΛΛ fg
i
m
i

Σλ i 0

λigi(X 0 ) = 0, i = 1,... , m (12.23a)

Many texts use the notation

∇

∂∂

∂∂

∂∂

⎛

⎝

⎜

⎜

⎜

⎜⎜

⎞

⎠

⎟

⎟

⎟

⎟⎟

∇

∂∂

∂∂

∂∂

⎛

⎝

⎜

⎜

⎜

⎜

⎜

⎞

⎠

⎟

⎟

⎟

⎟

⎟

f

fx

fx

fx

g

gx

gx

n gx

j

j

j

jn

=

/

/

/

and =

/

/

/

1

2

1

2

M M

where∇f is termed as the function gradient and ∇gj is called the constraint gradient with partial
derivatives evaluated at X 0 to conveniently represent the above set of equations as

∇f(X 0 ) + λ 1 ∇g 1 (X 0 ) + λ 2 ∇g 2 (X 0 ) +... + λm∇gm(X 0 ) = 0 (nequations)

λigi(X 0 ) = 0, i = 1,... , m (12.23b)

These are known as the Karush-Kuhn-Tucker necessary conditions for optimality with inequality
constraints. The above are n + m equations in n + m variables X 0 and ΛΛΛΛΛ 0 that can be computed with
the implicit condition gi(X 0 )≤ 0, i = 1,... , m. In addition, we may note that for an active constraint
gi(X 0 ) = 0, the corresponding Lagrange multipliers λi will have to be non-negative for f(X 0 ) to be a
local minimum. To show this, we rearrange Eq. (12.23b) in short notation as

• ∇f = λ 1 ∇g 1 + λ 2 ∇g 2 +... + λm∇gm (12.24)

LetS be a feasile search direction such that any step taken along this vector lies within the feasible
region, that is, if α is the step size along S, then X = X 0 + αS must satisfy gi(X)≤ 0, i = 1,... ,, m.
Such a vector has the property that the dot product

ST∇gi≤ 0 for all gi(X) = 0 (12.25)

The geometric interpretation is that S makes an obtuse angle with the normals of active constraints,
the minimum angle being 90° for linear or concave constraints. A case is illustrated in Figure 12.11
where two constraints g 1 and g 2 among m constraints are active.
Since the other constraints g 3 ,g 4 ,... , gm are all inactive and strictly smaller than zero, the corres-
ponding multipliers are zero. Eq. (12.24) then becomes

• ∇f = λ 1 ∇g 1 + λ 2 ∇g 2 (12.26)

Premultiplying by ST gives

• ST∇f = λ 1 ST∇g 1 + λ 2 ST∇g 2 (12.27)