<<

. 43
( 59 .)



>>

G G G G G
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,

<<

. 43
( 59 .)



>>