components except the ith are zero and whose ith component is 1. Then z is

G

in dom( ) and

(z ) . (0) 9 1 , z 2 9 1 , 02 : (0) 9 9 (0), (8)

G G G

the last inequality holding because : 0.

G

Since z . 0 and z : 0, we have X(0) 3 X(z ). Therefore,

G G

(z ) : inf+ f (x) : x + X(z ), - inf + f (x) : x + X(0), : (0),

G G

which contradicts (8). Thus . 0.

Remark 3.2. The vector 9 is any vector in * (0) and so need not be unique.

By Theorem III.3.1 the vector 9 is unique if and only if is differentiable at

0, in which case 9 :

(0). Thus, 9 gives the direction of maximum rate

of increase at 0 of the value function .

If is not differentiable, then by Exercise III.2.3,

(0, v) . 19 , v2 for all v in RK>L,

where (0, v) is the directional derivative of at 0 in the direction v. Thus,

9 again in a sense measures the changes in as we move away from the

origin. The vector is therefore called a sensitivity vector.

We noted in Remark 2.5 that if we know the multipliers ( , ) of Theorem

**

2.2, then we may replace the constrained problem by an unconstrained

problem. In other words, the multipliers ( , ) of Theorem 2.2 are Kuhn”

**

Tucker vectors. By Corollary 1 to Theorem 2.3, if CPII has a solution, then

the set K of Kuhn”Tucker vectors is equal to the set M of multiplier vectors.

194 CONVEX PROGRAMMING AND DUALITY

(0) is ¬nite, then every vector in

In the next lemma we shall show that if

9* (0) is a Kuhn”Tucker vector.

L 3.3. L et

(0) Y inf+ f (x) : x + X,,

where X : +x : g(x) - 0, h(x) : 0,, be ¬nite and let * (0) " `. T hen for each

: ( , ) such that 9 + * (0) the vector is nonnegative and

(0) : inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x + RL,.

Proof. Since 9 + * (0), for each z in dom( )

(z) . (0) 9 1 , z2. (9)

From the proof of Lemma 3.2 we get that . 0. For all x in RL, g(x) - g(x)

and h(x) : h(x). Therefore z : (g(x), h(x)) is in dom( ). Taking z : (g(x), h(x))

in (9) gives

(g(x), h(x)) ; 1 , g(x)2 ; 1 , h(x)2 . (0) (10)

for all x in RL. Now

(g(x), h(x)) : inf+ f (y) : y + X(g(x), h(x)),,

where X(g(x), h(x)) : +y : g(y) - g(x), h(y) : h(x),. But x + X(g(x), h(x)). Hence

f (x) . (g(x), h(x)).

Substituting this into (10) gives

f (x) ; 1 , g(x)2 ; 1 , h(x)2 . (0)

for all x. Hence

(0) - inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2,.

We now establish the reverse inequality and thus prove the lemma. We have

inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x + RL,

- inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : g(x) - 0, h(x) : 0,.

PERTURBATION THEORY 195

Since . 0, g(x) - 0, and h(x) : 0, the right-hand side of this inequality is less

than or equal to

inf+ f (x) : g(x) - 0, h(x) : 0, : (0).

Remark 3.3. Because of relationships (7) and (9), which bound the change in

from below by a linear function, problems with * (0) " ` are said to be

stable.

The next theorem is an immediate consequence of Lemmas 3.2 and 3.3.

T 3.1. L et the programming problem CPII be strongly consistent and let

(0) be ¬nite. T hen * (0) is nonempty and for every : ( , ) such that

9 + * (0) the vector is nonnegative and

(0) : inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)) : x + RL,.

The next theorem summarizes the relationships among the set * (0), the

multiplier vectors, and the Kuhn”Tucker vectors.

T 3.2. L et the programming problem CPII be strongly consistent and let

it have a solution. T hen the set M of multiplier vectors, the set K of

Kuhn”Tucker vectors, and the set 9* (0) are all nonempty and equal.

Proof. That M and K are nonempty and equal was noted in Corollary 1

of Theorem 2.3 and Remark 2.6. Theorem 3.1 states that if CPII is strongly

consistent and (0) is ¬nite, then * (0) is nonempty and every vector in

9* (0) is a Kuhn”Tucker vector.

To complete the proof of the theorem, we must show that each Kuhn”

Tucker vector is an element of 9* (0). Let : ( , ) be a Kuhn”Tucker

* **

vector. Since CPII is consistent, 0 + dom( ) and hence dom( ) " `. For any

z in dom( )

(0) : inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x in RL,

* *

- inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x + X(z),.

*

*

Since g(x) - z and h(x) : z for x in X(z) and since . 0, we get that

*

(0) - inf+ f (x) ; 1

, z 2 ; 1 , z 2 : x + X(z),

* *

: (z) ; 1 , z 2 ; 1 , z 2.

* *

Hence

(z) . (0) 9 1 , z 291 , z 2

* *

for all z in dom( ). Thus + 9* (0).

*

196 CONVEX PROGRAMMING AND DUALITY

The assumption of strong consistency in Theorem 3.2, as already noted,

guarantees that the sets M and 9* (0) are nonempty. In any speci¬c problem,

the validity of the strong consistency assumption is easily veri¬ed a priori from

the data of the problem. In the next theorem we show that if we drop the

assumption of strong consistency but assume that one of the sets K, M, or

9* (0) is nonempty, then all of the sets are nonempty and are equal. This

assumption, however, is not veri¬able a priori.

T 3.3. L et the programming problem CPII have a solution. L et one of the

sets 9* (0), the set K of Kuhn”Tucker multipliers, or the set M of multipliers

as in T heorem 2.2 be nonempty. T hen all of the sets M, K and 9* (0) are

,

nonempty and

M : K : 9* (0).

Proof. By Corollary 1 to Theorem 2.3, the sets M and K are equal. By

Lemma 3.3, if * (0) is not empty, then 9* (0) 3 K. Of course, if * (0) : `,

this is also true. In proving Theorem 3.2, we showed that K 3 9* (0). Thus,

K : 9* (0), and the theorem is proved.

Remark 3.4. The relationship between perturbations and multiplier vectors

has an interesting economic interpretation. We can consider the function f as

giving the cost of an activity described by a vector x, where x is subject to

constraints g(x) - 0 and h(x) : 0. Our objective is to minimize f subject to the

constraints. We perturb the constraints by a vector z : (z , z ) in the hope of

reducing the optimal cost (z). If we must pay a price : ( , ) per unit

change in the constraints, then the total cost of the perturbed process with

constraints g(x) - z and h(x) : z is

(z) ; 1 , z2.

Thus it will be advantageous to purchase a change in the constraints if and

only if

(z) ; 1 , z2 : (0).

But

(z) . (0) 9 1 , z 2 9 1 , z 2, ( , ) + M, (z , z ) + RK>I,

and so

(z) ; 1 , z 2 ; ( , z ) . (0).

Also, any ( , ) for which the last inequality holds is in 9* (0), and so is in

PERTURBATION THEORY 197

M. Thus we can consider a multiplier vector ( , ) to be a price such that the

purchase of a perturbation at that price will not result in a lowering of the cost.

Since at these prices no perturbation is worth buying, We may consider the

cost to be at equilibrium at these prices. Therefore, such prices are called

equilibrium prices.

We now illustrate the results of this section by several examples.

Example 3.1. Minimize

f (x) : e\ V>V‚

subject to

eV ; eV‚ 9 20 - z.

This problem is a perturbation of the problem in Exercise IV.5.5. Since f

and the constraint function g(x) : eV ; eV‚ 9 20 are convex, the nonperturbed

problem is a convex programming problem, as are the perturbed problems.

The problem is strongly consistent since g(0) : 20.

Let

L (x, , z) : e\ V>V‚ ; (eV ; eV‚ 9 20 9 z).

It follows from Theorem 2.5 that a solution : ( , ) is characterized by the

existence of a positive number such that (g( ) 9 z) : 0 and *L /*x :

*L /*x : 0, where the partial derivatives are evaluated at ( , ). Thus

9e\ K>K‚ ; eK : 0, 9e\ K>K‚ ; eK‚ : 0. (11)

From this it follows that " 0 and that

eK : eK‚.

: . From " 0 and (g( ) 9 z) : 0 it follows that

Hence

eK ; eK‚ : 20 ; z.

Let denote the common value of and . Then

2eK : 20 ; z, (12)

and so : ln(10 ; z). It follows from (11) and (12) that

: e\K : (10 ; z)\. (13)

198 CONVEX PROGRAMMING AND DUALITY

It also follows from (12) and from the relation f ( ) : eK that

(z) : e\K : (10 ; z)\.

Hence

(z) : 9(10 ; z)\.

From (13) we get that the value of the multiplier for the unperturbed

*

problem is 10\. Also, (0) : 910\ and so (0) : 9 , in agreement with

*

the theory.

We now show that the solution of the constrained problem can be obtained

by solving the unconstrained problem of minimizing F(x), where

F(x) : e\ V>V‚) ; (eV ; eV‚ 9 20).

*

Substituting the value of in the preceding expression gives

*

F(x) : e\ V>V‚ ; 10\(eV ; eV‚ 9 20).

Since F is convex, any critical point furnishes a minimum. Setting *F/*x and

*F/*x equal to zero gives

9e\ V>V‚ ; 10\eV : 0, 9e\ V>V‚ ; 10\eV‚ : 0.

Hence x : x . Setting x : x : x gives

eV : 10e\V,