<<

. 46
( 59 .)



>>


In this section we present a geometric interpretation of the duality and
perturbation results. We shall assume that all the constraints are inequality
constraints and that we are considering CPI: Minimize f (x) subject to
g(x) - 0.
The mapping

: f (x), z : g(x),

is a mapping from RL to RK>. We have indicated two image sets,

I : +(z, ), : f (x), z : g(x) : x + RL,, (1)
208 CONVEX PROGRAMMING AND DUALITY




Figure 5.1.



schematically for m:1 as the hatched areas in Figures 5.1 and 5.2. In geometric
terms, to solve CPI, we must ¬nd a point in the intersection of I and the closed
half space z - 0 with smallest coordinate if such a point exists. In Figure 5.1
this is the point M with coordinates (z*, *). In Figure 5.2 this is the point M

 
with coordinates (0, *).

Let . 0. The dual problem is to maximize  ( ), where  is de¬ned in
relation (2) of Section 4. We may therefore also write


 ( ) : inf+ ; 1 , z) : : f (x), z : g(x),
: inf+ : : ; 1 , z2 : (z, ) + I,.
GEOMETRIC INTERPRETATION 209




Figure 5.2.


Thus, for all ( , z) in I

1(9 , 91), (z, )2 - 9  ( ),

and so the hyperplane

1(9 , 91), (z, )2 : 9  ( ) (2)

is a supporting hyperplane for the set I. The equation of this hyperplane can
also be written as

: 19 , z2 ;  ( ). (3)

Hence  ( ) is the -intercept of the hyperplane (2). See Figures 5.1 and 5.2. The
210 CONVEX PROGRAMMING AND DUALITY


geometric interpretation of the dual problem is to ¬nd, among supporting
hyperplanes (3) to I with . 0, those whose -intercept in maximized provided
such hyperplanes exists.
In Figure 5.1 the supporting hyperplane to I at any point P with z-
coordinate greater than z* has : 0. Thus these hyperplanes do not enter into
the competition. The unique hyperplane through M with normal (0, 91) is

the required hyperplane. The -intercept of this horizontal hyperplane is *.

Thus there is no duality gap and the dual problem has a solution. The point
M corresponds to a point x such that g(x ) : 0. Therefore, from the
 * *
complementary slackness condition 1 , g(x )2 : 0, we have that : 0. This
* *
is in agreement with the geometry.
In Figure 5.2 any hyperplane through M whose normal lies in the angle

formed by n and the vector (0, 91) is a supporting hyperplane with . 0
having maximal -intercept equal to *. Thus, again there is no duality gap and

the dual problem has a solution.
From Figure 5.1 and the de¬nition of the function we see that the graph
is the lower boundary curve of I for z - z* and then the straight line
of

: * for z . z*. At M the function is differentiable and (0) : 0. The
  
dual problem has the unique solution : 0, and so (0) : .
* *
In Figure 5.2 the graph of is the lower boundary curve of I for z - 0 and
then the straight line : * for z . 0. At M the function is not differenti-
 
. 0 such that (9 , 91) lies in the angle formed
able. The set of vectors
* *
by n and (0, 91) is the set * (0). The dual problem attains its solution at any
vector in 9* (0).

Exercise 5.1. In Exercises 3.1(i), (ii), and (iv) sketch the sets I and carry out the
geometric arguments of this section in these speci¬c problems, whenever
possible. For problems in which the arguments made in connection with
Figures 5.1 and 5.2 seem to fail, explain why.


6. QUADRATIC PROGRAMMING

Quadratic Programming Problem (QP)
Let Q be a positive semide¬nite n ; n matrix, let b be a vector in RL, let A be
an m ; n matrix, and let c be a vector in RK. Minimize

f (x) : 1x, Qx2 9 1b, x2

subject to
Ax - c.

The formulation just given includes equality constraints of the form Hx : d.
This is achieved by the device already used of writing each equality constraint
1h , x2 : d , where h is the ith row of H as two equality constraints.
G G G
QUADRATIC PROGRAMMING 211


Because Q is positive semide¬nite, the function f is convex. The constraints
are af¬ne. Hence the problem is a convex programming problem. We leave it
as an exercise to show that if the matrix Q is positive de¬nite, the problem does
have a solution, while the problem need not have a solution if Q is only positive
semide¬nite. If Q is positive de¬nite, then f is strictly convex. Since in this case
we are minimizing a strictly convex function over a convex set, the minimum
is achieved at a unique point x .
*
For the quadratic programming problem the Lagrangian L is de¬ned by

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



T 6.1. A necessary and suf¬cient condition for a point x to be a solution
*
of QP is that

Ax - c (2)
*
and there exist a vector . 0 in RL such that
*
Qx 9 b ; AR : 0, (3)
* *
1 , Ax 9 c2 : 0. (4)
* *
Proof. We ¬rst prove the necessity of the conditions. If x is a solution of
*
QP, then x is feasible, so (2) holds. By Theorem IV.5.1 or by Remark 2.3,
*
. 0 and a vector . 0 in RL such that
there exists a real number
 *
( , ) " (0, 0),
*
(Qx 9 b) ; AR : 0, (5)
 * *
and (4) holds. We shall show that : 0 is not possible. Hence we may take

: 1 and get (3).

If : 0, then " 0, and from (5) we get that AR : 0. It then follows
 * *
from (4) that 1 , c2 : 0. Thus the system
*
AR
y : 0, y . 0, y " 0, y + RK,
cR

has a solution y : . It then follows from Gordan™s theorem (Theorem II.5.2)
*
that

x
(A, 9c) .0


for all x + RL, in R. Hence Ax . c for all x in RL and in R. In particular,
212 CONVEX PROGRAMMING AND DUALITY


this inequality holds for : 0. Hence Ax . 0 and A(9x) . 0 for all x in RL.
Thus Ax : 0 for all x in RL, which is not possible since A is not the zero matrix.
The suf¬ciency of the conditions follows from Theorem IV.5.3 with f (x) :
1x, Qx2 and g(x) : Ax 9 c.

Remark 6.1. In Theorem 6.1 we showed that in the quadratic programming
problem the KKT condition is a necessary condition for a minimum without
assuming a priori that a constraint quali¬cation holds. The linearity of the
constraints, however, played a crucial role.

Theorem 6.1 suggests the following procedure for solving QP. Solve the
linear system (3) and then reject all solutions of (3) that do not satisfy (2) and
(4). In actual practice, however, various computational algorithms related to
the simplex method have been devised to solve quadratic programming
problems. For a discussion of these see Bazzara, Shetty, and Sherali [1993].
An alternate, and possibly more fruitful, approach is through the dual
problem, which is

max+  ( ) : . 0,  ( ) 9 9-,, (6)
where

 ( ) : inf+L (x, ) : x + RL, (7)

and L is de¬ned in (1). A justi¬cation for this procedure is provided by the
following theorem.

T 6.2. L et Problem QP have a solution x . T hen there is no duality gap
*
between QP and the dual problem, the dual problem has a solution, and the
solution is given by the multipliers of T heorem 6.1.
*
Proof. For ¬xed . 0, the function L ( ·, ) de¬ned in (1) is convex on RL.
Therefore, by the corollary to Theorem IV.3.2, a necessary and suf¬cient
condition for a point x to minimize L is that
x L (x , ) : 0, where
x denotes
 
the gradient with respect to x. Since x is a solution to QP, it follows from (3)
*
of Theorem 6.1 that
x L (x , ) : 0. Hence,
**
L (x , ) : min+L (x, ) : x + RL,.
** *
From this and from (2) and (4) we see that (2.18) of Theorem 2.7 holds, where
h is the zero function. Thus, (x , ) is a saddle point for L . The conclusion of
**
the theorem now follows from Theorem 4.3.

Remark 6.2. Note that we have not assumed strong consistency, but we have
assumed that QP has a solution. We have already remarked that a suf¬cient
condition for the existence of a solution is that Q be positive de¬nite.
QUADRATIC PROGRAMMING 213


In determining the explicit form of the dual problem, it is useful to consider
the unconstrained quadratic programming problem. Minimize

f (x) : 1x, Qx2 9 1b, x2, x + RL. (8)


Since Q is positive semide¬nite, there exists an orthogonal matrix P such that
PAPR is a diagonal matrix. Under the transformation of coordinates y : Px,
(8) becomes

L
F(y) : f (PR y) :  yRPQPRy 9 bRPRy : ( y ; % ; y) ;  d y ,
   II GG
G

are the positive eigenvalues of Q. If k is positive de¬nite, then
where the
G
k : n; if k is positive semide¬nite, then k : n. If a coef¬cient d with i 9 k is
G
different from zero, then by considering vectors e , where is a scalar and e
G G
is the vector whose ith component is 1 and whose other components are zero,
we see that inf+F(y) : y + RL, : 9-. If d : 0 for all i 9 k, then
F(y ) : 0 at
G 
any point y : (y , . . . , y ) with
  L
d
G, i : 1, . . . , k,
y:
G

<<

. 46
( 59 .)



>>