<<

. 40
( 59 .)



>>

9h(x) - 0. Since h is af¬ne, both h and 9h are convex.

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

<<

. 40
( 59 .)



>>