whence x : ln 10. This is in agreement with the solution of the constrained

problem given by (12) with z : 0.

Example 3.2. Find the point in the half space de¬ned by x ; x - z that is

closest to the origin. This problem has a solution. (Why?)

We may formulate this problem analytically as follows: Minimize #x#

subject to x ; x - z. Thus the problem is a problem of type CPII(z). If we

take z : 0, we see that CPII is strongly consistent. On sketching the feasible

sets for z . 0, it becomes clear that for z . 0 the solution is the origin and that

(z) : 0. For z : 0 the minimum is the point of intersection of the line x : x

and the line x ; x : z. Thus the minimum is achieved at (z, z) and

(z) : z for z : 0. The function is differentiable at all points and (0) : 0.

Therefore 0 is the unique Kuhn”Tucker vector, and the constrained problem

CPII can be replaced by the problem of minimizing #x#. The conditions of

Theorem 2.5 are clearly satis¬ed if we take x : (0, 0) and : 0.

* *

PERTURBATION THEORY 199

We may also formulate the problem analytically as follows: Minimize #x#

subject to x ; x - z. Again, the solution is the origin if z . 0 and the point

(z, z) if z : 0. The function is now given by (z) : 0 for z . 0 and

(z) : 9z/(2 for z : 0. Thus, is not differentiable at the origin. It is a

straightforward calculation to show that * (0) is the interval [91/(2, 0].

Hence by Theorem 3.2 the Kuhn”Tucker vectors and multiplier vectors are all

points in the interval [0, 1/(2]. We now verify this assertion independently.

For to be a Kuhn”Tucker vector, we must have

inf+#x# ; (x ; x ), : 0.

When x : 0, the quantity in brackets is clearly zero. Therefore, for to be a

Kuhn”Tucker vector, we require that . 0 and

(x ; x ; (x ; x ) . 0 for all x + RL.

To see what requirement this places on , we introduce polar coordinates. The

preceding inequality is then satis¬ed at the origin and whenever

(cos ; sin ) . 91, 0- -2 . (14)

The function ( ) : cos ; sin achieve its minimum on the interval [0, 2 ]

at : 5 /4 and the value of the minimum is 9(2. Hence we must have

- 1/(2 as well as . 0.

We can replace the constrained problem by the unconstrained problem.

min+#x# ; (x ; x ),,

where is any point in [0, 1/(2]. The preferred choice of is clearly : 0.

We leave it to the reader to verify that any in [0, 1/(2] will serve as a

multiplier as in Theorem 2.2.

*

Example 3.2 furnishes another illustration of the advantage of minimizing

the square of the distance rather than the distance itself.

Example 3.3. Minimize f (x) : x subject to

g (x) : x 9 x - z .

g (x) : x - z ,

When z : 0, the problem reduces to the problem considered in Example 2.1.

We saw there that when z : 0, there exists no Kuhn”Tucker vector. By draw-

ing an appropriate ¬gure, the reader can see that dom( ) : +z : z ; z . 0,

and that (z) :9(z ; z . We leave the proof of this assertion as an exercise.

Thus neither 0 nor any point on the line z ; z : 0 are interior to dom( ).

It is easy to verify that * (z) : ` at each z on the boundary of dom( ).

200 CONVEX PROGRAMMING AND DUALITY

The next example has discontinuous value function at the origin.

Example 3.4. Minimize e\V‚ subject to (x ; x 9 x - z. For z : 0, the

feasible set is +x : (x , x ) : x . 0, x : 0,. The minimum is attained at each

point of the feasible set since e\V‚ : e\ : 1. Hence (0) : 1. If z : 0, the

feasible set X(z) is empty. If z 9 0, points x of the feasible set satisfy

x - 2x z ; z.

Thus the feasible set is the set of points on and ˜˜inside™™ the parabola x :

2x z ; z. This parabola is symmetric with respect to the x -axis, has vertex

at (9 z, 0), and opens to the right. Hence inf+e\V‚ : x + X(z), : 0, and so

(z) : 0 for z 9 0. Thus, dom( ) : [0, -), and is discontinuous at z : 0.

Also, * (0) : `. Note that if z 9 0, then the in¬mum is never attained at any

point of X(z). Thus the problem CP(z) has no solution if z 9 0.

Exercise 3.1. Prove the assertions in Example 3.3 that

(i) dom( ) : +z : z ; z . 0,,

(ii) (z) : 9(z ; z , and

(iii) * (z) : ` at each z on the boundary of dom( ).

, dom( ), and * (0) if it

Exercise 3.2. In each of the following problems ¬nd

is not empty:

(i) Minimize e\V subject to 9x - 0.

(ii) Minimize x subject to x ; x : 1.

(iii) Minimize x ; x ; 2x ; 2x subject to x ; x . 2.

(iv) Minimize x subject to e\V 9 x - 0.

Exercise 3.3. Show directly that there are no Kuhn”Tucker vectors for the

problem with z : 0 in Example 3.4.

4. LAGRANGIAN DUALITY

If CPII has a solution and is strongly consistent, then Theorem 2.4 suggests a

method for computing the value of the minimum. Let

Y : + : : ( , ) : + RK, . 0, + RI,, (1)

LAGRANGIAN DUALITY 201

+ Y let

and for each

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

Let

: sup+ ( ) : + Y ,. (3)

Then by Theorem 2.4, : , where

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

A possible procedure for ¬nding x , a point at which the minimum is achieved,

*

is to ¬rst ¬nd all solutions to the equation f (x ) : and then retain those

*

solutions that satisfy the constraints.

This discussion suggests that it might be fruitful to consider the following

problem, which we call the problem dual to CPII, or simply the dual problem,

and denote by DCPII.

Problem DCPII

Let

Y : + : + Y , ( ) 9 9-,, (5)

where Y is de¬ned in (1) and ( ) in (2). Then

Maximize + ( ) : + Y ,.

Note that in formulating the dual problem it is not assumed that CPII has

a solution or is strongly consistent. The set Y is the feasible set for DCPII. If

Y "`, then the dual problem is said to be consistent. The original problem

CPII is often referred to as the primal problem.

The next theorem indicates how the dual problem gives information about

the primal problem and vice-versa.

T 4.1 (L§®§©® Dµ¬© T ¦ C® P§©®§).

(i) If X " ` and Y "`, then for each x + X and +Y

( ) - f (x). (6)

Moreover, if and are as in (3) and (4), then both are ¬nite and - .

(ii) L et Y "`. If ( ) is unbounded above on Y, then X : `.

(iii) L et X " `. If f (x) is unbounded below on X, then Y : `.

(iv) If there exists an + Y and an x in X such that f (x ) : ( ), then

* * * *

: ( ) : f (x ) : .

* *

T hus x is a solution of CPII and is a solution of DCPII.

* *

202 CONVEX PROGRAMMING AND DUALITY

Proof. The key to the proof of the theorem is the observation that since

. 0 for + Y and since g(x) - 0 and h(x) : 0 for x + X, it follows that for

x + X and + Y,

f (x) ; 1 , g(x)2 ; 1 , h(x)2 - f (x). (7)

In (2) we take the in¬mum over all x in RL. This in¬mum is less than the

in¬mum in (2) taken over all x + X. From these observations and from (7) the

inequalities (6) and - follow. Assertion (ii) follows from (6), for if X were

not empty, then ( ) would be bounded above. Also, (iii) follows from (6) by

a similar argument. Statement (iv) follows from the chain

( *) - - - f (x *) : ( *).

We now see how the dual problem gives useful information about the primal

problem and vice-versa. Statement (i) shows how a feasible point for the dual

problem gives a lower bound for the value of the primal problem and how a

feasible point for the primal problem gives an upper bound for the value of the

dual problem. Statement (ii) gives a way of checking whether X : ` in the

absence of more direct checks. Statement (iii) gives a condition under which

the dual problem cannot be formulated.

De¬nition 4.1. Problems CPII and DCPII are said to exhibit a duality gap if

:.

The next theorem gives a suf¬cient condition for the absence of a duality

: ( , ) to the solutions of the dual

gap and relates the multipliers

* **

problem.

T 4.2. L et the primal problem CPII be strongly consistent and have a

solution. T hen:

(i) T here is no duality gap.

(ii) If : ( , ) is a multiplier for CPII, then is a solution of the dual

* ** *

problem.

(iii) If : ( , ) is a solution of the dual problem, then is a multiplier

vector for the primal problem.

Proof. Let x denote the point at which CPII achieves its minimum. Since

*

the problem is strongly consistent by Theorem 2.2, there exists a multiplier

: ( , ) for CPII. Thus,

vector

* **

f (x ) - f (x) ; 1 , g(x)2 ; 1 , h(x)2 (8)

* * *

for all x in RL. Hence, from (2), ( ) . f (x ). By Theorem 4.1, ( ) - f (x ),

* * * *

so ( ) : f (x ). Conclusions (i) and (ii) now follow from (iv) of Theorem 4.1.

* *

LAGRANGIAN DUALITY 203

: ( , ) be a solution of the dual problem. From (2) and from

Now let

the absence of a duality gap we get that

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

*

Thus ( , ) is a Kuhn”Tucker vector, and so by Theorem 2.3, ( , ) is a

multiplier vector for the primal problem.

We now present several examples to illustrate the theory developed in this

section.

Example 4.1. We take the primal problem to be the problem in Exercise IV.5.5

or the problem in Example 3.1 with z : 0. The primal problem is

Minimize f (x) : e\ V>V‚

subject to eV ; eV‚ - 20.

Let