Then for each . 0 de¬ne

( ) : inf+L (x, ) : x + R,.

The dual problem is to maximize ( ).

We saw in Example 3.1 that the primal problem is strongly consistent and

that it has a solution at x : ( , ), where : ln 10. The value of the minimum

*

is 10\ and the value of the multiplier is 10\. Thus we would expect the

*

value of the maximum of to be 10\ and for to assume this value at

: 10\. We now show that this is indeed so.

We ¬rst determine the function . For each . 0, the function L ( , ) is

readily seen to be a strictly convex function of x. Hence a necessary and

suf¬cient condition that L ( , ) attain a unique minimum at : ( , ) is that

*L /*x and *L /*x both equal zero at . As in Example 3.1 we see that for

" 0 this implies that : . Denoting this common value by , we get that

( ) : inf+

( , ) : + R,, (9)

where

( , ) : e\K ; 2 (eK 9 10).

For ¬xed positive ,

( , ) is a strictly convex function of . A necessary and

suf¬cient condition that

( , ) attain a unique minimum at a point is that

204 CONVEX PROGRAMMING AND DUALITY

d

/d vanish at . Now

d

: 92e\K ; 2 eK.

d

Setting d

/d : 0, we get that exp(9 ) : . Substituting this into (9) gives

( ) : 3 9 20 , 9 0.

Since ( ) : 0 when : 0, the preceding formula is valid for all . 0. An

elementary calculus argument shows that is maximized at the unique point

at which ( ) : 0. This value of is readily seen to be 10\ and the

corresponding value of is 10\. These values are as required.

Example 4.2. Let the primal problem be as follows: Minimize #x# subject to

x ; x - 0. This problem was analyzed in Example 3.2 with z : 0. This

problem is strongly consistent and has x : 0 as its solution. The value of the

minimum is clearly zero. Any in the interval [0, 1/(2] is a multiplier vector.

The dual problem is as follows: Maximize + ( ) : . 0, ( ) 9 9-,, where

( ) : inf+#x#; (x ; x) : x + R,. We introduce polar coordinates (r,

) and

obtain

( ) : inf+r(1 ; (cos

; sin

)) : r . 0, 0 -

- 2 ,.

Let

(

, ) : 1 ; (cos

; sin

).

Then ( ) : 0 if (

, ) . 0 for all 0 -

- 2 , and ( ) : 9- if this is not so

and r " 0. The argument used in Example 3.2 shows that (

, ) . 0 for all

in [0, 2 ] if and only if 0 - - 1/(2. Thus ( ) : 0 for in [0, 1/(2] and

( ):9- otherwise. Hence max+ ( ) : + Y ,:0 and the maximum is attained

at each + [0, 1/(2]. Comparison with the solution to the primal problem

shows that there is no duality gap and the points at which the dual problem

attains its maximum are the multipliers for the primal problem.

Example 4.3. Let the primal problem be the problem treated in Example 2.1

and in Example 3.3 with z : 0. The primal problem has the origin as the only

feasible point. This point furnishes the solution and the value of the minimum

is zero. This problem is clearly not strongly consistent.

The dual problem is as follows: Maximize + ( ) : + Y ,, where

( ) : inf(x ; x ; (x 9 x) : x + R,.

Y : + : . 0, ( ) 9 9-, and

LAGRANGIAN DUALITY 205

If we write

x ; x ; (x 9 x ) : x ; x ; ( 9 )x ,

" , then ( ) : 9-. For " 0 with :

we see that if , we have

" 0 and

( ) : inf+x ; x : x + R,.

The function inside the curly brackets attains its minimum at x : 91/2 and

( ) : 91/4 . (10)

: 0 we have

For

(0) : 9-.

Thus Y : + : ( , ) : : , 9 0,. Since 9 0, it follows from (10) that

sup+ ( ) : + Y , : 0. The supremum is not attained in the dual problem, even

though there is no duality gap. Thus we have an example in which there is no

duality gap; the primal problem has a solution but the dual problem has no

solution. We also recall from Example 3.3 that * (0) :

and there are no

Kuhn”Tucker vectors.

Example 4.4. In this example we will exhibit a duality gap. Let the primal

problem be the problem in Example 3.4 with z : 0. We saw there that the

minimum is attained at every point of the feasible set and that the value of the

minimum is 1.

The dual problem is to maximize + ( ) : . 0, ( ) 9 9-,, where

( ) : inf+e\V‚ ; ((x ; x 9 x) : x + R,.

Let

L (x, ) : e\V‚ ; ((x ; x 9 x ).

Then L (x, ) . 0 for all x in R. We shall show that ( ) : 0.

Let x 9 0 and let x 9 0. Then

x

L (x, ) : e\V‚ ;

(x ; x ; x

x

: e\V‚ ; .

x

1; ;1

x

x

206 CONVEX PROGRAMMING AND DUALITY

Now let x : (x ) and then let x ; -. We see that L (x, ) ; 0 along this

curve. Thus ( ) : 0 for all . 0 and max+ ( ) : . 0, : 0. Thus : 0, and

since : 1, we have a duality gap.

Theorem 4.2 states that if a solution to the primal problem exists, then

strong consistency is a suf¬cient condition for the absence of a duality gap and

the existence of a solution to the dual problem. The following example shows

that strong consistency is not a necessary condition for the absence of a duality

gap and for the existence of a solution to the dual problem.

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

g (x) : (x ; 1) ; (x ) 9 1 - 0, g (x) : 9x - 0.

The problem is clearly a convex programming problem. The feasible set

consists of the origin 0 in R, and the problem is not strongly consistent. The

solution to the primal problem is x : 0 and : 0.

*

The dual objective function is given by

( ) : inf+x ; [(x ; 1) ; (x ) 9 1] 9 x : x + R,,

where . 0. If we take : : (0, 1) we get that ( ) : 0. If then follows

* *

from (iv) of Theorem 4.1 that there is no duality gap and that is a solution

*

of the dual problem.

We will now obtain two necessary and suf¬cient conditions for the absence

of a duality gap and the existence of a solution to the dual problem.

T 4.3. L et problem CPII have a solution x . T hen a necessary and

*

suf¬cient condition for the absence of a duality gap and for : ( , ), . 0,

***

*

to be a solution of the dual problem is that (x , , ) is a saddle point for L .

***

Proof. Let (x , , ) be a saddle point for L . Then (2.18i) and (2.19) of

***

Theorem 2.7 hold. Thus (8) of Theorem 4.2 holds. That there is no duality gap

and that ( , ) is a solution to the dual problem follows by the same

**

arguments used to establish (i) and (ii) in Theorem 4.2.

: ( , ) be a solution of the dual problem and let there be no

Now let

* **

duality gap. Then, as in the proof of statement (iii) in Theorem 4.2 with

: and : , we get that ( , ) is a multiplier as in Theorem 2.2 for

**

* *

the primal problem. But (7) of Theorem 2.2 states that (x , , ) is a saddle

***

point for L .

T 4.4. L et CPII have a solution x . T hen a necessary and suf¬cient

*

condition for the absence of a duality gap and the existence of a solution to the

dual problem is that * (0) " `. In this event every vector in 9* (0) is a

solution of the dual problem.

GEOMETRIC INTERPRETATION 207

Proof. We ¬rst prove the suf¬ciency of the condition * (0) " `. Since the

primal problem has a solution, (0) is ¬nite. By hypothesis, * (0) " `. Hence

by Lemma 3.3 each vector : ( , ) such that 9 + * (0) is a Kuhn”Tucker

vector, and such vectors exist. By Theorem 3.3 each such vector is in M, the

set of multiplier vectors, as in Theorem 2.2. Thus (x , , ) is a saddle point

*

for L , and so by Theorem 4.3 there is no duality gap and ( , ) is a solution

to the dual problem. Now suppose that there is no duality gap and that the

: ( , ). Then by Theorem 4.3 the point

dual problem has a solution

* **

(x , , ) is a saddle point for L . By Theorem 2.7, ( , ) is a Kuhn”Tucker

*** **

vector. It then follows from Theorem 3.3 that ( , ) + 9* (0).

**

C¬¬ 1. L et CPII have a solution x . T hen a necessary and suf¬cient

*

condition for the absence of a duality gap and the existence of a solution to the

dual problem is that one of the sets * (0), K, or M be nonempty.

The corollary is an immediate consequence of Theorems 4.4 and 3.3.

Remark 4.1. In Remark 3.4 we indicated an economic interpretation of the

multiplier vectors as equilibrium prices. In view of the preceding corollary, we

see that the solution of the dual problem gives the equilibrium price.

Exercise 4.1. Formulate, and solve whenever possible, the problems dual to the

problems in Exercise 3.2. Discuss your results as they relate to Theorem 4.2.

Exercise 4.2. The problem posed in Exercise IV.5.8 is a convex programming

problem. Solve this problem by formulating the dual and solving the dual.

Hint: To simplify the algebra involved, ¬rst solve the problem for x : 0. Then

use a translation of coordinates to obtain the result for general x .

Exercise 4.3. Show that the function de¬ned by (2.2) is concave.

5. GEOMETRIC INTERPRETATION