<<

. 42
( 59 .)



>>

not known precisely but are known to lie in certain ranges of values. Thus one
might assign a value to the parameters and then study the effect of perturbing
the parameters. We shall assume that this is modeled by perturbing the
constraints and shall study the effect of perturbations on the value of the
in¬mum of the problem. Given the uncertainty in the parameter values, one
would hope for a certain stability of the problem in the sense that small
perturbations in the constraints will not lead to large changes in the value of
the in¬mum. We shall show that if the unperturbed convex programming
problem is strongly consistent and has a solution, then the change in the value
of the in¬mum is bounded below by a linear function of the perturbations. In
the preceding section we showed that under reasonable assumptions the set M
of multipliers and the set K of Kuhn”Tucker vectors are nonempty and equal.
In this section we shall show that the vectors in K and M are the coef¬cient
vectors of the aforementioned linear function of the perturbations. Moreover,
the sets K and M are the negative subdifferential of the in¬mum as a function
of the perturbation, evaluated at the unperturbed value. Thus, in a sense, the
multipliers measure the rate of change of the value of the in¬mum as we
perturb the constraints. We shall also give an economic interpretation of the
multipliers. These statements will be made precise in this section.
PERTURBATION THEORY 189


Throughout this section we assume that the problem CPII is consistent, that
is, it has a nonempty feasible set. For each z : (z , z ) with z + RK and z + RI
  
we de¬ne a perturbed programming problem CPII(z) as follows.
Problem CPII(z)
Minimize f (x) subject to x in X(z), where
X(z) : +x : g(x) - z , h(x) : z ,,
 
the function f is a convex function from RL to R, the function g is a convex
function from RL to RK, and the function h is an af¬ne function from RL to RI.

The constraint set X(z) can also be described by
X(z) : +x : g(x) 9 z - 0, h(x) 9 z : 0,.
 
For each ¬xed z the function g(x) 9 z is convex and the function h(x) 9 z is
 
af¬ne. Thus, each problem CPII (z) is a convex programming problem. Note
that the problem CPII is the problem CPII(0).
For each z in RK>I the feasible set X(z) is either empty or convex. For each
z such that X(z) " `, let
(z) : inf+ f (x) : x + X(z),.
Thus we have a function whose domain is the set of z such that X(z) is not
empty and which can assume the value 9-. We shall designate the domain
of by dom( ) and shall call the value function of the family of perturbed
problems CPII(z), or simply the value function. For z in dom( ) we shall call
(z) the value of CPII(z). We shall denote the in¬mum of the unperturbed
problem CPII by . Thus
: inf + f (x) : g(x) - 0, h(x) : 0,,
so : (0).
Since (z) : 9- is possible, we shall adjoin 9- to the reals R. Although
we shall not need to do so in this section, we shall also adjoin ;- to R. To
work with 9- and ;- in a consistent way, we de¬ne the following
operations:
(;-) ; (;-) : ;-,
(9-) ; (9-) : 9-,
(9-) ; x : 9-, x real,
x(9-) : 9-, x real x 9 0,
x(9-) : ;-, x real x : 0,
9- : x : ;-, x real.

The operation (9-) ; (;-) is not de¬ned.
190 CONVEX PROGRAMMING AND DUALITY


For functions f de¬ned on a convex set C and taking on either real values
or the value of 9-, the de¬nition of convexity is unchanged. Namely, f is said
to be convex on C if for every x , x in C and every ( , ) in P
 
f ( x ; x ) - f (x ) ; f (x ),
   
where the values of 9- are to be operated on as in (1). As in Chapter 3, an
equivalent de¬nition of f convex is that the set

epi( f ) : +(x, y) : x + C, y + R, y . f (x),

is convex.

L 3.1. T he domain of the value function is a convex set and is a convex
function on dom( ). If the problem CPII is strongly consistent, then 0 is an
interior point of dom( ).
Proof. We ¬rst show that dom( ) is a convex set. We shall suppose that the
af¬ne equality constraints have been written as pairs of inequality constraints.
Since we assume that CPII is consistent, 0 is in dom( ) and thus dom( ) " `.
We must show that if w and w are two points in dom( ), then so is
 
w ; w for all ( , ) in P . Since w and w are in dom( ), there exist points
    
x and x in RL such that
 
g(x ) - w and g(x ) - w .
   
Since g is convex, for any ( , ) in P

g( x ; x ) - g(x ) ; g(x ) - w ; w .
     
Thus, x ; x is in X( w ; w ) and w ; w is in dom( ).
     
To show that is convex, again let w and w be two points in dom( ) and
 
let ( , ) be in P . Let x + X(w ) and let x + X(w ). Then as in the preceding
    
paragraph x ; x is in X( w ; w ). Hence
   
( w ; w ) : inf+ f (x) : g(x) - w ; w ),
   
- inf+ f (x) : x : x ; x , g(x ) - w , g(x ) - w ,
     
: inf+ f ( x ; x ) : x + X(w ), x + X(w ),.
   
- inf+ f (x ) ; f (x ) : x + X(w ), x + X(w ),. (1)
   
D  
If (w ) and (w ) are both ¬nite, then by Exercise I.6.4 the rightmost
 
expression in (1) is equal to

inf+ f (x ) : x + X(w ), ; inf+ f (x ) : x + X(w ), : (w ) ; (w ).
     
PERTURBATION THEORY 191


If either (w ): 9 - or (w ) : 9-, then the rightmost expression in (1) is
 
equal to 9-. Thus,

( w ; w )- (w ) ; (w ), (2)
   
and the convexity of is established.
We now suppose that the problem CPII is strongly consistent and shall
show that 0 is an interior point of dom( ). We shall not incorporate the af¬ne
equality constraints into the inequality constraints. Recall that we are writing
the vector z which is the perturbation of the constraints as z : (z , z ), where

z + RK is the perturbation of the inequality constraints and z + RI is the
 
perturbation of the equality constraints.
Since CPII is strongly consistent, there exists an x such that

g(x ) : 0 and h(x ) : 0. (3)
 
Let z : (z , . . . , z ). For each i : 1, . . . , m, the function G de¬ned on RL;R
  K G
by

G (x, z ) : g (x) 9 z
G G G G
is continuous. This holds because G is convex and a convex function is
G
continuous on the interior of its domain of de¬nition, which in this case is
RL;R. From (3) we get that G (x , 0) : 0. Hence, by the continuity of G , there
G G
exist a 9 0 and a 9 0 such that whenever "z " : and #x 9 x # :
G G G  G
g (x) 9 z : 0.
G G
: min+ : i : 1, . . . , m, and let : min+ , . . . , ,. Then
Let
 G   K
g(x) : z (4)

when #z # : and #x 9 x # : .
   
We now consider the perturbed equality constraints, which in accordance
with (1.2) we write as

Ax : b ; z . (5)

Recall that in Remark 1.1 we assumed that A has rank k. We assume that the
square matrix A consisting of the ¬rst k columns of A is nonsingular. There
I
is no loss of generality in this assumption since we can relabel the components
to achieve this. Let A be the matrix consisting of the last n 9 k columns of
L\I
A. Let x : (x , x ), where x is the vector consisting of the ¬rst k components
I L\I I
is the vector consisting of the last n 9 k components of x. Then
of x and x
L\I
192 CONVEX PROGRAMMING AND DUALITY


we may write (5) as

A x ;A x :b;z .
II L\I L\I 
From this equation and the equation Ax : b we get that

(x 9 x ) : A\[9A (x 9 x ) ; z ], (6)
I
I  I L\I L\I  L\I 
where x : (x , . . . , x ) and x : (x , . . . , x ). It follows from
 I    I  L\I  I>  L
#:
(6) that there exist a  9 0 and a 0 : : such that if #x 9 x

 L\I  L\I
and #z # : , then #x 9 x # :  . Since for any x we have #x# :

 I  I
#x # ; #x #, it follows that for every vector x satisfying
I L\I L\I
 and for every vector z satisfying #z # :  the vector
#x 9 x #:

L\I  L\I  
x : (x , x ), where x is given by (6), is such that #x 9 x # : /(2 and (5)
I L\I I  
is satis¬ed. The last statement together with (4) show that for every z : (z , z )

with #z# : min( , ) there exists a vector xz that is feasible. Thus 0 is an

interior point of dom( ).

Lemma 3.1 guarantees that dom ( ) is a convex set and is a convex
function. It also guarantees that if CPII is strongly consistent, dom( ) has
nonempty interior. There is no guarantee, however, that in general dom( ) will
have a nonempty interior. To state two important corollaries to Lemma 3.1, it
will therefore be necessary to consider the notions of relative interior and
relative boundary, which were introduced in Section 7 of Chapter II.

C¬¬ 1. If (w ) : 9- at some point w in dom( ), then (z) : 9-
 
at all points of dom( ) with the possible exception of relative boundary points.
Proof. It follows from (2) that if (w ) : 9- at some point w in dom( ),
 
then (z) : 9- at all points of the half open line segment [w , w ), where

w " w is another point of dom( ).
 
Let w be a point of dom( ) that is not a relative boundary point. Then w
 
is a relative interior point of dom( ). Hence the line segment [w , w ], which

lies in dom( ), can be extended to a line segment [w , w ] that lies in dom( ).

The point w is interior to [w , w ], and so (w ) : 9-.
  
C¬¬ 2. If is ¬nite at a relative interior point of its domain, then is
¬nite over its entire domain.

This follows from Corollary 1, for if were not ¬nite at some point, it would
have to be in¬nite at all relative interior points of its domain.

Remark 3.1. The only property of that was used in the proof of Corollary 1
was the convexity of . Thus Corollaries 1 and 2 are valid for all convex
functions admitting 9- as a value.
PERTURBATION THEORY 193


L 3.2. L et problem CPII be strongly consistent and let Y (0) be ¬nite.
T hen is ¬nite on dom( ), the subdifferential * (0) " ` and each in 9* (0)
can be written as : ( , ), where + RK, . 0, + RI and such that for all
z : (z , z ) in dom( )

(z) . (0) 9 1 , z2 : (0) 9 1 , z 2 9 1 , z 2. (7)
 
Proof. It follows from Lemma 3.1 that 0 is an interior point of dom( ) and
that is a convex function on the convex set dom( ). Since (0) is ¬nite, it
follows from Corollary 2 to Lemma 3.1 that is ¬nite at all points of dom( ).
Therefore, by Theorem III.2.1, the set of subgradients of at 0 is not empty.
Relation (7) then follows by taking : 9 , where is any element in * (0).
We now show that . 0. Since the problem is consistent, +x : g(x) - 0,
h(x) : 0, is nonempty. Hence the set X(z) is nonempty for any vector
z : (z , z ) with z . 0 and z : 0. Thus, all such vectors are in dom( ).
  
If were not nonnegative, then at least one component of , say , would
G
be negative. Let z : (z , 0 ) where z : e , the vector in RK all of whose

<<

. 42
( 59 .)



>>