<<

. 32
( 59 .)



>>

SL P. T hen there exists a vector " 0 in RK such that (x , ) satis¬es
*
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.

<<

. 32
( 59 .)



>>