Constraint Qualifications for Semi-Infinite Systems of Convex Inequalities.
We introduce and study the Abadie constraint qualification, the weak Pshenichnyi--Levin--Valadier property, and related constraint qualifications for semi-infinite systems of convex inequalities and linear inequalities. Our main results are new characterizations of various constraint qualifications in terms of upper semicontinuity of certain multifunctions. Also, we give some applications of constraint qualifications to linear representations of convex inequality systems, to convex Farkas--Minkowski systems, and to formulas for the distance to the solution set. Some of our concepts and results are new even in the particular case of finite inequality systems.
Introduction
Let I) be a family of convex functions, where I is an arbitrary (but
nonempty) index set, and let us consider the system of \convex inequalities"
Throughout this paper we shall consider only the above framework, which is sucient for many
applications. However, let us mention that some of our results and proofs can be extended to
arbitrary (nite or innite dimensional) normed linear spaces X and to inequality systems (1) with
convex functions
In the sequel we shall assume, without any special mention, that the solution set S of the system
(1) is nonempty, i.e.,
We shall often consider the important particular case when each g i is ane, say
where a denotes the dot product of vectors in IR n . In this case, (1)
becomes a system of linear inequalities,
and (2) becomes
Note that one can formally convert (1) to one convex inequality:
where G() is the sup-function [7] of (1), dened as
i2I
The system (1) is said to be a system with nite-valued sup-function, if
In this paper, we always assume that (8) holds.
For the inequality system (1) and for any x in IR n , we shall denote by I(x) the set of \active
indices" at x, i.e.,
Note that if is the classical
denition of active indices.
One of the reasons of the diculty of extending the results from nite inequality systems to
semi-innite inequality systems is that in the semi-innite case for x 2 bd S the set I(x) may be
empty or may be innite. As we shall see in the sequel, some other reasons, which explain why
many results cannot be extended at all, or can be extended only under some additional assumptions
(and sometimes only with dierent proofs), are the following: while in the nite case the index set
I is compact, in our main results on the general semi-innite case we shall assume no topology on
I; also, while in the nite case for each x 2 IR n the set A x := fg i (x)j i 2 Ig is closed in IR; and
the sup-function G(x) := sup i2I g i (x) is always nite-valued on IR n ; in the general semi-innite case
these are no longer true. Furthermore, it is well-known that for a linear inequality system (4) with
a nite index set I we have
where N S (x) and bd S denote the normal cone of S at x and the boundary of S; respectively. In
general, (10) does not hold for a linear inequality system (4) if I is innite. Given a convex system
(1), another important well-known property for a nite I is (with the convention [ i2; A
where co(A) denotes the convex hull of a set A and @g(x) denotes the subdierential of a convex
function g at x :
In general, (11) does not hold if I is innite.
In the present paper we shall give a detailed discussion of constraint qualications for semi-
innite systems of convex inequalities and linear inequalities and the relations among them. We
shall introduce and study the Abadie constraint qualication, the weak Pshenichnyi-Levin-Valadier
property and related constraint qualications. Our main results are new characterizations of various
constraint qualications in terms of upper semicontinuity of certain multifunctions. Also, we
shall give some applications of constraint qualications to linear representations of convex inequality
systems, convex Farkas-Minkowski systems, and formulas for the distance to the solution set.
Moreover, some of our concepts and results on semi-innite convex inequality systems will yield new
contributions even when applied to the particular case of nite inequality systems (such as Corollary
2).
Let us describe now, brie
y, the sections of our paper.
It is well-known (see e.g. [7, pp. 307-309]) that in the theory of convex minimization over the
solution set of a nite system of convex inequalities the so-called basic constraint qualication, or
brie
y, the BCQ, which requires that the normal cone at each point of the boundary of the solution
set should coincide with \the cone of the active constraints" at that point, plays an important
role; for example, it is satised if and only if the Karush-Kuhn-Tucker (KKT) sucient optimality
conditions are also necessary for optimality (see e.g. [7, Proposition 2.2.1, page 308]). Recently,
the BCQ has been extended to semi-innite linear inequality systems by Puente and Vera de Serio
[14], who have used the term \locally Farkas-Minkowski systems", or brie
y, LFM systems, and
further extended to semi-innite systems of convex inequalities by Goberna and Lopez [5, page
162], who have used the term \convex locally FM systems", or brie
y, CLFM systems. In section
2 we shall introduce a weaker constraint qualication than the BCQ, which is dierent from the
BCQ even in the particular case of nite convex inequality systems, and which we shall call the
Abadie CQ, requiring only that the normal cone at each point of the boundary of the solution set
should coincide with the closure of the cone of the active constraints at that point. We shall give
new characterizations of the Abadie CQ and the BCQ in terms of upper semicontinuity of certain
associated convex cone-valued multifunctions.
In section 3 we shall introduce and study the PLV (Pshenichnyi-Levin-Valadier) property and
the weak PLV property of a semi-innite convex inequality system at a point x, requiring that the
subdierential of the sup-function G() at x should coincide with (respectively, with the closure
of) the convex hull of the subdierentials of constraints corresponding to the active indices at
that point; when this property holds for all points in the boundary of the solution set, we shall
simply use the terms PLV property or weak PLV property, respectively. In the particular case of
nite linear inequality systems the BCQ (and hence the Abadie CQ) is always satised, and for
nite convex inequality systems so is the PLV property (whence also the weak PLV property) at
all points of IR n , but for semi-innite inequality systems the situation is dierent. We shall give
new characterizations of the PLV and weak PLV properties in terms of upper semicontinuity of
certain associated multifunctions. We shall also show some connections among the PLV, weak PLV
properties, the BCQ, and Abadie CQ.
In section 4 we shall be concerned with Slater conditions. In contrast with the case of nite
systems of convex inequalities, in the semi-innite case two dierent Slater conditions appear in
a natural way: the usual one, requiring the existence of a point in the solution set, at which all
inequalities of the system are satised as strict inequalities, and the so-called strong Slater condition
(following the terminology of [5, page 128]), in which the inequalities of the system are required to
be satised uniformly strictly, that is, in which the sup-function of the system is required to satisfy
the usual Slater condition. We shall study the connections between the Slater conditions and the
constraint qualications discussed in sections 2 and 3; it will turn out that the situation concerning
these connections is dierent from that occurring in the case of nite inequality systems. Also, we
shall see that in the general semi-innite case the usual Slater condition is too weak.
The nal section 5 is devoted to some applications of constraint qualications.
Given a system of convex inequalities, we recall that any equivalent system of linear inequalities
(i.e., a system of linear inequalities with the same solution set) is called a linear representation
of the given convex system. It is well known that linear representations and, especially a certain
simple one, which we shall call the \standard" linear representation, are useful tools in the study of
convex inequality systems (see e.g. [5] and the references therein). In subsection 5.1 we shall give a
new linear representation of (nite or semi-innite) convex inequality systems satisfying the Abadie
CQ, which uses a much smaller subset of inequalities of the standard linear representation. Also,
we shall show the connections between some properties of the initial convex inequality system and
its representation.
In subsection 5.2 we shall extend from semi-innite linear inequality systems to semi-innite
convex inequality systems the concepts of consequence relations and FM (Farkas-Minkowski) systems
and, using the standard linear representation, we shall extend a known relation between linear
FM systems and the BCQ, given in [14] and [5], to the case of convex FM systems. We shall also
give a direct proof of this result, which, in contrast with the known proof for the linear case, does
not use any subset of
The exact formulas for the distance of a point to the solution set of a convex inequality system are
important, among other reasons, for their connection with \asymptotic constraint qualications"
and for obtaining results on error bounds for such a system (see [11]). The well-known general
formulas for the distance of a point to a closed convex set are not suciently useful for this purpose,
since they do not exploit the special structure of the constraints of the inequality system. Up to
the present, only a formula for the distance to the solution set of a semi-innite linear inequality
system has been essentially known (for a dual version, see [4] and [19], and for the nite case see
[2]). In subsection 5.3, assuming the Abadie CQ or the BCQ, we shall give the rst formulas for
the distance of a point to the solution set of a semi-innite system of convex inequalities, which are
new even in the nite case. Also, using this result, we shall show that the distance of a point to the
solution set of a convex inequality system (1) satisfying the BCQ is equal to the distance of that
point to some nite subsystem of (1).
We conclude this section by introducing some notations which we shall use in this paper.
We shall consider IR n endowed with the usual scalar product h; i; the Euclidean norm kk ; and
the topology induced by this norm. For an index set J , jJ j denotes the cardinality of J . Let A be
a subset of IR n . Then
A; int(A) and bd(A) denote the closure, the interior, and the boundary of
are the convex hull and the closed convex hull of A; respectively;
are the convex cone and the closed convex cone, generated by vectors in A;
is the polar of A, i.e.,
and A is the bipolar of A; in the particular case when A is a cone, A 0 coincides with the
\negative polar of A", i.e., we have
The results of the present paper and of [11] have been presented at the "Workshop on Error
Bounds and Applications in Mathematical Programming" in Hong Kong, December 8-14, 1998.
We wish to thank A. Auslender and A. M. Rubinov for the references [13] and [8], in connection
with Theorem 3. We also thank M. A. Lopez for sending us the manuscript [3], which we have
received after the present paper had been completed; in order to compare our results with those of
[3], we have inserted Remarks 2, 3(a) and 5(a).
Finally, we wish to express our gratitude to M. A. Lopez and M. D. Fajardo for their careful
reading of the manuscript of the present paper and for their valuable remarks which contributed to
its improvement.
Constraint Qualication and Basic Constraint
Qualication
For characterizations of constraint qualications for (1) we consider the convex cone generated by
the subdierentials of the active members of G() at x:
We use N 0 (x) to denote the closure of N 0 (x).
If every g i is an ane function as dened in (3), then
is the cone generated by the \active constraints" at x. Thus, in [5], N 0 (x) is called \the cone of
active constraints at x".
Let T S (x) be the tangent cone of S at x, i.e., T S x). The normal cone of S at
x 2 S is dened as
It is well-known that N S e.g. [7, Proposition 5.2.4, page 137]).
Denition 1 We shall say that the convex inequality system (1) satises
(a) the Abadie constraint qualication, or brie
y, the Abadie CQ, at a point x 2 bd
or equivalently, N S
(b) the basic constraint qualication, or brie
y, the BCQ, at a point x 2 bd S, if
(c) the Abadie CQ (respectively, the BCQ), if it satises the Abadie CQ (respectively, the BCQ) at
all points x 2 bd S.
Remark 1 (a) The equivalence of the two formulas in (18) follows from the bipolar theorem. In
fact, if N S since T S (x) is a closed convex cone, by the bipolar theorem and by
e.g. [7, Proposition 5.2.4, page 137]) we have
On the other hand, if and the bipolar theorem, and since
is a cone, we obtain
(b) Since we always have (see e.g. [7, Lemma 4.4.1, page 267] and [7, Lemma 2.1.3, page 305])
the system (1) satises the Abadie CQ at x 2 bd S if and only if
and it satises the BCQ at x 2 bd S if and only if
Moreover, for x 2 bd S, by (20), (1) satises the Abadie CQ at x if and only if N 0
and (6) satises the Abadie CQ at x. Similarly, by (21), (1) satises the BCQ at x if and only if
the BCQ at x. Clearly, (1) satises the BCQ at x if and
only if it satises the Abadie CQ at x and N 0 (x) is closed. Thus, (1) satises the BCQ at x if and
only if T S closed. The points x 2 bdS with the latter property have
been called \Lagrangian regular points" in [12, Denition 3.3].
(c) When I is nite, Denition 1 is the classical denition of the Abadie CQ introduced by Abadie
(see [1], also [10]) and, respectively, of the basic constraint qualication (see [7, page 207]). If I is
nite and each g i is a dierentiable convex function, then @g i is the
gradient of g i at x) and the cone N 0 (x) of (15) is closed (see e.g. [7, Lemma 4.3.3, page 130]). In
this case, the Abadie CQ and the BCQ coincide.
(d) The BCQ, in an equivalent form, has been introduced for semi-innite linear inequality systems
(4) in [14] (called locally Farkas-Minkowski systems, or brie
y, LFM systems) and extended to
convex inequality systems (1) in [5, pp. 162-163] (called convex LFM constraint qualication).
When I is nite and each g i is an ane function, the BCQ, and hence also the Abadie CQ, are
satised (see e.g. [7, Example 5.2.6(b), page 138]). When each g i is ane, for semi-innite systems
of linear inequalities, the Abadie CQ may not hold and the Abadie CQ is not the same as the BCQ,
as shown by the following example.
Example 1 Let 2:
(a) Semi-Innite Linear Systems Without the Abadie CQ:
x 2i
0g. Also,
Thus the family (24) does not satisfy the Abadie CQ.
(b) Semi-Innite Linear Systems With the Abadie CQ but Without BCQ:
Also,
Thus the family (25) satises the Abadie CQ, but not the BCQ.
Next we give new characterizations of the Abadie CQ and the BCQ for (1), in terms of the
upper semicontinuity of the multifunctions N 0 (); cone(@G()), N 0 () and cone(@G()). We recall
(see e.g. [16, page 55]) that a multifunction (i.e., a set-valued
(the
collection of subsets of IR n ) is said to be upper semicontinuous in the sense of Kuratowski, or brie
y,
upper semicontinuous, at x 2 IR n , if the relations lim k!+1 x
Clearly, the graph of Q (i.e., the set f(x; y)j x 2
is closed if and only if Q is upper semicontinuous at all x 2 IR n .
We shall rst prove a lemma, in which we shall use the convex hull of the subdierentials of the
active members of G(x), that is, the set
be a multifunction such that, for all z in a neighborhood
of x; Q(z) is a convex set, I(z) 6= ;, and D 0 (z)  Q(z). If Q is upper semicontinuous at x,
then @G(x)  Q(x).
Proof. Assume the contrary that there exists y 2 @G(x) n Q(x): Since Q is upper semicontinuous
at x and Q(x) is a convex set, Q(x) is a closed convex set. Then, by the strict separation theorem
[7, Theorem 4.1.1, page 121], there exists u 2 IR n nf0g such that
Let G 0 (x; u) be the directional derivative of G at x in the direction u. By y 2 @G(x) and a
well-known formula for G 0 (x; u) (see e.g. [7, page 240]), we get
z in a neighborhood of x, without loss of generality
we can assume I(x+t k u) 6= ;. Let
Then
whence, by t k
is bounded, the set fy
is bounded as well (see e.g. [7, Proposition 6.2.2, page 282]). Hence, we may assume, without loss
of generality, that y
y. Then, letting k ! +1 in (28) and using (27), we obtain
hb
But, since
lim
and since Q is upper semicontinuous at x, we have b
which contradicts (29). 2
Theorem 1 Let x 2 bd S and I(z) 6= ; for z in a neighborhood of x. Then the following two
statements are equivalent.
(a) (1) satises the Abadie CQ at x.
(b) Both cone(@G()) and N 0 () are upper semicontinuous at x.
Proof. (a))(b): Let x y. We claim that
To prove the claim, let
We consider two cases:
Case 1: (6) does not satisfy the Slater condition, that is, G(z)  0 for all z 2 IR n . Then
. Thus, (31) implies
Letting in the above inequality we obtain
That is, y 2 N S (x).
Case 2: (6) satises the Slater condition, that is, G(^x) < 0 for some ^
S. Then there is k 0 > 0 such that z 2 S k for k  k 0
By (31), we have
Since (32) holds for any z 2 int S, it also holds for z 2 int
If (1) satises the Abadie CQ at x, we get y 2 N S
Therefore, both N 0 () and cone(@G()) are upper semicontinuous at x.
y. Then x 0 62 S (since x
would imply hy; xi  hy; x which is impossible) and
hence
and assume k large enough so that 1
be such that
k. Then, since x 2 S k , we have
Thus, fx
k g is a bounded sequence. Without loss of generality we may assume that x
in (34) we obtain
On the other hand, since x 0 x is the projection of x 0 onto S. Hence,
imply that Consequently, x
y.
We claim that x 0 x
k k we have x
and x 0 x
satises the Slater condition and x
e.g. [7, Theorem 1.3.5, page 245]). Thus, x 0 x
which proves the claim.
by the upper semicontinuity of
cone(@G()) at x we get y 2 cone(@G(x)). Hence, since y was an arbitrary nonzero element in
On the other hand, by the upper semicontinuity of N 0 () at x and
(applied to we have @G(x)  N 0 (x), which implies cone(@G(x))  N 0 (x).
Therefore, we have (22), and thus (1) satises the Abadie CQ at x. 2
Theorem 2 Let x 2 bd S and I(z) 6= ; for z in a neighborhood of x. Then the following two
statements are equivalent.
(a) (1) satises the BCQ at x.
(b) Both cone(@G()) and N 0 () are upper semicontinuous at x.
Proof. (a))(b): By Theorem 1, both cone(@G()) and N 0 () are upper semicontinuous at x. Since
closed, we know that N 0 (x) and cone(@G(x)) must be
closed. Thus, both cone(@G()) and N 0 () are upper semicontinuous at x.
(b))(a): By Theorem 1, (1) satises the Abadie CQ at x. But (b) also implies that N 0 (x) is a
closed set. So N 0 satises the BCQ. 2
From Theorems 1 and 2 we obtain the following characterizations of the Abadie CQ and the
BCQ.
Corollary 1 Suppose that I(z) 6= ; for z in a neighborhood of bdS. Then the following two
statements are true.
(a) (1) satises the Abadie CQ if and only if both cone(@G()) and N 0 () are upper semicontinuous
at every x in bdS.
(b) (1) satises the BCQ if and only if both cone(@G()) and N 0 () are upper semicontinuous at
every x in bd S.
Remark 2 Fajardo and Lopez [3, Theorem 3.1(i)] proved that if (1) satises the BCQ, then the
multifunction A(x) := fy 2 N 0 (x)j kyk  1g (B)-upper semicontinuous on S (which is
equivalent to the upper semicontinuity of N 0 () on S) and that if (6) satises the Slater condition,
then the converse is also true [3, Theorem 3.1(iib)].
Here a mapping
is said to be (B)-upper semicontinuous at x 2 IR n , if for every
open set W in IR n containing Q(x) there exists a neighbourhood V (x) of x such that Q(z)  W
for each z 2 V (x); furthermore, Q is said to be (B)-upper semicontinuous on a set M  IR n if
it is (B)-upper semicontinuous at each x 2 M: It is well-known (see e,g, [5, p. 128]) that if Q is
(B)-upper semicontinuous (at x) then it is upper semicontinuous (at x); but the converse is not
true. One can show that if the set fzj z 2 Q(y) for y in some neighborhood of xg is bounded, then
the (B)-upper semicontinuity of Q() at x is equivalent to the upper semicontinuity of Q() at x.
3 Subdierentials of the Sup-Function and Its Active Member

In this section, we study the relations between the subdierential of the sup-function G and the
subdierentials of its active member functions fg I(x)g.
We shall use the set D 0 (x) dened by (26). Note that
We shall denote by D 0 (x) the closure of the set D 0 (x):
One important property of (1) when I is nite is the equality (11) (see e.g. [13, Theorem 1.4]),
which can be rewritten as
The above equality means that the subdierential of the sup-function G() is the convex hull of
subdierentials of its active members.
In general, (37) does not hold if I is innite. The following sucient (but not necessary)
condition that guarantees , and is satised when I is nite, has been
given by Levin [8, Theorem 2] (and, at the same time, Valadier [18, Theorem 2] has obtained, in
an arbitrary topological linear space instead of IR n ; the weaker conclusion in which D 0 is replaced
by D 0
Theorem 3 (Pshenichnyi-Levin-Valadier Theorem [13, 8, 18]) If I is a compact set (in some
metric space), and is a family of convex functions such that for each xed
upper semicontinuous on I, then (37) holds at all x 2 IR n .
Here a real-valued function f(t) is said to be upper semicontinuous at
lim
i.e.,
lim
sup
Note that (39) is equivalent to the upper semicontinuity of the multifunction F fy 2 IRj y
f(t)g at t 0 .
For convenience, we shall introduce the following denition related to (37) (where PLV stands
for \Pshenichnyi-Levin-Valadier").
Denition 2 Let (1) be a convex inequality system with a nite-valued sup-function. We shall say
that the family fg or the system (1), has
(a) the weak PLV property at a point x 2
(b) the PLV property at a point x 2
(c) the weak PLV property (respectively, the PLV property), if it has the weak PLV property (re-
spectively, the PLV property ) at all x 2 bd S:
One major problem with an innite I is the possibility of (which can
not happen when I is nite). For example, given a family of convex functions
holds if and only if
However, the active index set for (42) is empty at every x 2 bd S and so there is no (weak) PLV
property for (42).
One can avoid the inconvenience of having by requiring the closedness of fg i (x)j i 2 Ig.
Proposition 1 Let x 2 bd S: If the set A x := fg i (x)j i 2 Ig is closed in IR, then I(x) 6= ;:
Proof. Since x 2bd S; we have (by the continuity of G): Taking any sequence fi k g  I
such that g i k
by the closedness of A x we obtain 0 2 A x ;
so I(x) 6= ;: 2
However, even if I(x) 6= ;, (4) (and hence, in general, (1)) might not have the weak PLV
property. Also, in general, the weak PLV property is not the same as the PLV property.
(a) A Semi-Innite Linear System Without Weak PLV Property:
Then
k1
4x if x  0:
f3g. Therefore, the system does not have the weak PLV property at
(b) A Semi-Innite Linear System With Weak PLV Property, But Without PLV Property:
Then
k1
x if x < 0;
5x if x  0:
5). Therefore, the system has the weak PLV property at but not the PLV
property.
There is no relation of implication between the CQs and the PLV properties. Indeed, in Example
2(a), the system actually satises the BCQ at but the PLV property does not hold at
while for any I with one index the PLV property is trivially true, but (1) may not satisfy
the Abadie CQ. However, when (1) satises the PLV property (in particular, when I is nite),
and the characterizations for the Abadie CQ and the BCQ can be simplied.
Corollary 2 Suppose that (1) satises the PLV property and I(x) 6= ; for x in a neighborhood of
bd S (e.g., this happens when I is nite). Let x 2 bd S. Then the following two statements are
true.
(a) (1) satises the Abadie CQ at x if and only if N 0 () is upper semicontinuous at x.
(b) (1) satises the BCQ at x if and only if N 0 () is upper semicontinuous at x.
Proof. By the assumption, D 0 all x, which implies N 0
x. Thus Corollary 2 follows from Corollary 1. 2
The following proposition shows that if (1) satises the (weak) PLV property, then (1) and (6)
are \equivalent" in terms of CQ's.
Proposition 2 Let x 2 bdS.
(a) Suppose that (1) satises the weak PLV property at x. Then (1) satises the Abadie CQ at x
if and only if (6) satises the Abadie CQ at x.
(b) Suppose that (1) satises the PLV property at x. Then (1) satises the BCQ at x if and only
if (6) satises the BCQ at x.
Proof. (a) If (1) satises the weak PLV property at x; then, by (40) and (36),
only if N S
(b) If (1) satises the PLV property at x; then, by (41) and (36),
only if N S
It turns out the the weak PLV property or the PLV property at a point x 2 IR n can be characterized
by the upper semicontinuity at x of the multifunction D 0 () or D 0 (), respectively.
Theorem 4 Let x 2 IR n and I(z) 6= ; for z in a neighborhood of x. Then
only if D 0 () is upper semicontinuous at x.
Proof. If D 0 () is upper semicontinuous at x, then, by Lemma 1, @G(x)  D 0 (x). Since @G(x)
holds, we have
Next we assume that prove the upper semicontinuity of D 0 () at x.
Let lim k!+1 x
we have y k 2 @G(x k G is a nite convex function, @G(z) 6= ; for all z 2 IR n and @G
is upper semicontinuous (see e.g. [7, Proposition 6.2.1, page 282]). Thus, y 2 @G(x). Since
upper semicontinuous at x. 2
Theorem 5 Let x 2 IR n and I(z) 6= ; for z in a neighborhood of x. Then
only if D 0 () is upper semicontinuous at x.
Proof. Note that D 0 () is upper semicontinuous at x if and only if D 0 () is upper semicontinuous at
x and D 0 (x) is a closed set.
If D 0 () is upper semicontinuous at x, then, by Theorem 4, On the
other hand, if then by the upper semicontinuity of @G(), D 0 (x) is a closed set
and Hence, by Theorem 4, D 0 () is upper semicontinuous at x. Therefore, D 0 () is
upper semicontinuous at x. 2
Using Theorems 4 and 5 we obtain the following characterizations of the weak PLV and PLV
properties at all x 2 IR n .
Theorem 6 The following statements are true.
(a)
semicontinuous on
only if D 0 (x) 6= ; for all x 2 IR n and D 0 () is upper
semicontinuous on
Proof. Since G() is a nite convex function, @G(x) 6= ; for any x. Therefore, every condition in the
above theorem implies I(x) 6= ; for all x 2 IR n . Consequently, Theorem 6 follows from Theorems 4
and 5. 2
Remark 3 (a) Fajardo and Lopez [3, Theorem 4.1(i)] proved that if D 0 (x) 6= ; for all x 2 IR n and
(B)-upper semicontinuous on IR n (see Remark 2 above), then
Since the (B)-upper semicontinuity of D 0 () is equivalent to the upper semicontinuity of D 0 ()
(see Remark 2), the \if" part of Theorem 6(a) is equivalent to [3, Theorem 4.1(i)].
(b) Using Theorem 6, we can give a new proof of Theorem 3, which seems simpler and more natural
than the proofs known in the literature (see e.g. the proof of Theorem 4.4.2 [7, page 267 ]. To this
end, let us rst prove the following fact:
If I is a compact metric space and if is a family of convex functions
such that for each x 2 IR n the function upper semicontinuous on I, then
the set-valued mapping x ! I(x) is upper semicontinuous on IR n and the set-valued
mapping upper semicontinuous on W; where W := f(x; i)j i 2 I(x)g.
i.e., if lim k!+1 x
y with
First we prove by contradiction. In fact, if by the upper semicontinuity
of g i (x) with respect to i, there exist a positive constant  and a neighborhood O( ^ i) of ^ i in I such
that
(x). By the assumptions, ^
are
continuous convex functions. Thus,
But (45) implies that ^
G(^x)  G(^x) , a contradiction to (46). This proves that
Now, for any z 2 IR n , we have
Thus, letting k ! +1 in (47) and using lim k!+1 g i k
(by the assumption of upper
semicontinuity of the mapping
Since (49) holds for any z, we have ^
Finally, in order to prove Theorem 3 it will be sucient, by Theorem 5, to prove that under the
assumptions of Theorem 3 the mapping D 0 () has closed graph and I(x) 6= ; for all x 2 IR n . Let
By the denition of D 0
there exist
theorem (see e.g. [7,
Theorem 1.3.6, page 98]) we may assume, without loss of generality, that m k  n + 1. Since G()
is nite-valued and x
x, the set fy 2 @G(x k )j bounded (see e.g. [7, Proposition
6.2.2, p. 282]). By y j;k 2 @g i j
we know that fy j;k
a bounded set. Since I is compact and fm k g, fy j;k are all bounded with respect to k, by
repeatedly selecting subsequences we may assume, without loss of generality, that m
+1. By the fact proved above, we know that
and y
(x). Thus,
which proves that D 0 () has closed graph. Finally,
since I is compact and i ! g i (x) is upper semicontinuous, we have I(x) 6= ; for all x 2 IR n . This
provides an alternative proof of Theorem 3.
4 Slater Conditions
If there exists  x 2 IR n such that
then (1) is said to satisfy the Slater condition. Let us recall the following well-known result, which
gives a sucient condition for the BCQ of (1) or (6).
Proposition 3 ([7, Theorem 1.3.5, page 245] and [7, Remark 1.3.6, page 246]) If I is nite and
(1) satises the Slater condition, then (1) satises the BCQ. In particular, if (6) satises the Slater
condition, then (6) satises the BCQ.
Remark 4 (a) If (6) satises the Slater condition, then (1) also satises the Slater condition. But
the converse is not true. The Slater condition for (6) is sometimes called the strong Slater condition
for the convex system (1) (see e.g. [5, page 128]). However, the term \strong Slater condition"
is also used in the literature in other senses (see e.g. Lewis and Pang [9], where \strong Slater
condition" means that 0 does not belong to the closure of the set @G(G 1 (0)); and, for a dierent
sense, see [7, Denition 2.3.1, page 311]).
(b) When I is nite, (1) satises the Slater condition if and only if (6) satises the Slater condition.
Proposition 4 Suppose that (6) satises the Slater condition.
(a) If (1) has the weak PLV property, then (1) satises the Abadie CQ.
(b) If (1) has the PLV property, then (1) satises the BCQ.
Proof. (a) By Proposition 3, the Slater condition for (6) implies the BCQ for (6). Hence, by
Proposition 2(a), we have the Abadie CQ at all x 2 bd S.
(b) The proof is similar, using Proposition 2(b). 2
Remark 5 (a) Fajardo and Lopez [3, Theorem 4.1(ii)] proved that if (6) satises the Slater condi-
tion, D 0 () is (B)-upper semicontinuous (see Remark 2), D 0 (x) closed
for each x in S, then (1) satises the BCQ. But the (B)-upper continuity of D 0 () is equivalent to
the upper continuity of D 0 () (see Remark 2), so this result also follows from Theorem 6(a) and
Proposition 4(a).
(b) The assumptions in (a) and (b) of Proposition 4 cannot be omitted, as shown by Example 1(a),
in which the Slater condition for (1) or (6) is satised (in fact, for
but the Abadie CQ is not satised. When I is a nite set, the PLV property always holds. In this
case, the Slater condition, the BCQ, and the Abadie CQ are all dierent.
We recall that for a convex system (1) a solution
x 2 S is called a Slater point if we have (50).
Proposition 5 If for each x 2 S the active index set I(x) 6= ;, then every Slater point of (1) is a
Slater point of (6) (and hence, in this case, the Slater condition for (1) and the Slater condition for
are equivalent).
Proof. Let
x be a Slater point of (1), i.e., let
x be a point such that (50) holds. If  x were not a
Slater point of (6), i.e., if we had sup i2I g i since I(x) 6= ;, there would exist i 0 2 I
such that g i 0
a contradiction to the assumption (50). 2
Using Theorem 3, one can give a stronger condition which ensures the BCQ. Indeed, combining
Theorem 3 and Proposition 4, we obtain the following result, which has been proved with a more
complicated method by Lopez and Vercher [12, Theorem 3.8].
Corollary 3 If I is a compact set (in some metric space), is a family of
convex functions such that for each xed x 2 IR n the function upper semicontinuous on
I, and (1) satises the Slater condition, then the BCQ holds for (1).
Proof. Since I is compact and i ! g i (x) is upper semicontinuous, I(x) 6= ; for any x. By Proposition
5, (6) satises the Slater condition. By Theorem 3, the PLV property holds. Thus, the corollary
follows from Proposition 4. 2
Even though we stated Corollary 3 in terms of the Slater condition of (1), obviously the Slater
condition of (6) is also satised. In general, the Slater condition for (1) is not very meaningful if
(6) does not satisfy the Slater condition. One might wonder whether we should use the following
stronger version of (50):
where  is a positive constant. In the case that G(x) < +1 for x 2 IR n , (51) is nothing more than
the Slater condition for (6). If one allows G(x) to be +1, then (51) does not provide any useful
information about the system as shown in the following example.
Example 3 (a) For fg
Then (51) holds with g i and  being replaced by  g i and 1, respectively. Note that x 2 S if and
only if  g i (x)  0 (i 2 I). Also the sets I(x) and N 0 (x) remain unchanged for x 2 bd S. Thus, (1)
satises the Abadie CQ (respectively, the BCQ) if and only if so does the system
This example shows that replacing (50) by (51) without requiring a nite-valued G does not give
any new information about the underlying system.
(b) Or we could make the situation worse. For example,
Then we always have
It is easy to see that x 2 S if and only if 1. In this case, the active index
set is always empty for any x 2 bdS. Thus, it is not possible to study S by using N 0 (x). This
example shows that (51) without requiring a nite-valued G(x) could be a meaningless condition;
while (51) with a nite-valued G(x) means that (6) satises the Slater condition, which is useful
for constraint qualication properties of (1) (see Proposition 4).
Applications
5.1 Linear Representation of Convex Systems
Given a semi-innite convex inequality system (1), we recall that a semi-innite linear inequality
system,
a is said to be a linear representation of the system (1), provided that x
is a solution of (1) if and only if x  is a solution of (54) (i.e., provided that the systems of inequalities
(1) and (54) are equivalent). Each linear representation (54) of (1) is also called a linear system
associated to the convex system (1).
It is well-known (see e.g. the proof of Theorem 5.2 in [6]) that the system,
is a linear representation of the convex system (1), which we shall call the standard linear representation
of (1). For the sake of completeness, we include here the proof. If x  2
so x  satises (55). Conversely, if x  satises (55), then
Taking here which completes the proof.
A natural question is whether we can use a smaller subsystem of (55) to get a linear representation
of (1). In particular, we study when the following semi-innite linear system,
is a linear representation of (1). Note that (56) is indeed a subsystem of (55), since for z 2 bd S,
Theorem 7 (a) If the convex system (1) satises the Abadie CQ, then the system (56) is a linear
representation of (1).
(b) If the convex system (1) satises the Slater condition (50) and I(x) 6= ; for all x 2 S, then
the system (56) is a linear representation of (1).
Proof. Obviously, if x 2 S, then, since @g i (z)  N S (z) for i 2 I(z) and z 2 bd S, (56) follows from
(z). Thus, every solution of (1) is a solution of (56). In order to prove that (56) is a linear
representation of (1), it is sucient to show that if x 62 S, then (56) does not hold.
(a) First we prove the following more general result:
Suppose that for any x 2 bd S and y 2 N S (x) n f0g, there is a vector ^
that linear representation of (1).
Let x 62 S and let z be the projection of x onto S. Then z 2 bdS, x z 6= 0, and x z 2 N S (z)
[7, Theorem 3.1.1, page 117]. If hy
for all y 2 N 0 (z), a contradiction to the assumption there is ^
Hence, x does not satisfy (56). This proves that x 2 S if and only if x satises (56), i.e., (56) is a
linear representation of (1).
Now, if the convex system (1) satises the Abadie CQ, i.e., N S
then it is trivially true that for any x 2 bd S and y 2 N S (x) n f0g, there is a vector
that
(indeed, it is enough to take ^
suciently close to y): So (56) is a linear
representation of (1).
(b) By Proposition 5, (6) satises the Slater condition. Let x 62 S, and let  x 2 S be such that
contains exactly one point, say z. Then there is a positive constant
such that
by the denition of @G(z), we have
xi  G(z)
Since  > 0, it follows from (57) and (58) that 1
Thus, for any x 62 does not hold. So (56) is a linear representation of (1).Remark 6 (a) In [12, the proof of Theorem 4.5], it has been observed that if (1) satises the
assumptions of Corollary 3, then the linear inequality system,
is a linear representation of (1). Let us observe that this follows also from Corollary 3 and Theorem
under the assumption of Corollary 3,
hence (59) is equivalent to (56).
(b) In the particular case when all are convex and dierentiable, Theorem 7(b) (even
with a smaller subsystem of (56), obtained by choosing for each x 2bd S; with the aid of the axiom
of choice, an index i(x) 2 I(x) and an y i(x) 2 @g i (x)) has been shown, essentially, in the proof of
Theorem 5.4 in [6].
Some connections between the inequality systems (1) and (56) are given in the following proposition

Proposition 6 Let (56) be a linear representation of the convex inequality system (1). Then
(a) (1) satises the Abadie CQ (respectively, the BCQ) if and only if so does (56).
(b) Denoting by G and G 0 the sup-functions of (1) and (56) respectively, we have
Proof. (a) Let (56) be a linear representation of (1) and let x 2 bd S: Since (1) and (56) have the
same solution set and hence the same normal cone N S (x) at x; it will be enough to show that
Since the linear system (56) is a subset of the linear system (55), we have
Furthermore, by [5, proof of Theorem 10.7], there holds
Finally, from the denitions it is obvious that
which, together with (62) and (63), yields (61).
(b) By the denitions of the sup-function and of @g i (z) and I(z); we have, for any x 2
z2bd
sup
i2I
Remark 7 (a) The inequality in Proposition 6(b) may be strict.
(b) From Proposition 6(b) above it follows that if (1) satises the Slater condition, then so does
also, if (6) satises the Slater condition, then G 0 (x) < 0 for some x 2 However, the
converse statements are not true.
5.2 Convex Farkas-Minkowski Systems
Related to the BCQ are the convex Farkas-Minkowski systems, dened as follows.
Denition 3 (a) A linear inequality
where a will be called a consequence relation of the convex inequality
system (1), if every x 2 S satises (65):
(b) The system (1) will be called a convex Farkas-Minkowski (or brie
y, a convex FM) system, if
every linear consequence relation of system (1) is also a consequence relation of some nite
subsystem of (1).
Remark 8 In the particular case of a linear inequality system (4), the above denition reduces to
the usual denition of consequence relations and FM systems [5].
One can extend some results on linear FM systems to convex FM systems. For example, the
fact that a linear inequality system (4) satisfying the BCQ and with bounded solution set S is an
FM system (see [5, Exercise 5.7]), admits the following extension.
Proposition 7 A convex inequality system (1) satisfying the BCQ and with bounded solution set
S is a convex FM system.
Proof. By the above proof of Proposition 6(a), (1) satises the BCQ (if and) only if so does its
standard linear representation (55). Furthermore, since (55) is a linear inequality system having
the same bounded solution set it is an FM system (see e.g. [5, Exercise 5.6]). Finally, let us
show that if (55) is an FM system, then so is (1). Indeed, let
where a since (55) is an FM system and has the same solution set
there exists a nite subsystem of (55), say
where jJ j < +1; such that (65) is a consequence relation of (67). Let S J be the solution set of the
nite subsytem
of (1) and let x
so x is a solution of (67). Hence, since (65) is a consequence relation of (67), we obtain ha
which, since x 2 S J was arbitrary, proves that (1) is an FM system. 2
Remark 9 The proofs of some results on linear systems, given in [5], use certain cones of IR n+1
associated to (4). However, let us observe that one can give, directly for the extensions of those
results to convex systems, proofs which are new even for the case of linear inequality systems, and
do not use any subsets of us give such a proof of Proposition 7. Assume that S
is bounded and (1) satises the BCQ, and let (65) be a consequence relation of (1). Let c be the
smallest number such that ha 0 ; xi  c is still a consequence relation of (1) (such a number exists,
since otherwise S  fx 2 a contradiction to the general assumption made
in this paper).
We claim that there exists z 2 S such that ha Indeed, by the denition of c; we have
cg and for each
Then, since S is bounded and closed, hence compact, fx k g has a subsequence converging to some
which proves our claim.
By the above, we have S  fx 2 Hence, by the BCQ,
there exists a nite subset J of I(z); such that
a
Let
Then, by (70) and J  I(z), we have a 0 2co([ i2J @g i (z))  N S J
(z); that is, ha
Thus, the inequality ha 0 ; xi  c; whence also (65), is a consequence relation of the nite
subsystem of (1), which completes the proof.
Combining Proposition 7 and Corollary 3, there results the following corollary, which has been
proved with more complicated methods in [12, Theorem 4.5].
Corollary 4 If I is a compact set, is a family of convex functions such that
for each xed x 2 IR n the function upper semicontinuous on I, (1) satises the Slater
condition, and the solution set S is bounded, then (1) is an FM system.
The denition of a convex FM system given in [12] referees to its standard linear
representation being a FM system. Under the assumptions of Corollary 4, both denitions are
equivalent.
5.3 The Distance to the Solution Set of a Convex Inequality System
Theorem 8 Let x 2 IR n nS and ^
x be the projection of x onto S.
(a) If (1) satises the Abadie CQ, then
I 0 I(^x)
sup


xi: (72)
(b) If (1) satises the BCQ, then
I 0 I(^x)
sup


xi:
Proof. By [17, Remark 8b)], we have
(a) By the Abadie CQ at ^
x, we have y 2 N S (^x) with only if there exist I k


1 such that
y.
Thus, (72) is equivalent to (74).
(b) By the BCQ at ^
x, we have y 2 N S (^x) with only if there exist I 0  I(^x),


1 such that
y. Thus,
(73) is equivalent to (74). 2
Remark 11 The assumption of Abadie CQ may be too strong, but at least the assumption I(b x)
(which is implied by the Abadie CQ) is necessary in order to have (72). Indeed, if I(b
the right hand side of (72) is meaningless.
When applied to the semi-innite linear system (4), @g j means that
and thus Theorem 8 reduces to the following form.
Corollary 5 Let x 2 IR n nS and ^ x be the projection of x onto S.
(a) If (4) satises the Abadie CQ, then
I 0


(b) If (4) satises the BCQ, then


Remark 12 (a) By a well-known theorem of Caratheodory (see e.g. [15, Corollary 7.1(i), page
94]), in each positive combination
may assume that fy j jj 2 I 0 g is linearly independent.
That is,
fy is linearly independent;  i  0 (i 2 I 0 )
fy j jj 2 I 0 g is linearly independent: (78)
and hence we also have the following representation of N 0 (x):
One could rewrite the distance formulas (72), (73), (75), and (76), based on either (77) or (79).
(b) In the particular case when I is nite, (4) satises the BCQ (see the observation before Example
1), and hence Corollary 5(b) reduces to [17, Remark 8(a)].
The following theorem shows that if the BCQ holds, then the distance of a point to the solution
set S of an arbitrary convex inequality system (1) is equal to the distance of that point to the
solution set of some nite subsystem of (1).
Theorem 9 If (1) satises the BCQ and b
x is the projection of x onto S, then there exists
with
Jj < +1; such that
where
J)g:
Proof. Choose any
J  I(b x) for which the rst max in (73) is attained. Then, applying Theorem 8
to the inequality system
and to its solution set S
J (of (81)), we obtain




dist (x; S
which, since S  S
J (by (2) and (81)), yields (80). 2
Remark 13 In the particular case when I is nite and each g i is an ane function, (1) satises
the BCQ, and hence Theorem 9 yields [2, Corollary 1.1].



--R

On the Kuhn-Tucker theorem
The distance to a polyhedron.

On systems of linear inequalities.



Application of a theorem of E.
bounds for convex inequality systems.
Abadie's constraint quali
Asymptotic constraint quali

Convex programming in a normed space

Theory of linear and integer programming.
The theory of best approximation and functional analysis.
Duality for optimization and best approximation over

Generalizations of some fundamental theorems in linear inequalities.
--TR

--CTR
Chong Li, Strong uniqueness of the restricted Chebyshev center with respect to an RS-set in a Banach space, Journal of Approximation Theory, v.135 n.1, p.35-53, July 2005
Mara J. Cnovas , Marco A. Lpez , Juan Parra, Stability in the Discretization of a Parametric Semi-Infinite Convex Inequality System, Mathematics of Operations Research, v.27 n.4, p.755-774, November 2002
convex Farkas-Minkowski systems;distance formulas;constraint qualifications;semi-infinite inequality systems