<<

. 47
( 59 .)



>>

G
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.
* *

<<

. 47
( 59 .)



>>