5

CONSTRAINED
OPTIMALITY CRITERIA

In Chapters 2 and 3, we discussed the necessary and sufficient optimality

criteria for unconstrained optimization problems. But most engineering prob-
lems involve optimization subject to several constraints on the design varia-
bles. The presence of constraints essentially reduces the region in which we
search for the optimum. At the outset, it may appear that the reduction in the
size of the feasible region should simplify the search for the optimum. On
the contrary, the optimization process becomes more complicated, since many
of the optimality criteria developed earlier need not hold in the presence of
constraints. Even the basic condition that an optimum must be at a stationary
point, where the gradient is zero, may be violated. For example, the uncon-
strained minimum of ƒ(x) ⫽ (x ⫺ 2)2 occurs at the stationary point x ⫽ 2.
But if the problem has a constraint that x ⭓ 4, then the constrained minimum
occurs at the point x ⫽ 4. This is not a stationary point of ƒ, since ƒ⬘(4) ⫽
4. In this chapter we develop necessary and sufficient conditions of optimality
for constrained problems. We begin with optimization problems involving
only equality constraints.

5.1 EQUALITY-CONSTRAINED PROBLEMS

Consider an optimization problem involving several equality constraints:

Minimize ƒ(x1, x2, . . . , xN)

Subject to hk (x1, . . . , xN) ⫽ 0 k ⫽ 1, . . . , K

218 Engineering Optimization: Methods and Applications, Second Edition. A. Ravindran, K. M. Ragsdell and
G. V. Reklaitis © 2006 John Wiley & Sons, Inc. ISBN: 978-0-471-55814-9
 5.2 LAGRANGE MULTIPLIERS 219

In principle, this problem can be solved as an unconstrained optimization

problem by explicitly eliminating K independent variables using the equality
constraints. In effect, the presence of equality constraints reduces the dimen-
sionality of the original problem from N to N ⫺ K. Once the problem is
reduced to an unconstrained optimization problem, the methods of Chapters
2 and 3 can be used to identify the optimum. To illustrate this, consider the
following example.

Example 5.1

Minimize ƒ(x) ⫽ x1x2x3

Subject to h1(x) ⫽ x1 ⫹ x2 ⫹ x3 ⫺ 1 ⫽ 0

Eliminating the variable x3 with the help of h1(x) ⫽ 0, we get an unconstrained

optimization problem involving two variables:

min ƒ(x1, x2) ⫽ x1x2(1 ⫺ x1 ⫺ x2)

The methods of Chapter 3 can now be applied to identify the optimum.

The variable elimination method is applicable as long as the equality con-

straints can be solved explicitly for a given set of independent variables. In
the presence of several equality constraints, the elimination process may be-
come unwieldy. Moreover, in certain situations it may not be possible to solve
the constraints explicitly to eliminate a variable. For instance, in Example 5.1,
if the constraints h1(x) ⫽ 0 were given as

h1(x) ⫽ x12x3 ⫹ x2x32 ⫹ x⫺1

2 x1 ⫽ 0

then no explicit solution of one variable in terms of the others would be

possible. Hence, in problems involving several complex equality constraints,
it is better to use the method of Lagrange multipliers, which is described in
the next section, for handling the constraints.

5.2 LAGRANGE MULTIPLIERS

The method of Lagrange multipliers essentially gives a set of necessary con-

ditions to identify candidate optimal points of equality-constrained optimi-
zation problems. This is done by converting the constrained problem to an
equivalent unconstrained problem with the help of certain unspecified param-
eters known as Lagrange multipliers.
220 CONSTRAINED OPTIMALITY CRITERIA

Consider the minimization of a function of n variables subject to one equal-

ity constraint:

Minimize ƒ(x1, x2, . . . , xN) (5.1)

Subject to h1(x1, x2, . . . , xN) ⫽ 0 (5.2)

The method of Lagrange multipliers converts this problem to the following

unconstrained optimization problem:

Minimize L(x, v) ⫽ ƒ(x) ⫺ vh1(x) (5.3)

The unconstrained function L(x; v) is called the Lagrangian function, and v

is an unspecified constant called the Lagrange multiplier. There are no sign
restrictions on the value of v.
Suppose for a given fixed value of v ⫽ vo the unconstrained minimum of
L(x; v) with respect to x occurs at x ⫽ x o and x o satisfies h1(x o) ⫽ 0. then, it
is clear that x o minimizes Eq. (5.1) subject to (5.2) because for all values of
x that satisfy (5.2), h1(x) ⫽ 0 and min L(x; v) ⫽ min ƒ(x).
Of course, the challenge is to determine the appropriate value for v ⫽ vo
so that the unconstrained minimum point x o satisfies (5.2). But this can be
done by treating v as a variable, finding the unconstrained minimum of (5.3)
as a function of v, and adjusting v such that (5.2) is satisfied. We illustrate
this with the following example:

Example 5.2

Minimize ƒ(x) ⫽ x21 ⫹ x22

Subject to h1(x) ⫽ 2x1 ⫹ x2 ⫺ 2 ⫽ 0

The unconstrained minimization problem becomes

Minimize L(x; v) ⫽ x21 ⫹ x22 ⫺ v(2x1 ⫹ x2 ⫺ 2)

Solution. Setting the gradient of L with respect to x equal to zero,

⭸L
⫽ 2x1 ⫺ 2v ⫽ 0 ⇒ x 1o ⫽ v
⭸x1

⭸L v
⫽ 2x2 ⫺ v ⫽ 0 ⇒ x 2o ⫽
⭸x2 2

To test whether the stationary point x o corresponds to a minimum, we com-

pute the Hessian matrix of L(x; v) with respect to x as
 5.2 LAGRANGE MULTIPLIERS 221

HL(x; v) ⫽ 冋 册
2
0
0
2

which is positive definite. This implies that HL(x; v) is a convex function for
all x. Hence x o1 ⫽ v, x o2 ⫽ v /2 corresponds to the global minimum. To deter-
mine the optimal v, we substitute the values of x o1 and x o2 in the constraint
2x1 ⫹ x2 ⫽ 2 to get 2v ⫹ v /2 ⫽ 2 or vo ⫽ –45 . Hence the constrained minimum
is attained at x o1 ⫽ –45 , x o2 ⫽ –25 , and min ƒ(x) ⫽ –45 .

In the solution of Example 5.2, we treated L(x; v) as a function of two

variables x1 and x2 and considered v as a parameter whose value is ‘‘adjusted’’
to satisfy the constraint. In problems where it is difficult to get an explicit
solution to

⭸L
⫽0 for j ⫽ 1, 2, . . . , N
⭸xj

as a function of v, the values of x and v can be determined simultaneously

by solving the following system of N ⫹ 1 equations in N ⫹ 1 unknowns:

⭸L
⫽0 for j ⫽ 1, 2, . . . , N
⭸xj

h1(x) ⫽ 0

Any appropriate numerical search technique discussed in Chapter 3 (e.g.,

Newton’s method) could be used to determine all possible solutions. For each
of the solutions (x o; vo), the Hessian matrix of L with respect to x has to be
evaluated to determine whether it is positive definite for a local minimum (or
negative definite for a local maximum).

Example 5.3

Maximize ƒ(x) ⫽ x1 ⫹ x2
Subject to x12 ⫹ x22 ⫽ 1
222 CONSTRAINED OPTIMALITY CRITERIA

Solution

L(x; v) ⫽ x1 ⫹ x2 ⫺ v(x12 ⫹ x22 ⫺ 1)

⭸L
⫽ 1 ⫺ 2vx1 ⫽ 0
⭸x1

⭸L
⫽ 1 ⫺ 2vx2 ⫽ 0
⭸x2

h1(x) ⫽ x21 ⫹ x22 ⫺ 1 ⫽ 0

There are two solutions to this system of three equations in three variables,
given by

(x (1); v1) ⫽ ⫺ 冉 1 1
,⫺ ;⫺
兹 2 兹2
1
2 冪冊
(x (2); v2) ⫽ 冉 1
,
1
兹 2 兹2
; 冪冊 1
2

The Hessian matrix of L(x; v) with respect to x is given by

HL(x; v) ⫽ 冋 ⫺2v
0
0
⫺2v 册
Evaluating the matrix H at the two solutions, we find that

HL(x (1); v1) ⫽ 冋

兹2
0
0
兹2 册 is positive definite

and

HL(x (2); v2) ⫽ 冋 ⫺兹2

0
0
⫺兹2 册 is negative definite

Hence, (x (2); v2) corresponds to the maximum of L with respect to x, and the
optimal solution is x o1 ⫽ x 2o ⫽ 1/ 兹2. [Note that (x (1); v1) corresponds to the
minimum of L.]

It is to be emphasized here that if we consider L as a function of three

variables, namely, x1, x2 and v, then the points (x (1); v1) and (x (2); v2) do not
correspond to a minimum or maximum of L with respect to x and v. As a
matter of fact, they become saddlepoints of the function L(x, v). We shall
discuss saddlepoints and their significance later in this chapter.
 5.2 LAGRANGE MULTIPLIERS 223

The Lagrange multiplier method can be extended to several equality con-

straints. Consider the general problem

Minimize ƒ(x)
Subject to hk (x) ⫽ 0 k ⫽ 1, 2, . . . , K

The Langrange function becomes

冘vh
K
L(x; v) ⫽ ƒ(x) ⫺ k k
k⫽1

Here v1, v2, . . . , vK are the Lagrange multipliers, which are unspecified
parameters whose values will be determined later. By setting the partial de-
rivatives of L with respect to x equal to zero, we get the following system of
N equations in N unknowns:

⭸L(x; v)
⫽0
⭸x1

⭸L(x; v)
⫽0
⭸x2

⯗
⭸L(x; v)
⫽0
⭸xN

It is difficult to solve the above system as a function of the vector v explicitly,

we can augment the system with the constraint equations

h1(x) ⫽ 0
h2(x) ⫽ 0
⯗
hK (x) ⫽ 0

A solution to the augmented system of N ⫹ K equations in N ⫹ K variables

gives a stationary point of L. This can then be tested for minimum or maxi-
mum by computing the Hessian matrix of L with respect to x as discussed in
the single-constraint case.
There may exist some problems for which the augmented system of N ⫹
K equations in N ⫹ K unknowns may not have a solution. In such cases, the
Lagrange multiplier method would fail. However, such cases are rare in prac-
tice.