In Remark IV.5.9 we pointed out that if the feasible set X in CPI is not

empty, then it is convex. Thus in CPI we are minimizing a convex function

179

180 CONVEX PROGRAMMING AND DUALITY

de¬ned on the convex set X. Therefore, the properties of solutions listed in

Theorem IV.3.1 are valid for CPI.

If the functions f and g are differentiable on X , then CPI is a special case

of the programming problem PI. Hence Theorem IV.5.1 (the Fritz John

necessary conditions), Theorem IV.5.2 (the KKT necessary conditions), and

the suf¬ciency theorem IV.5.3 are all valid.

It turns out that in many problems involving af¬ne equality constraints

h(x) : 0, sharper results can be obtained if we retain the equality constraints

as such rather than replace them by two sets of inequality constraints. It will

also be convenient to take X : RL when af¬ne constraints are present. We

therefore formulate the convex programming problem with af¬ne constraints

as follows.

Convex Programming Problem II (CPII)

Let f : RL ; R be convex, let g: RL ; RK be convex and let h: RL ; RI be af¬ne.

Minimize

+ f (x) : x + X,,

where

X : +x : g(x) - 0, 5 +x : h(x) : 0,.

If the feasible set X is not empty, the problem is said to be consistent.

Remark 1.2. The components of the af¬ne equality constraints h(x) : 0 can be

written as

1a , x2 9 b : 0, i : 1, . . . , k. (1)

G G

Thus, if the problem is consistent, then the system

Ax : b, (2)

where A is the k;n matrix whose ith row is a and b : (b , . . . , b )2 has

G I

solutions. We recall from linear algebra that for (2) to have solutions the rank

of A must equal the rank of the augmented matrix (A, b). If the system (2) has

solutions and if the rank of (A, b) were less than k, then one of the equations

in (1) could be written as a linear combination of the others and thus

eliminated from the system. Since we are only interested in problems that are

consistent, there is no loss of generality in assuming that A has maximum

possible rank, namely k. In that event the ranks of A and (A, b) both equal k.

If the feasible set consists of only one point, then the programming problem is

trivial. Therefore, we further assume that k : n. For if k : n and A has rank

NECESSARY CONDITIONS AND SUFFICIENT CONDITIONS 181

k : n, then (2) has a unique solution and the feasible set consists of a single

point. The assumptions that A has rank k and that k : n will be in force

henceforth.

In the next section we shall develop necessary conditions and a suf¬cient

condition for a point x to be a solution of CPII without assuming differentia-

*

bility.

2. NECESSARY CONDITIONS AND SUFFICIENT CONDITIONS

Our ¬rst necessary condition will involve a function with domain

RL;R;RK;RI and range in R de¬ned by

(x, , , ) : f (x) ; 1 , g(x)2 ; 1 , h(x)2. (1)

The function is sometimes called a generalized Lagrangian.

T 2.1. L et f and g be convex on RL and let h be af¬ne. L et x be a

*

solution of CPII. T hen there exist a real number , a vector in RK, and a

* *

vector in RI with ( , ) . (0, 0) and ( , , ) " (0, 0, 0) such that

* * * * * *

1 , g(x )2 : 0 (2)

* *

and such that for all x in RL, all . 0 in RL, and all in RI

, , ) - (x , , , ) - (x, (3)

(x , , , ).

* * * * * * * * *

Moreover,

, , ): f (x ). (4)

(x ,

* * * * * *

Proof. Since x is a solution of CPII, the system

*

f (x) 9 f (x ) : 0,

*

g(x) : 0, h(x) : 0,

has no solution in RL. Hence by Theorem III.4.1 there exists a vector

( , , ) " (0, 0, 0) with ( , ) . 0 such that

* * * * *

( f (x) 9 f (x )) ; 1 , g(x)2 ; 1 , h(x)2 . 0

* * * *

182 CONVEX PROGRAMMING AND DUALITY

for all x in RL. Hence

f (x ) - f (x) ; 1 , g(x)2 ; 1 , h(x)2 (5)

* * * * *

for all x in RL. In particular, (5) holds for x : x . Since h(x ) : 0, we get that

*

*

1 , g(x )2 . 0. On the other hand, since x is feasible, g(x ) - 0. But . 0,

* * *

* *

so 1 , g(x )2 - 0. Hence, 1 , g(x )2 : 0, and (2) is established.

*

* * *

From (2), (5), and h(x ) : 0 we now get

*

f (x ) ; 1 , g(x )2 ; 1 , h(x )2

* * * * * *

: f (x ) - f (x) ; 1 , g(x)2 ; 1 , h(x)2

* * * *

*

for all x. This establishes (4) and the rightmost inequality in (3). From (2) and

from g(x ) - 0 it follows that for . 0

*

1 , g(x )2 - 0 : 1 , g(x )2.

* *

*

From this and from h(x ) : 0 we get that

*

f (x ) ; 1 , g(x )2 ; 1 , h(x )2 - f (x ) ; 1 , g(x )2 ; 1 , h(x)2,

* * * * * * *

* *

which is the leftmost inequality in (3).

. 0 and g(x ) - 0, condition (2) is equivalent to

Remark 2.1. Since

*

*

g (x ) : 0, i : 1, . . . , m. (2)

*G G *

Remark 2.2. Although (3) is written as a saddle point condition for the

function , the leftmost inequality does not involve since h(x ) : 0.

*

Remark 2.3. If the functions f and g are differentiable, then since x minimizes

*

the function ( · , , , ) on RL, where

* * *

(x, , , ): f (x) ; 1 , g(x)2 ; 1 , h(x)2,

* * * * * *

we have

*

, , ) : 0, i : 1, . . . , n.

(x ,

*x * * * *

G

Thus, if A is the matrix in (1.2),

f (x ) ; R

g(x ) ; R A : 0,

* *

* * *

which together with (2) and the condition ( , , ) " (0, 0, 0) constitute the

* * *

FJ necessary condition of Theorem IV.5.1.

NECESSARY CONDITIONS AND SUFFICIENT CONDITIONS 183

Remark 2.4. In the proof of Theorem 2.1, the optimality of x is shown to

*

imply the existence of a vector ( , , ) " (0, 0, 0) with . 0 and .0

* * * * *

such that relation (5) holds. All the conclusions of the theorem then follow from

(5) and the feasibility of x . We shall use this observation in the sequel.

*

As in the study of differentiable problems, we seek a constraint quali¬cation

" 0, for then we can take : 1. For the convex

that guarantees that

* *

programming problem the following simple constraint quali¬cation suf¬ces.

De¬nition 2.1. The problem CPII is said to be strongly consistent, or to satisfy

the Slater condition, if there exists an x such that g(x ) : 0 and h(x ) : 0.

T 2.2. L et x be a solution of CPII and let the problem be strongly

*

consistent. T hen there exists a . 0 in RK such that

*

1 , g(x )2 : 0 (6)

* *

and a vector in RI such that for all x, all . 0 in RK, and all in RI

*

L (x , , ) - L (x , , ) - L (x, , ), (7)

* *** **

where

L 1x, , ) : (x, 1, ) : f (x) ; 1 , g(x)2 ; 1 , h(x)2. (8)

Moreover,

f (x ) : L (x , , ). (9)

* ***

Proof. Since x is a solution of CPII, the conclusion of Theorem 2.1 holds.

*

: 0, then since (2) holds and h(x ) : 0, the rightmost inequality in (3)

If

* *

becomes

0-1 , g(x)2 ; 1 , h(x)2 (10)

*

*

for all x. If we also have : 0, then the condition ( , , ) " (0, 0, 0)

* * *

*

" 0. Since h(x) : Ax 9 b, the inequality (10) and : 0 imply

implies that

* *

that

1 R A, x2 . 1 , b2. (11)

*

*

for all x. The standing hypothesis made in Section 1 that A has rank k and the

" 0 imply that R A " 0. Hence if we take x : y R A and then let

condition

*

*

*

y ; 9-, we see that (11) cannot hold for all x. Hence " 0.

*

Since the problem is strongly consistent, there exists an x such that

g(x ) : 0 and h(x ) : 0. Thus, from (10), 1 , g(x )2 . 0. On the other hand,

*

184 CONVEX PROGRAMMING AND DUALITY

. 0 and " 0 imply that 1 , g(x )2 : 0. This contradiction shows that

* * *

" 0. Therefore, we can divide through by 9 0 in (2), (3), and (4), relabel

* *

/ as , and relabel / as to get the conclusion of Theorem 2.2.

* * *

* *

Remark 2.5. The rightmost inequality in (7) and equation (9) give

f (x ) : L (x , , ) - f (x) ; 1 , g(x)2 ; 1 , h(x)2

* *** * *

for all x. Therefore, if we assume that CPII has a solution x and if we know

*

the multipliers and , then the solution x of the constrained problem