i : k ; 1, . . . , n.

arbitrary,

Since F is convex, it follows from the corollary to Theorem IV.3.2 that F

attains a minimum at any such point y . If Q is positive de¬nite, then k : n

and the point y is unique. We summarize this discussion in the following

lemma.

L 6.1. T he unconstrained programming problem either has in¬mum equal to

9- or attains a minimum at a ¬nite point.

We return to the determination of the explicit form of the dual problem. For

¬xed .0, the problem of minimizing L (x, 2 over all x in RL is an uncon-

strained quadratic programming problem, since

L (x, ) : 1x, Qx2 9 1b, x2 ; 1 , Ax 9 c2

: 1x, Qx2 9 1b 9 AR , x2 9 1 , c2

: 1x, Qx2 9 1d, x2 9 1 , c2,

where d : b 9 AR . It then follows from Lemma 6.1 that if ( ) is ¬nite, then

we may replace the in¬mum in (7) by a minimum. Thus, for ¬xed such that

214 CONVEX PROGRAMMING AND DUALITY

( ) 9 9-, if we denote a point at which min L ( ·, ) is attained by x , then

( ) : L (x , ) : 1x , Qx 2 9 1b, x 2 ; 1 , Ax 9 c2. (9)

the function L ( ·, ) is convex on RL, it follows from the

Since for ¬xed

corollary to Theorem IV.3.2 that the minimum is attained at a point x if and

only if

x L (x , ) : 0. A straightforward calculation shows that

x L (x , ) : 0

if and only if

Qx 9 b ; AR : 0. (10)

If we take the inner product of each side of (10) with x , we get

1x , Qx 2 9 1b, x 2 ; 1 , Ax 2 : 0.

Substitution of this equation into (9) gives

( ) : 91x , Qx 2 9 1 , c2.

Thus the explicit formulation of the dual problem is as follows.

Dual Quadratic Programming Problem (DQP)

Maximize

91x, Qx2 9 1 , c2 (11)

subject to

Qx ; AR : b, . 0. (12)

If Q is positive de¬nite, then the dual problem can be simpli¬ed. From (12)

we get that

x : Q\(b 9 AR ). (13)

If we substitute this into (11), then a straightforward calculation, using the fact

that Q\ is symmetric, gives

( ) : 91 , R 2 ; (d, 2 ; a, (14)

where

a : 91b, Q\b2.

R : AQ\AR, d : bRQ\AR 9 c,

DUALITY IN LINEAR PROGRAMMING 215

Thus the dual problem becomes the following: Maximize ( ) subject to . 0,

where ( ) is given by (14).

This problem is a quadratic programming problem whose constraint set has

a simple structure, namely + : + RL, . 0,. By Theorem 6.2 there is no

duality gap and this problem has a solution , where is a multiplier as in

* *

Theorem 6.1. Thus, from (3) we get that the solution of QP is

x : Q\(b 9 AR ).

* *

Exercise 6.1. Show that if Q is positive de¬nite, then the quadratic program-

ming problem has a unique solution. Does your proof apply to the uncon-

strained problem?

Exercise 6.2. The problems posed in Exercise IV.5.8 and Exercise 3.2(iii) are

quadratic programming problems. Use the duality developed in this section to

solve these problems. Compare with the duality in Exercises 4.1 and 4.2.

7. DUALITY IN LINEAR PROGRAMMING

The linear programming problem LPI formulated in Section 1 in Chapter IV

can be viewed as a convex programming problem with f (x) : 19b, x2 and

g(x) : Ax 9 c. Thus all of the results of this chapter hold for the linear pro-

gramming problem. The linear nature of LPI, however, results in a much

stronger duality than that of Theorem 4.1. We proceed to determine this

duality.

To maintain a symmetry in the duality, we shall not incorporate the

constraint x . 0 in the matrix A and the vector c, as was done in Chapter IV,

but shall write our primal problem (P) as

A c

Minimize 19b, x2 subject to x- (P)

,

9I 0

L L

where I is the n ; n identity matrix and 0 is the zero vector in RL.

L L

We now formulate the dual problem. Let : ( , ), where + RK, . 0,

+ RL, . 0. Let

( ) : inf+19b, x2 ; 1 , Ax 9 c2 9 1 , x2 : x + RL,

: inf+1(9b 9 ; AR ), x2 9 1 , c2 : x + RL,.

The expression inside the curly braces is linear in x. Therefore, for it to have a

¬nite in¬mum over all x in RL, the coef¬cient of each component of x must be

zero, and so

AR 9 b 9 : 0. (1)

216 CONVEX PROGRAMMING AND DUALITY

. 0, equation (1) is equivalent to

Since

AR 9 b . 0.

If (1) holds, then ( ) : 19c, 2. Thus the problem dual to P is

AR b

Maximize 19c, 2 subject to . (D)

,

I 0

K K

where I is the m ; m identity matrix and 0 is the zero vector in RK.

K K

The dual problem (D) can be written as a linear programming problem:

9AR 9b

Minimize 19(9c), 2 subject to - .

9I 0

K K

The dual of this problem is

9A 9c

Maximize 1b, y2 subject to y. .

I 0

L L

If we write this problem as a minimization problem and relabel the vector

y + RL as x, we see that the dual of the dual problem is the primal problem. We

summarize this discussion in the following lemma.

L 7.1. T he dual of the linear programming problem

A c

Minimize 19b, x2 subject to x- (P)

9I 0

L L

is

AR b

Maximize 19c, 2 subject to . (D)

.

I 0

K K

T he dual of the dual problem (D) is the primal problem (P).

T 7.1 (Dµ¬© T ¦ L©® P§©®§). L et X denote the

feasible set for the primal problem and let Y denote the feasible set for the dual

problem. T hen:

(i) For each x in X and in Y,

19c, 2 - 19b, x2 (weak duality)

DUALITY IN LINEAR PROGRAMMING 217

(ii) L et Y be nonempty. T hen X is empty if and only if 19c, 2 is unbounded

above on Y.

(iii) L et X be nonempty. T hen Y is empty if and only if 19b, x2 is bounded

below on X.

(iv) (Strong duality). L et the primal problem (P) have a solution x . T hen the

*

dual problem (D) has a solution and 1c, 2 : 1b, x 2.

* * *

Remark 7.1. Since problem P is also a convex programming problem, all of

the conclusions of Theorem 4.1 apply to the linear programming problem.

Thus, (i) is a special case of (i) of Theorem 4.1. In (ii) the statement that if

19c, 2 is unbounded above then X is empty is a special case of (ii) of

Theorem 4.1. In the linear programming problem the stronger ˜˜if and only if™™

statement holds. Analogous comments hold for (iii).

Also note that the phenomenon exhibited in Example 4.3 in which there is

no duality gap, yet the dual problem has no solution, cannot occur.

We now prove the theorem. We pointed out in Remark 7.1 that (i) follows

from (i) of Theorem 4.1.

From the discussion of (ii) in Remark 7.1 it follows that to establish (ii) we

must show that if X is empty then 19c, 2 is unbounded above. We ¬rst note

that if X is empty, then we must have c " 0. For if c : 0, then x : 0 would be

feasible and X would be nonempty.

If X is empty, then the system

A c

x-

9I 0

L L

has no solution. It then follows from Theorem II.5.4 that if X is empty, then

there exists a vector y : (y , y ), where y + RK, y . 0, y + RL, y . 0, such

that

y

(AR, 9I ) : (0 , 0 ).

1(c, 0 ), (y , y )2 : 91, (2)

L Ly KL

Hence (2) becomes

1c, y 2 : 91, ARy : 0 , y .0 .

K K

Since Y "`, there exists a . 0 such that AR . b. Then for any real 9 0,

the vector ; y is in Y and

19c, ; y 2 : 19c, 2 ; .

can be taken to be arbitrarily large, 19c, 2 is unbounded above.

Thus, since

218 CONVEX PROGRAMMING AND DUALITY

We view the primal problem as the dual to the dual and view the dual

problem as primal. Then from (ii) we conclude that if X is nonempty, then Y

is empty if and only if 1b, x2 is unbounded above, or equivalently that 19b, x2

is unbounded below. Thus, (iii) is proved.

We now take up the proof of (iv). Since the primal problem has a solution,

there exists a vector in RK as in Theorem IV.4.1. It is readily seen that this

vector is a multiplier as in the KKT conditions of Theorem IV.5.2. The set M

is thus nonempty. The absence of a duality gap and the existence of a solution

follow from Corollary 1 to Theorem 4.4. Since there is no duality gap and both

the primal and dual have a solution, 19c, 2 : 19b, x 2.

* *

C¬¬ 1. A necessary and suf¬cient condition that a point x in X and a

*

point in Y be solutions of the primal and dual problems respectively is that

*

1b, x 2 : 1c, 2.

* *

Proof. The necessity of the condition follow from (iv) of Theorem 7.1 and

the suf¬ciency from (iv) of Theorem 4.1.

C¬¬ 2. Necessary and suf¬cient conditions that a point x in X and a

*

point in Y be solutions of the primal and dual problems respectively are

*

(i) 1Ax 9 c, 2 : 0 and

* *

(ii) 1AR 9 b, x 2 : 0.

* *