*

DIFFERENTIABLE NONLINEAR PROGRAMMING PROBLEMS 145

(i) Ax - c, x . 0;

* *

(ii) K a . b , j : 1, . . . , n, with equality holding if x 9 0;

G G GH H *H

(iii) . 0;

(iv) 1Ax 9 c, 2 : 0; and

*

(v) 1b, x 2 : 1c, 2.

*

If there exist an x in RL and a " 0 in RK such that (i) ”(v) hold, then x

* *

is a solution of SL P.

C¬¬ 2. L et x be a solution of the canonical linear programming problem

*

CL P. T hen there exists a vector " 0 in RK such that (x , ) satis¬es

*

(i) Ax : c, x . 0;

* *

(ii) K a . b , j : 1, . . . , n, with equality holding if x 9 0;

G G GH H *H

(iii) 1Ax 9 c, 2 : 0; and

*

(iv) 1b, x 2 : 1c, 2.

*

If there exist an x in RL and a " 0 in RK such that (i) ”(iv) hold, then x

* *

is a solution of CL P.

. 0 is absent.

Note that in Corollary 2 the condition

Exercise 4.2. Show that the problem LPI can be written as a problem in

standard form.

5. FIRST-ORDER CONDITIONS FOR DIFFERENTIABLE

NONLINEAR PROGRAMMING PROBLEMS

In this section we shall derive ¬rst-order necessary conditions for differentiable

programming problems. As noted in the introduction of this chapter, the set of

points that satisfy the necessary conditions need not furnish a solution to the

programming problem. If a solution exists, then it belongs to this set. Solution

of the necessary conditions corresponds to ˜˜bringing in the usual suspects™™ in

a criminal investigation. Further investigation is required to determine which,

if any, of these points, or ˜˜suspects,™™ furnish a solution. In this vein, we shall

show that if the data of the problem are convex, then a point that satis¬es the

necessary conditions is a solution.

Problem PI

Let X be an open convex set in RL. Let f, g, and h be C functions with domain

X and ranges in R, RK, and RI, respectively. Let

X : +x : x + X , g(x) - 0, h(x) : 0,.

Minimize f over X.

146 OPTIMIZATION PROBLEMS

The problem is often stated as

Minimize f (x)

subject to g(x) - 0, h(x) : 0.

If the constraints g(x) - 0 and h(x) : 0 are absent, the problem becomes an

unconstrained problem, which was treated in Section 2. We saw there that a

necessary condition for a point x to be a solution is that all ¬rst-order partial

*

derivatives of f vanish at x . For n : 2, 3 and 1 - k : n, the problem with

*

equality constraints and no inequality constraints is also usually treated in

elementary calculus courses. It is stated there, with or without proof, that if x

*

is a solution of the problem and if the k gradient vectors

h (x ) are linearly

H*

, j : 1, . . . , k, such that for each

independent, then there exist scalars

H

i : 1, . . . , n

*f I *h (x )

H * :0

(x ) ;

H *x

*x *

G H G

and

h (x ) : 0, j : 1, . . . , k.

H*

This is the Lagrange multiplier rule.

We now give a ¬rst-order necessary condition that is satis¬ed by a solution

of problem PI. The condition includes a more general version of the Lagrange

multiplier rule in the case that inequality constraints are absent.

We recall the notation established in Section 11 of Chapter I. If f is a

real-valued function and g : (g , . . . , g ) is a vector-valued function that is

K

differentiable at x , then

*f *f *f

f (x ) : (x ), (x ), . . . , (x )

*x

*x *x

L

and

g (x )

g (x ) *g (x )

: G.

g(x ) :

$ *x

H

g (x )

K

T 5.1. L et x be a solution of problem PI. T hen there exists a real number

*

. 0, a vector . 0 in RK, and a vector in RI such that

DIFFERENTIABLE NONLINEAR PROGRAMMING PROBLEMS 147

(i) ( , , ) " 0,

(ii) 1 , g(x )2 : 0, and

*

(iii)

f (x ) ; R

g(x ) ; R

h(x ) : 0.

* * *

Vectors ( , , ) having the properties stated in the theorem are called

multipliers, as are the components of these vectors.

De¬nition 5.1. A point x at which the conclusion of Theorem 5.1 holds will

*

be called a critical point for problem PI.

Thus, Theorem 5.1 says that a solution x of problem PI is a critical point.

*

Remark 5.1. The necessary condition asserts that . 0 and not the stronger

statement 9 0. If 9 0, then we may divide through by in (ii) and (iii)

and relabel / and / as and , respectively, and thus obtain statements

(i)”(iii) with : 1. In the absence of further conditions that would guarantee

that 9 0, we cannot assume that : 1. We shall return to this point later.

Remark 5.2. If g Y 0, that is, the inequality constraints are absent, Theorem

5.1 becomes the Lagrange multiplier rule.

. 0 and g(x ) - 0, condition (ii) is equivalent to

Remark 5.3. Since

*

g (x ) : 0, i : 1, . . . , m. (ii)

GG *

Condition (iii) is a system of n equations

*f K *g (x ) I *h (x )

G * ; G * : 0,

(x ) ; j : 1, . . . , n. (iii)

*x * G *x G *x

H G H G H

Remark 5.4. The necessary conditions are also necessary conditions for a local

minimum. For if x is a local minimum, then there exists a 9 0 such that

*

f (x ) - f (x) for all x that are in B(x , ) 5 X and that satisfy the constraints

* *

g(x) - 0 and h(x) : 0. Thus, x is a global solution to the problem in which

*

X is replaced by X 5 B(x , ).

*

Remark 5.5. Theorem 5.1, under additional hypotheses guaranteeing that

9 0, was proved in Kuhn and Tucker [1951]. This paper had great impact

since interest in nonlinear programming was developing at that time in

economics and other areas of application. The theorem with . 0 had been

proved in John [1948], and prior to that, again under conditions ensuring that

9 0, in Karush, [1939]. The results of John and of Karush were unnoticed

when they appeared, probably because interest in programming problems had

not yet come about. These papers were looked upon only as mathematical

148 OPTIMIZATION PROBLEMS

generalizations of the Lagrange multiplier rule. In the literature, Theorem 5.1,

with additional hypotheses guaranteeing that 9 0, is often referred to as the

Karush”Kuhn”Tucker Theorem. Theorem 5.1, as stated here, is referred to as

the Fritz John theorem. We shall adopt this terminology and refer to Theorem

5.1 as the FJ theorem and call the multipliers ( , , ) FJ multipliers.

The next example, due to Fiacco and McCormick [1968], illustrates the use of

Theorem 5.1 and will be used to illustrate some subsequent theorems.

Example 5.1. Let X : R, let

f (x) : (x 9 1) ; x,

and let

g(x) : 2kx 9 x - 0, k 9 0.

For each value of k 9 0 we obtain a programming problem . The feasible set

I

X for problem is the set of points on and exterior to the graph of the

I I

parabola x : 2kx , and the function to be minimized is the distance from x

to the point (1, 0). In Figure 4.1 we have sketched some level curves of f and

the parabolas for two values of k. Although the solution can be read from

Figure 4.1, we will apply the appropriate theorems in this section and in the

next section to solve this problem.

By straightforward calculation

f : (2(x 9 1), 2x ),

g : (2k, 92x ).

From Theorem 5.1 we get that if a point x is a solution to the programming

problem , then there exist a . 0 and a . 0 with ( , ) " (0, 0) such that

I

( , ) and x satisfy

(2(x 9 1), 2x ) ; (2k, 92x ) : (0, 0), (1)

(2kx 9 x) : 0. (2)

If : 0, then since " 0, equation (1) would imply that k : 0, contradic-

ting the assumption that k 9 0. Hence we may take : 1. If : 0, then (1)

would imply that x : 1 and x : 0. The point (1, 0) is not feasible for any

value of k 9 0, so we may assume that " 0 in (1). It then follows from (2)

that 2kx 9 x : 0; that is, the point x must lie in the parabola. Thus we may

replace (1) and (2) by

x : 2kx .

((x 9 1), x ) ; (k, 9x ) : (0, 0), (3)

DIFFERENTIABLE NONLINEAR PROGRAMMING PROBLEMS 149

Figure 4.1.