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