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