This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA

Download & View **Solving Strategies And Well-posedness In Linear Semi-infinite Programming** as PDF for free.

**Words:**10,165**Pages:**20

Annals of Operations Research 101, 171–190, 2001 2001 Kluwer Academic Publishers. Manufactured in The Netherlands.

Solving Strategies and Well-Posedness in Linear Semi-Infinite Programming ∗ M.J. CÁNOVAS [email protected] Operations Research Center, Miguel Hernández University of Elche, E-03202 Elche (Alicante), Spain M.A. LÓPEZ ∗∗ [email protected] Department of Statistics and Operations Research, University of Alicante, E-03071 Alicante, Spain J. PARRA [email protected] Operations Research Center, Miguel Hernández University of Elche, E-03202 Elche (Alicante), Spain M.I. TODOROV [email protected] Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias Físico-Matemáticas, Apdo. postal 1152, C.P. 72000 Puebla, Pue., Mexico

Abstract. In this paper we introduce the concept of solving strategy for a linear semi-infinite programming problem, whose index set is arbitrary and whose coefficient functions have no special property at all. In particular, we consider two strategies which either approximately solve or exactly solve the approximating problems, respectively. Our principal aim is to establish a global framework to cope with different concepts of well-posedness spread out in the literature. Any concept of well-posedness should entail different properties of these strategies, even in the case that we are not assuming the boundedness of the optimal set. In the paper we consider three desirable properties, leading to an exhaustive study of them in relation to both strategies. The more significant results are summarized in a table, which allows us to show the double goal of the paper. On the one hand, we characterize the main features of each strategy, in terms of certain stability properties (lower and upper semicontinuity) of the feasible set mapping, optimal value function and optimal set mapping. On the other hand, and associated with some cells of the table, we recognize different notions of Hadamard well-posedness. We also provide an application to the analysis of the Hadamard well-posedness for a linear semi-infinite formulation of the Lagrangian dual of a nonlinear programming problem. Keywords: stability, Hadamard well-posedness, semi-infinite programming, feasible set mapping, optimal set mapping, optimal value function AMS subject classification: 90C34, 15A39, 49J53, 52A40

1.

Introduction

In this paper we present the concept of solving strategy in order to offer an unified treatment of different notions of Hadamard well-posedness for the linear optimization ∗ This research was partially supported by grants PB96-0335 and PB98-0975 from DGES and GV-C-CN-

10-067-96 from Generalitat Valenciana.

∗∗ Corresponding author.

172

problem, in Rn ,

CÁNOVAS ET AL.

π : Inf c x | at x bt , t ∈ T ,

where c, x and at belong to Rn , bt ∈ R, and y denotes the transpose of y ∈ Rn . π is represented by the pair (c, σ ), where the constraints system, σ := {at x bt , t ∈ T }, is alternatively represented by ((at , bt )t ∈T ). We shall not assume any structure for T , the index set of σ (so, the functions t → at and t → bt have no particular property). When T is infinite, π is a linear semi-infinite programming problem (LSIP). The set of all the problems π = (c, σ ), with c = 0n , and whose constraint systems have the same index set T , will be denoted by . When different problems are considered in , they and their associated elements will be distinguished by means of sub(super)scripts. So, if π1 also belongs to , we write π1 = (c1 , σ1 ) and σ1 := {(at1 ) x bt1 , t ∈ T }. Obviously, the parameter space can be identified with (Rn \{0n }) × (Rn × R)T , where the set of possible constraint systems is itself identified with (Rn × R)T . The solving strategies for π , formally introduced in section 3, are based on the idea of approaching π by means of sequences of problems, in , converging to π . The notion of convergence in is leaned on the extended distance δ : × → [0, +∞], given by 1 1 at at δ(π1 , π ) := max c − c∞ , sup b1 − bt . t ∈T ∞ t In this way, is endowed with the uniform convergence topology. (, δ) is a Hausdorff space, whose topology satisfies the first axiom of countability (i.e., convergence is established by means of sequences, since each point has a countable base of neighbourhoods). Given π ∈ , we will denote by F its feasible set, by v its optimal value, and by F ∗ its optimal set. We also use the (lower) level set L(α) := {x ∈ F | c x α}, α ∈ R (obviously, L(v) = F ∗ ). Since F and L(α), α ∈ R, are given as intersection of closed half-spaces, they are obviously closed and convex sets in Rn . We consider, in , the subsets c , of consistent problems (i.e., having a non-empty feasible set), b , of bounded problems (i.e., with finite optimal value), and s , of solvable problems (i.e., whose optimal value is attained). We will write v = −∞ if π is unbounded (i.e., when c x is not bounded from below on F ), and v = +∞ when π is inconsistent (i.e., when F = ∅). This paper approaches the stability and well-posedness of the LSIP problem, following the tradition of the MPDP Symposia (see, for instance, [12], presented to the first symposium, held on May 24–25, 1979). In section 3 we present two particular solving strategies for a solvable problem π , by means of proximal bounded problems or solvable problems, respectively. We also introduce three desirable properties for a general solving strategy. The first two ones are analyzed, for both strategies, in section 4, and the last one is studied in section 5, in connection with certain notions of well-posedness of π . Section 6 organizes the main results of the paper in a summary-table, emphasizing

SOLVING STRATEGIES

173

the high relationship held between the notions of well-posedness provided in the paper and some stability properties of the problem already analyzed in [7] and [3]. We make use of this relationship in an application to the analysis of the Hadamard well-posedness of the Lagrangian dual associated to a nonlinear programming problem. 2.

Preliminaries

This section collects some results needed later. First, we introduce some notation used throughout the paper. Given ∅ = X ⊂ Rp , by conv(X), cone(X), span(X), O + (X) and X o we denote the convex hull of X, the conical convex hull of X, the linear hull of X, the recession cone of X (assumed that X is convex), and the dual cone of X (i.e., X o = {y ∈ Rp | y x 0 for all x ∈ X}), respectively. It is assumed that cone(X) always contains the zero-vector, 0p, and, so, cone(∅) = {0p }. The Euclidean and Chebyshev norms of x ∈ Rp , will be x and x∞ , respectively. The unit open ball, in Rp , for the Euclidean norm is represented by B. From the topological side, if X is a subset of any topological space, int(X), cl(X) and bd(X) represent the interior, the closure and the boundary of X, respectively. Finally, limr should be interpreted as limr→∞ , and {zr } is used to represent a sequence. At this moment, we recall some stability properties of π . More precisely, we will refer to some continuity properties of the feasible set mapping, F, the optimal value function, ϑ, and the optimal set mapping, F ∗ . The first one assigns to each problem π its feasible set (i.e., F(π ) = F ), the second one assigns to π its optimal value (i.e., ϑ(π ) = v), and the last one assigns to π the (possibly empty) optimal set (i.e., F ∗ (π ) = F ∗ ). Next, we recall some well-known continuity concepts for set-valued mappings. If Y and Z are two topological spaces and M : Y ⇒ Z is a set-valued mapping, we shall consider the following properties of M: If both spaces verify the first axiom of countability, we say that M is closed at y ∈ Y if for all sequences {y r } ⊂ Y and {zr } ⊂ Z satisfying limr y r = y, limr zr = z and zr ∈ M(y r ), one has z ∈ M(y). The mapping M is lower semicontinuous (lsc, for short) at y ∈ Y if for each open set W ⊂ Z such that W ∩ M(y) = ∅ there exists an open set U ⊂ Y, containing y, such that W ∩ M(y 1 ) = ∅ for each y 1 ∈ U . M is said to be upper semicontinuous (usc, in brief) at y ∈ Y if for each open set W ⊂ Z such that M(y) ⊂ W there exists an open neighbourhood of y in Y, U , such that M(y 1 ) ⊂ W for every y 1 ∈ U . It has been established in [7] that F is closed at any consistent problem π . Moreover, it is shown in [8] that the boundedness of F implies the upper semicontinuity of F at π . The following theorem gathers some characterizations of the lower semicontinuity of F at π , given in [7, theorem 3.1]. The last statement in this theorem refers to the so-called strong Slater condition, which is said to be satisfied by a problem π ∈ c if

174

CÁNOVAS ET AL.

there exist ρ > 0 and x ∈ Rn such that at x bt + ρ for all t ∈ T . Then, x is called an SS-element of π . Theorem 2.1. If π = (c, σ ) ∈ c , then the following statements are equivalent: (i) F is lsc at π ; (ii) π ∈ int(c ); at / cl conv , t ∈T ; (iii) 0n+1 ∈ bt (iv) π satisfies the strong Slater condition. The next theorem [6, corollary 9.3.1] characterizes the boundedness of the optimal set. In it, M denotes the first moment cone associated to σ , given by M := cone({at , t ∈ T }). It can immediately be checked that all the non-empty level sets, L(α), (and, in particular, F ∗ if π is solvable) have the same recession cone, given by {at , t ∈ T ; −c}o . Theorem 2.2. Let π ∈ c . The following statements are equivalent: (i) F ∗ is non-empty and bounded; (ii) {at , t ∈ T ; −c}o = {0n }; (iii) c ∈ int(M). The boundedness of the optimal set entails itself a nice stability property of the problem π , according to the following lemma [3, lemma 4.1], where intc (s ) denotes the interior of s in the topology relative to c . Lemma 2.3. π ∈ intc (s ) if and only if F ∗ is a non-empty bounded set. The following results [3, theorems 4.2 and 5.1] deal with the stability properties of the optimal value function and the optimal set mapping. Theorem 2.4. Let π = (c, σ ) ∈ c . Then: (i) ϑ is usc at π if and only if F is lsc at π . (ii) If F ∗ is a non-empty bounded set, ϑ will be lsc at π . If π ∈ b , the converse statement holds. Theorem 2.5. Given π ∈ s , the following propositions hold: (i) F ∗ is closed at π if and only if either F is lsc at π or F = F ∗ . (ii) If F ∗ is usc at π , then F ∗ is closed at π . The converse statement holds if F ∗ is bounded. (iii) F ∗ is lsc at π if and only if F is lsc at π and F ∗ is a singleton.

SOLVING STRATEGIES

175

Section 4 in [3] establishes the connection between the mentioned stability properties of π and certain concept of Hadamard well-posedness for this problem, which was traced out from [4]. Given {πr = (cr , σr )} ⊂ b such that limr πr = π , the sequence {x r } is said to be an asymptotically minimizing sequence (a.m.s., in brief) for π , associated with {πr }, if x r ∈ Fr for all r, and limr cr x r − vr = 0, i.e., as r increases, x r approximately solves the approximating problem πr . The problem π ∈ s will be Hadamard well-posed (Hwp, for short) if for each x ∗ ∈ F ∗ and for each possible sequence {πr } ⊂ b converging to π , there exists at least an associated a.m.s. converging to x ∗ . The following theorem (obtained from [3, theorem 4.3]) characterizes this property. Here, ϑb denotes the restriction of ϑ to b . Theorem 2.6. Let π = (c, σ ) ∈ s . Then, π is Hwp if and only if ϑb is continuous at π and, either F is lsc at π or F is a singleton. Finally, we recall a concept to be applied in section 5. Given a consistent system σ := {at x bt , t ∈ T }, with solution set F , we say that a x b is a consequence of σ if it is satisfied at each point of F , i.e., a z b for every z ∈ F . The so-called nonhomogeneous Farkas lemma [11], characterizes the linear inequalities a x b which are consequences of a consistent system σ := {at x bt , t ∈ T } as those satisfying 0n a at . (2.1) , t ∈ T; ∈ cl cone bt −1 b ) If we introduce the cone, R(T + , of all the functions λ : T → R+ taking positive values only at finitely many points of T , (2.1) is equivalent to the existence of sequences ) {λr } ⊂ R(T + and {µr } ⊂ R+ , such that

a 0n a t r , λt + µr = limr bt −1 b t ∈T

and where λr = (λrt )t ∈T , r = 1, 2, . . . . 3.

Solving strategies

Let π ∈ s be given. Let & be a non-empty subset of c such that π is an accumulation point of &, and let A& denote the set of all the sequences {πr } ⊂ & converging to π . We define a solving strategy for π based on & as a set-valued mapping N S : A& ⇒ Rn

176

CÁNOVAS ET AL.

satisfying the following properties: (S1) {x r } ∈ S ({πr }) implies x r ∈ Fr , for all r ∈ N; (S2) If {x r } ∈ S({πr }) and {x rk } is a subsequence of {x r }, then {x rk } ∈ S({πrk }). In this paper we consider two particular solving strategies for the problem π based on b and s , motivated, respectively, by the idea of solving either approximately or exactly proximal problems. Note that, for an arbitrarily chosen π = (c, σ ) ∈ s , both, b and s , satisfy the conditions required to & in the previous definition (just consider πr = ((1 + 1/r)c, σ ), r ∈ N). For the sake of brevity, we write Ab and As instead of Ab and As . In the first strategy, N Sb : Ab ⇒ Rn , Sb ({πr }) represents the set of all the asymptotically minimizing sequences associated with {πr }. The second one, N Ss : As ⇒ Rn , is defined by Ss ({πr }) = {{x r } ⊂ Rn | x r ∈ Fr∗ , r = 1, 2, . . .}. We approach the well-posedness of the problem π in terms of the behaviour of these two strategies, which is qualified by means of the following definitions. If S is a solving strategy for π based on &, we say that S is admissible if, for all {πr } ∈ A& , any cluster point of any sequence {x r } ∈ S({πr }), belongs to F ∗ . S will be efficient if, for all {πr } ∈ A& , any sequence {x r } ∈ S({πr }) has at least a cluster point in F ∗ . Finally, S is said to be complete if, for all x ∗ ∈ F ∗ and for all {πr } ∈ A& , there exists a sequence {x r } ∈ S({πr }), which has x ∗ as a cluster point. As a straightforward consequence of these definitions, we observe that every efficient solving strategy for π (based on &), S, is admissible. In fact, let us consider an arbitrary sequence {πr } ∈ A& , and suppose that x is a cluster point of certain {x r } ∈ S({πr }), i.e., x = limk x rk for some subsequence {x rk } of {x r }. Applying condition (S2) in the definition of solving strategy and the current assumption, we conclude x ∈ F ∗ . 4.

Admissibility and efficiency

The first theorem of this section characterizes the admissibility of the strategies under consideration, Sb and Ss . Theorem 4.1. Let π ∈ s and consider the solving strategies, for π , Sb and Ss . Then the following statements are equivalent: (i) Sb is admissible; (ii) Ss is admissible; (iii) F ∗ is closed at π .

SOLVING STRATEGIES

177

Proof. First we prove (i) ⇒ (ii). Let {πr } ∈ As , and take {x r } ∈ Ss ({πr }). Since, As ⊂ Ab and, obviously, {x r } ∈ Sb ({πr }), we conclude from (i) that every cluster point of {x r } belongs to F ∗ . The statement (ii) ⇒ (iii) is a trivial consequence of the definitions. Finally, we prove (iii) ⇒ (i). Let {πr } ∈ Ab and {x r } ∈ Sb ({πr }). If x is a cluster point of {x r }, we may assume from condition (S2), and without loss of generality, that x = limr x r . By statement (i) in theorem 2.5, we first suppose F = F ∗ . Then, the closedness of F at π (established in [7]) implies x ∈ F = F ∗ , and we obtain (i) in this case. Now, assume that F is lsc at π . Since {x r } is an a.m.s. for π , associated with {πr }, one has c x = limr cr x r = limr vr . Applying theorem 2.4(i), we have c x v, and then x ∈ F ∗ .

The equivalence between the efficiency of Sb and Ss is established in the next theorem. Theorem 4.2. Let us consider the solving strategies, for π ∈ s , Sb and Ss . Then the following statements are equivalent: (i) Sb is efficient; (ii) Ss is efficient; (iii) F ∗ is closed at π and F ∗ is bounded; (iv) ϑb is continuous at π and F ∗ is bounded. Proof. The proposition (i) ⇒ (ii) is immediate and follows from the same idea of (i) ⇒ (ii) in the previous theorem. Theorem 4.1 allows us to state that (ii) implies that F ∗ is closed at π (remember that efficiency entails admissibility). If F ∗ were unbounded, then we could consider the constant sequence πr = π , for all r ∈ N, and a sequence {x r } ⊂ F ∗ such that limr x r = +∞. Obviously, {πr } ∈ As and {x r } ∈ Ss ({πr }); however {x r } has no cluster points, which contradicts (ii). Hence, we have already established (ii) ⇒ (iii). Next we prove (iii) ⇒ (iv). If {πr } ⊂ b converges to π , lemma 2.3 establishes the existence of r0 such that πr is solvable if r r0 . For each r r0 , we take x r ∈ Fr∗ . Thus, vr = (cr ) x r if r r0 , and we are going to prove that limr vr = v. First we prove that {x r }rr0 is bounded, entailing the boundedness of {vr }rr0 . In fact, applying theorem 2.5(ii), F ∗ will be usc at π . So, if W is any bounded neighbourhood of F ∗ , we may assume r0 taken such that x r ∈ W , for all r r0 . Now, we prove that if {vrk } (r1 r0 ) is any convergent subsequence of {vr }, then there must be limk vrk = v. Hence, we have limr vr = lim infr vr = lim supr vr = v and, so, continuity of ϑb at π .

178

CÁNOVAS ET AL.

Assume that {vrk } converges to v. We write vrk = (crk ) x rk , with x rk ∈ Fr∗k . The sequence {x rk } is bounded, and we assume w.l.o.g. that limk x rk = x. The closedness of F ∗ implies x ∈ F ∗ and we get v = limk vrk = limk crk x rk = c x = v. Finally, we are going to prove (iv) ⇒ (i). Let us consider {πr } ∈ Ab , and take {x r } ∈ Sb ({πr }). In a first step, we see that {x r } is bounded. Otherwise, we would have a subsequence {x rk } such that limk x rk = ∞ (so, we can assume x rk = 0n , for all k). The sequence {x rk −1 x rk } will contain a subsequence, denoted in the same way for the sake of brevity, converging to y ∈ bd(B). Since {x rk } is an a.m.s. for π , associated with {πrk }, we have −1 r r c k x k − vrk = c y, 0 = limk x rk since limk vrk = v. Moreover, for each t ∈ T , one has −1 −1 at y = limk atrk x rk x rk limk x rk btrk = 0, because limk btrk = bt . Thus y ∈ O + (F ∗ )\ 0n , contradicting the boundedness of F ∗ . Once we have proved {x r } is bounded, it will have, at least, a cluster point x. We write x = limk x rk , for some subsequence {x rk } of {x r }, and c x = limk crk x rk = limk vrk = v. So, x ∈ F ∗ .

Properties of the solving strategies Sb and Ss can be seen as properties of the problem π itself. In order to emphasize this approach, we give the following definition. Definition 4.3. The problem π ∈ s is called efficiently Hadamard well-posed (e-Hwp, for short) if it verifies any one of the equivalent statements given in theorem 4.2. We finish this section with an immediate corollary of the previous results. Corollary 4.4. Let π ∈ s . If F ∗ is bounded, then the following conditions are equivalent: (i) Sb is admissible; (ii) Ss is admissible; (iii) Sb is efficient; (iv) Ss is efficient.

SOLVING STRATEGIES

5.

179

Completeness

This section is devoted to characterize the completeness of the solving strategies Sb and Ss in connection with two notions of well-posedness. We shall start with the study of Sb . Theorem 5.1. Let π ∈ s , and consider the solving strategy Sb for the problem π . Then, Sb is complete if and only if π is Hwp. Proof. The “if” part is an immediate consequence of the definitions. Now, assuming that Sb is complete, we will prove that π is Hwp; which is equivalent to show that ϑb is continuous at π and, either F is lsc at π or F is a singleton (see theorem 2.6). If ϑb is not continuous at π , there will exist {πr } ∈ Ab , such that the sequence {vr } does not converge to v. Consequently, there exist a subsequence of {vr }, {vrk }, and ε > 0, such that |vrk − v| ε, for k = 1, 2, . . . . Let x ∗ ∈ F ∗ be given. By hypothesis, there will exist a sequence {x rk } ∈ Sb ({πrk }) having x ∗ as a cluster point. So, for some subsequence {x rks } of {x rk }, one has x ∗ = lims x rks , and then lims vrks = lims crks x rks = c x ∗ = v, which contradicts the assumption about {vrk }. Next, assuming that F is not lsc at π and, simultaneously, F is not a singleton, we shall get a contradiction. Since F is assumed to be non-lsc at π , condition the (iii) in p ) , verifying λ = 1, orem 2.1 must fail. Then, there exists a sequence {λp } ⊂ R(T + t ∈T t p = 1, 2, . . . , and such that p a t λt . (5.1) 0n+1 = limp bt t ∈T

First, we prove that F ∗ has to be bounded. Suppose that it is not the case, and take x ∗ ∈ F ∗ and u ∈ O + (F ∗ ) with u = 1. Then define µr = 1/(u x ∗ + r), with r sufficiently large, say r r0 for certain r0 ∈ N, to guarantee the positiveness of the denominator, and take, for r r0 , cr := c − µr u and y r := x ∗ + ru. Obviously, y r ∈ F ∗ and (cr ) y r = v − 1. Define also the systems 1 r v−1 at + c x bt + , t ∈ T , r r0 , σr := kr kr where the constants kr , r r0 , are chosen in such a way that r c < 1 and v − 1 < 1 . k r k r r ∞ r Finally, we shall introduce the associated problems πr := (cr , σr ), r r0 , which obviously verify limrr0 πr = π and πr ∈ c (because y r ∈ Fr ).

180

CÁNOVAS ET AL.

Then we have, for each r r0 , r p at + 1 cr 1 c kr , λt = limp v−1 v −1 bt + kr kr t ∈T and the non-homogeneous Farkas lemma allows us to conclude that (cr ) x v − 1 is a consequence of σr , which in fact entails y r ∈ Fr∗ and vr = v − 1. Thus, we have attained a contradiction with the continuity of ϑb at π . On the other hand, since we are assuming that F is not a singleton, we can take an optimal point x ∗ ∈ F ∗ and an arbitrary y ∈ F \{x ∗ }. Define w := y − x ∗ and, associated with each r ∈ N, take a positive scalar lr satisfying 1 w < 1 and 1 w y < 1 . r l r lr r ∞ Let us introduce, for each r ∈ N, the problem π r = (c, σ r ) with 1 1 σ r := at + w x bt + w y, t ∈ T . lr lr Obviously δ(π r , π ) < 1/r and, so, limr π r = π . Moreover, y ∈ F r (= F(π r )), for every r, and w x w y is a consequence of each σ r , since (5.1) implies p at + 1 w 1 w lr = . λt limp lr w y bt + l1r w y t ∈T According to lemma 2.3, the boundedness of F ∗ entails that {π r }rr0 ⊂ s , for a certain r0 , and, hence, {π r }rr0 ∈ Ab . However, the set W := {x ∈ Rn | w x < w y} is an open neighbourhood of x ∗ such that F r ∩ W = ∅, for all r ∈ N. So, x ∗ cannot be a cluster point of any sequence {x r } ∈ Sb {π r }, and we attain the aimed contradiction with the completeness of Sb . By means of the following two results, it turns out that, under the existence of at least n constraints, the completeness of Ss implies the unicity of the optimal solution. Lemma 5.2. Let us consider the solving strategy Ss for a given π ∈ s . If |T | n and Ss is complete, then F ∗ contains no lines. Proof. Assume that |T | n, Ss is complete and F ∗ contains, at least, a line. Fix x ∗ ∈ F ∗ and take u ∈ Rn , u = 1, such that x ∗ + λu ∈ F ∗ , for all λ ∈ R. Since c x v is a consequence of σ , we can apply the non-homogeneous Farkas lemma, and ) (2.1) leads us to the existence of sequences {λr } ⊂ R(T + and {µr } ⊂ R+ satisfying at 0n c r . (5.2) λt + µr = limr bt −1 v t ∈T

SOLVING STRATEGIES

181

Multiplying both sides of (5.2) by

x∗

we get ∗ r ∗ λt at x − bt + µr , 0 = c x − v = limr −1

t ∈T

and then limr µr = 0. So, we can eliminate the last term in (5.2). We can also assume w.l.o.g. that, for all r ∈ N, c at < 1. λrt v − bt ∞ r t ∈T In the following paragraphs we shall consider a fixed index r. At this time, let us note that dim span{at : t ∈ T } < n (because u is orthogonal to this set) and, thus, dim span{ abtt : t ∈ T } < n + 1. According to Carathéodory s theorem we can suppose that |supp λr | n (where supp λr is the support of λr , i.e., supp λr = {t ∈ T : λrt > 0}). Pick n different indices t1r , t2r , . . . , tnr such that supp λr ⊂ {t1r , t2r , . . . , tnr }, and let us define cr :=

n

λrtr atir . i

i=1

We can redefine, if necessary, {λrtr }i=1,2,...,n , adding to each one a sufficiently small posi itive number, to get r λtir > 0, i = 1, 2, . . . , n, n c

atir r < 2. λt r v − r i b r ti i=1 ∞ In particular, we have c − cr ∞ < 2/r. Let kr be a positive number such that kr r, u x ∗ + kr > 0, and µri < 1/r, for all i = 1, 2, . . . , n, where µri :=

(atir ) x ∗ − btir u x ∗ + kr

,

i = 1, 2, . . . , n.

So, if we define y r := x ∗ + kr u, we have (atir − µri u) y r = btir , for i = 1, 2, . . . , n. Now, let us define, for i = 1, 2, . . . , n, wir := atir − µri u. So, r w − at r = µr u∞ < 1 , i = 1, 2, . . . , n. i i i ∞ r r r We can slightly modify the set {w1 , . . . , wn } to get a linearly independent system of vectors {atrr , . . . , atrnr }. The process runs as follows: 1 r if w1r = 0n , w1 , atrr : = 1 1 (1, 0, . . . , 0) , if w r = 0 , n 1 r

182

CÁNOVAS ET AL.

atrr = j+1

r wj +1 , wjr +1 +

if wjr +1 ∈ / span{atrr , . . . , atrr }, 1

j

1 r u , if wjr +1 ∈ span{atrr , . . . , atrr }, j 1 (kr )2 j +1

where urj +1 is any vector belonging to {atrr , . . . , atrr }⊥ ∩ bd(B), and j = 1, 2, . . . , n − 1. 1 j Moreover, we can observe that r a r − at r < 2 , i = 1, 2, . . . , n. ti i ∞ r The next step consists of slightly modifying the set {bt1r , . . . , btnr } in order to get a new set {btrr , . . . , btrnr }, such that (atrr ) y r = btrr , i = 1, 2, . . . , n. Hence, we define 1 i i r r r r r r bt r := at r − wi y + wi y = btir + atrr − wir y r . i

i

=

i

(in which case = btir ), or r 1 r ∗ 1 r ∗ 1 r r r u (x + k u) = x + u u u. at r − wi y = r i i i (kr )2 (kr )2 kr i

Note that, either

atrr i

wir

btrr i

In the second case, we have ∗ r b r − bt r x + 1 . ti i (kr )2 kr

Finally, we define atr := at and btr := bt , if t ∈ T \ {t1r , . . . , tnr }. In this way we obtain a system σr := {(atr ) x btr , t ∈ T } verifying ar 2 x ∗ 1 at t max , + . supt ∈T r − bt bt ∞ r (kr )2 kr Next, we define cr :=

n

λrtr atrr . i

i

i=1

Remember that {atrr , . . . , atrnr } is a basis of Rn , and λrtr > 0, for i = 1, 2, . . . , n. We can 1 i also observe n n 2 2 c − cr c − cr + cr − cr < + 1+ λrtr atir − atrr ∞ λrtr . ∞ ∞ ∞ i i i r r i=1 i=1

So, if we are able to prove that the sequence { ni=1 λrtr }r∈N is bounded, and if we define i πr := (cr , σr ), r ∈ N, we shall obtain limr πr = π . By assumption, Ss is complete and F ∗ is unbounded. Next we shall prove that F has to be lsc at π . If it is not the case, proceeding as in the proof of theorem 5.1, we can vr = v − 1 for r = 1, 2, . . . , so, x ∗ cannot be a find a sequence { πr } ∈ As such that r πr }), which represents a contradiction. cluster point of any sequence { x } ∈ Ss ({

SOLVING STRATEGIES

183

Applying theorem 2.1, the lower semicontinuity of F at π entails the existence of an SS-element, x, of σ ; i.e., there exists a scalar ρ > 0 such that at x − bt ρ, for all t ∈ T . Since n atir c r λt r , = limr i btir v i=1

one has c x − v = limr

n

n λrtr (atir ) x − btir ρ lim supr λrtr . i

i

i=1

i=1

Hence, lim supr ni=1 λrtr (c x − v)/ρ, which implies the boundedness of { ni=1 λrtr }r∈N. i i At this moment, we summarize what we have. We have built a sequence {πr } ⊂ , such that limr πr = π . Also by construction, we have y r ∈ Fr , for all r ∈ N. On the other hand, r n at r cr r i λt r = , i (cr ) y r btrr i=1 i

= (atrr ) y r , i r r

i = 1, 2, . . . , n. According to the non-homogeneous Farkas lemma since r (c ) x (c ) y turns out to be a consequence of σr . Hence, y r ∈ Fr∗ , for all r ∈ N. In fact, Fr∗ = {y r }, for all r ∈ N, because the system σ r := {(atrr ) x btrr : i = 1, 2, . . . , n} i i has y r as the only point satisfying the Kuhn–Tucker conditions for the ordinary LP∗ problem π r = (cr , σ r ). So, F r = {y r }, which implies Fr∗ = {y r }, for all r ∈ N. Let us finish the proof of the lemma. It is obvious that limr y r = +∞. Hence, r {y } has no cluster points. In particular, x ∗ is not a cluster point of {y r }. Since {y r } is the unique element of Ss ({πr }), we reach a contradiction with the completeness of Ss . btrr i

Theorem 5.3. Let us consider the solving strategy Ss for a given π ∈ s . If |T | n and Ss is complete, then F ∗ is a singleton. Proof. If we suppose that F ∗ contains more than one point, namely x ∗ and y ∗ , we shall get a contradiction. Because of the previous lemma, we may assume that F ∗ contains no lines. This fact implies that the dimension of span{at , t ∈ T } is n (observe that F ∗ contains a line if and only if F does, since

n π ∈ s ⊂ b ). Let {at1 , at2 , . . . , atn } be a basis of span{at , t ∈ T }, and define d := i=1 ati . It is obvious that the homogeneous system at y 0, t ∈ T ; d y 0 has no non-trivial solution (if y = 0n were a solution, one would conclude y ∈ {at , t ∈ T }⊥ ). Now let us consider the system σ := at x bt , t ∈ T ; d x d y ∗ , σ ). provided that d y ∗ d x ∗ (otherwise, we shall replace y ∗ by x ∗ , in

184

CÁNOVAS ET AL.

σ is a system, in Rn , with index set T := T ∪ {t0 }, t0 ∈ / T , and whose solution ) and bounded, since , is non-empty (y ∗ ∈ F set, F ) = y ∈ Rn | at y 0, t ∈ T , d y 0 = {0n }. O + (F , will be usc at Accordingly, the corresponding feasible set mapping, F σ , entailing the boundedness of the solution set, F1 , of the system σ1 := at x bt , t ∈ T ; (d + εu) x (d + εu) y ∗ , where u = x ∗ − y ∗ and ε is taken positive and sufficiently small. Next, we consider the sequence {πr := (c + (1/r)w, σ )}, where w := d + εu. Obviously, limr πr = π and πr is solvable, for all r, as consequence of the non-emptiness and boundedness of the associated (lower) level sets 1 ∗ 1 ∗ 1 Lr v + w y = x ∈ F c + w x v + w y , r r r 1 . which are all contained in F Finally, let us take the open set W = {x ∈ Rn | w x > w y ∗ }. It can be easily seen that the assumption d y ∗ d x ∗ implies x ∗ ∈ W . Moreover, if x ∈ F ∩ W , we have 1 1 c + w x > c y ∗ + w y ∗ = cr y ∗ , r r and, so, Fr∗ ∩ W = ∅. Hence, x ∗ cannot be a cluster point of any sequence {x r } ∈ Ss ({πr }), contradicting the completeness of Ss . Some authors consider that any kind of well-posedness should entail the unicity of the optimal solution, which will be approximated by optimal solutions of proximal problems. Next, we are going to establish the equivalence between the completeness of the solving strategy Ss , for the problem π ∈ s , viewed as a stability property of the problem itself, and certain concept of Hadamard well-posedness of this problem (more restrictive at a first glance), which can be found, for instance, in [10]. As a remarkable fact, we recall that the uniqueness of the optimal solution of π , assuming the existence of, at least, n constraints, is not an hypothesis in the completeness of the solving strategy Ss , but a consequence. We give the following definition: Definition 5.4. The problem π ∈ s is called strongly Hadamard well-posed (s-Hwp, in brief) if F ∗ is a singleton (i.e., F ∗ = {x ∗ }) and, for every {πr } ∈ As and every sequence {x r } ∈ Ss ({πr }), one has limr x r = x ∗ . Theorem 5.5. Let us consider the solving strategy Ss for a given π ∈ s . Assume |T | n. Then, the following statements are equivalent: (i) π is s-Hwp; (ii) Ss is complete.

SOLVING STRATEGIES

185

Proof. The statement (i) ⇒ (ii) is a trivial consequence of the definitions. Now, assume the completeness of Ss . Since |T | n, theorem 5.3 establishes the uniqueness of the optimal solution. Put F ∗ = {x ∗ }, and fix any {πr } ∈ As and any {x r } ∈ Ss ({πr }). We prove that x ∗ = limr x r through the following reasoning in two steps: Step 1. The sequence {x r } is bounded. Otherwise, it will have a subsequence {x rk }, such that limk x rk = ∞ and {x rk −1 x rk } converges to a certain non-zero vector z belonging to O + (F ) (following the same reasoning that in the proof of implication (iv) ⇒ (i) in theorem 4.2). Applying (ii), there must exist a sequence {y rk } ∈ Ss ({πrk }), having x ∗ as a cluster point. We can assume, without loss of generality, that {y rk } converges to x ∗ . So, −1 −1 c z = limk crk x rk x rk = limx rk crk x rk k r −1 r r k k k = limk x c y = 0, and z belongs actually to O + (F ∗ ), contradicting the boundedness of F ∗ . Step 2. Let us prove that every convergent subsequence of {x r } converges to x ∗ and, consequently, the sequence itself converges to x ∗ . If we suppose that {x rk } converges to x, we can repeat the previous argument and take a sequence {y rks } converging to x ∗ , and then c x = lims (crks ) x rks = lims (crks ) y rks = c x ∗ . Thus x is optimal for π , i.e., x = x∗. The following corollary gathers some equivalent statements for a problem π with a unique optimal solution. Corollary 5.6. Let us consider π ∈ s such that F ∗ = {x ∗ }. Then the following statements are equivalent: (i) Ss is efficient (or admissible); (ii) Ss is complete; (iii) π is s-Hwp; (iv) Sb is efficient (or admissible); (v) Sb is complete; (vi) π is Hwp; (vii) π is e-Hwp. Proof. It is immediate that, under the assumption, F ∗ = {x ∗ }, every efficient solving strategy for π is complete. So, we have (i) ⇒ (ii) and (iv) ⇒ (v). The uniqueness of the optimal solution also implies |T | n, and then, we have (ii) ⇔ (iii) (according to theorem 5.5). The statement (iii) ⇒ (i) is a trivial consequence of the definitions.

186

CÁNOVAS ET AL.

Corollary 4.4 provides (i) ⇔ (iv). Moreover, these two properties are equivalent to (vii), by definition. Theorem 5.1 states the equivalence between (v) and (vi). Finally, [3, corollary 4.4] establishes that, if π is Hwp, then the limit of any convergent a.m.s. for π is an optimal point. This property, together with condition (S2) in the definition of solving strategy, ensures the admissibility of Sb , i.e., we have (vi) ⇒ (iv). Next, we are going to study the completeness of Ss in the remaining case, i.e., when |T | < n. So, let us consider π = (c, σ ) ∈ s , with σ = {ai x bi , 1 i p}, p p < n. We have, for some λ = (λi )1ip ∈ R+ , p ai c λi . = bi v

(5.3)

i=1

Denoting by H the (possibly empty) set {x ∈ Rn | ai x = bi , 1 i p}, we obtain H ⊂ F ∗ . In fact, (5.3) shows that every point of H is a Kuhn–Tucker point of the LP-problem π . The following theorem provides a characterization of the completeness of Ss when |T | < n, which, roughly speaking, says that F ∗ must be “as small as possible”. Theorem 5.7. Assume |T | < n. Then Ss is complete if and only if H = F ∗ and {a1 , . . . , ap } is a linearly independent set. Proof (Sketch). The proof of the “if” condition is routine. For the converse statement, assume that, either H F ∗ , or the set {a1 , . . . , ap } is linearly dependent. In any case, we obtain that at least one of the multipliers, say λp , is equal to zero. Pick two different points x ∗ and y ∗ in F ∗ , and take u := y ∗ − x ∗ . Now, let us consider, for all r ∈ N, the system 1 1 ∗ σr = ai x bi , 1 i p − 1; ap + u x bp + u y , r r for which y ∗ is a solution. Let us define r 1 ap + 1r u c c := + vr v r bp + 1r u y ∗ p−1 1 ap + 1r u ai λi + , = bi r bp + 1r u y ∗

r = 1, 2, . . . .

(5.4)

i=1

Putting πr = (cr , σr ), we have limr πr = π . (5.4) shows that πr ∈ s , for all r ∈ N. In fact, y ∗ ∈ Fr∗ , and so v r is the optimal value of πr . It can easily be realized that, if x ∈ Rn is a cluster point of any sequence in Ss ({πr }), then it must be u x u y ∗ . Since, obviously, u x ∗ < u y ∗ , we attain a contradiction with the completeness of Ss .

SOLVING STRATEGIES

6.

187

Conclusions. Application to the Lagrangian dual problem in nonlinear programming

At this moment we underline the fact that the three desirable properties of both strategies have been entirely characterized in terms of stability properties of the problem, most of them easily checkable in practice (see section 2 and references therein). For instance, when the strong Slater condition and the boundedness (and non-emptiness) of the optimal set are simultaneously satisfied at the nominal problem, π , one has all the desirable properties of both strategies, unless the completeness of Ss , which requires, in addition, the uniqueness of the optimal solution (note that the boundedness and non-emptiness of the optimal set entails |T | n). Moreover, the uniqueness of the optimal solution is dealt in [6, section 10.5]. We summarize the main results given in the paper by means of table 1. This approach also allows us to analyze the Hadamard well posedness of continuous problems, i.e., those in which T is assumed to be a compact Hausdorff space and the functions a(·) and b(·) are continuous on T . The stability theory of the feasible set mapping, optimal value function and optimal set mapping in this context has been developed in [2,5]. When a continuous problem π turns out to be Hwp (in any of the senses given in the table), it can be solved via discretization techniques, by means of repeating a suitable finite set of constraints in order to keep the cardinality of T (note that we can lose the continuity of the coefficient functions). Next, we are going to apply our approach in order to analyze the Hadamard wellposedness of a linear semi-infinite continuous problem, which comes from reformulating the Lagrangian dual of a nonlinear programming problem (inspired in [1, section 6.4]). Let us consider the (primal) nonlinear programming problem Inf f (t) s.t. g(t) 0m ,

(P) t ∈ C,

where C is a compact subset of Rn and the functions f : C → R and g : C → Rm are continuous on C. Assume that the set {t ∈ C | g(t) 0m } is non-empty. The Lagrangian dual of (P) is given by (D) Sup inf f (t) + λ g(t) λ0m t ∈C

Table 1 Well-posedness of the LSIP problem. π ∈ s Admissible Efficient Complete

Sb

Ss F ∗ is closed at π F ∗ is closed at π and F ∗ is bounded (π is e-Hwp) (If |T | n) π is s-Hwp π is Hwp F ∗ = {x ∈ Rn | at x = bt , t ∈ T }, (If |T | < n) {at , t ∈ T } is linearly independent.

188

CÁNOVAS ET AL.

whose value, vD , coincides with the optimal value of the semi-infinite problem Sup z s.t. z f (t) + λ g(t), λ 0m .

(D ) t ∈ C,

The problem (D ) can be translated into the LSIP problem π : Inf c x | at x bt , t ∈ T , where we have used the following notation: x := λz ∈ Rm+1 , T := C ∪{s 1 , s 2 , . . . , s m }, provided that C ∩{s 1 , s 2 , . . . , s m } = ∅ (note that T is compact with the topology induced by Rn ); and g(t) −1 , t ∈ C, 0m , at : = c := −1 e j , t = s j , 1 j m, 0 −f (t), t ∈ C, bt : = 0, t = s j , 1 j m, where ej is the j -th vector of the usual basis of Rm . It is immediate that the coefficient functions t → at and t → bt are continuous on T and, so, π is a continuous problem. Moreover the optimal value of π , v, is equal to −vD . It is easily checked that π is consistent, since, if we arbitrarily choseλ 0m , the λ ∈ F. In function t → f (t)+λ g(t) attains its global minimum on T , z(λ); and, so, z(λ) fact, π is bounded, since the weak duality theorem (see, for instance, [1, theorem 6.2.1]) entails the boundedness of (D). λ is an SS-element of π for any On the other hand, it is immediate that z(λ)−1 λ > 0n (coordinate by coordinate) and, so, F is lsc at π (theorem 2.1). We devote the rest of this section to characterize the boundedness of the optimal set of π . This property, together with the lower semicontinuity of F at π , entails nice stability and well-posedness properties of π (as we commented at the beginning of the section). First we shall establish that the so called characteristic cone associated to σ (the constraint system of π ), 0m+1 at , , t ∈ T; K := cone bt −1 is closed. Because of (2.1), cl(K) is sometimes called the cone of consequences of σ . A linear inequality system whose characteristic cone is closed is called Farkas– Minkowski system. For those consistent problems π = (c, σ ) such that σ is a Farkas– Minkowski system, theorems 5.3(i) and 7.1 in [6] state that π is solvable if and only π

SOLVING STRATEGIES

189

satisfies the Karush–Kuhn–Tucker condition, i.e., there exist a point x ∗ ∈ F and certain indices t1 , . . . , tk ∈ T such that c ∈ cone {ati , 1 i k} and (ati ) x ∗ = bti , for all i = 1, . . . , k. In order closedness of K, it will be sufficient to establish that X := m+1 to show the }), is a compact set which does not contain 0m+2 (see [9]). conv({ abtt , t ∈ T ; 0−1 The compactness of X is a consequence of Mazur’s other hand, if there at Onthe

theorem. (T ) 0m+1 exist λ ∈ R+ and µ 0 such that 0m+2 = t ∈T λt bt + µ −1 , then, looking at the (m + 1)-th coordinate, it must be λt = 0 for all t ∈ C. Now, looking at the j -th coordinate, 1 j m, it must be λs j = 0. Finally, looking at the (m+ 2)-th coordinate, / X. we must have µ = 0. So, 0m+2 ∈ Theorem 6.1. Let π be the problem introduced above. The following statements are equivalent: (i) F ∗ is non-empty and bounded; (ii) cone({g(t), t ∈ C}) contains some element whose coordinates are, all of them, negative. Proof.

(i) ⇒ (ii). By virtue of theorem 2.2, statement (i) is equivalent to g(t) ej 0m ∈ int cone , t ∈ C; , j = 1, . . . , m . c= −1 −1 0

Projecting both sides on its first m coordinates space, and since the projection is an open function, 0m ∈ int(cone{g(t), t ∈ C; ej , j = 1, . . . , m}). So, cone g(t), t ∈ C; ej , j = 1, . . . , m = Rm , and, hence, there exist certain indices t1 , . . . , tk ∈ C and non-negative scalars λt1 , . . . , λtk , µ1 , . . . , µm such that −1m =

k

λti g(ti ) +

m

µj ej ,

j =1

i=1

where −1m denotes the vector of Rm whose coordinates are, all of them, equal to −1. Thus, ki=1 λti g(ti ) has all its coordinates negative. (ii) ⇒ (i). Let us suppose that there exist t1 , . . . , tk ∈ C and certain non-negative scalars λt1 , . . . , λtk such that ki=1 λti g(ti ) has all its coordinates negative. We may

assume, w.l.o.g, that ki=1 λti = 1 (by means of dividing each coefficient by the sum of all of them, which is obviously non-zero). Denoting by −µj to the j -th coordinate of

k i=1 λti g(ti ), 1 j m, we obtain k m 0m g(ti ) ej = . (6.1) λt i µj + 0 −1 −1 i=1

j =1

190

CÁNOVAS ET AL.

Note that µj > 0, j = 1, 2, . . . , m, and there exists certain i0 ∈ {1, . . . , k} such that the whole space Rm+1 . λti0 > 0. Obviously, { g(t−1i0 ) ; e0j , j = 1, . . . , m generates 0m Finally, by means of [6, theorem A.7], (6.1) implies −1 ∈ int(M), and, hence, F ∗ is a non-empty bounded set. References [1] M.S. Bazaraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming: Theory and Algorithms (Wiley, New York, 1993). [2] B. Brosowski, Parametric semi-infinite linear programming I. Continuity of the feasible set and of the optimal value, Math. Programming Study 21 (1984) 18–42. [3] M.J. Cánovas, M.A. López, J. Parra and M.I. Todorov, Stability and well-posedness in linear semiinfinite programming, SIAM J. Optim. 10 (1999) 82–98. [4] A.L. Dontchev and T. Zolezzi, Well-Posed Optimization Problems (Springer, Berlin, 1993). [5] T. Fischer, Contributions to semi-infinite linear optimization, in: Approximation and Optimization in Mathematical Physics, eds. B. Brosowski and E. Martensen (Peter Lang, Frankfurt-am-Main, 1983) pp. 175–199. [6] M.A. Goberna and M.A. López, Linear Semi-Infinite Optimization (Wiley, Chichester, UK, 1998). [7] M.A. Goberna, M.A. López and M.I. Todorov, Stability theory for linear inequality systems, SIAM J. Matrix Anal. Appl. 17 (1996) 730–743. [8] M.A. Goberna, M.A. López and M.I. Todorov, Stability theory for linear inequality systems II: upper semicontinuity of the solution set mapping, SIAM J. Optim. 7 (1997) 1138–1151. [9] R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, NJ, 1970). [10] M.I. Todorov, Generic existence and uniqueness of the solution set to linear semi-infinite optimization problems, Numer. Funct. Anal. Optim. 8 (1985–86) 27–39. [11] Y.J. Zhu, Generalizations of some fundamental theorems on linear inequalities, Acta Math. Sinica 16 (1966) 25–40. [12] S. Zlobec, R. Gardner and A. Ben-Israel, Regions of stability for arbitrarily perturbed convex programs, in: Mathematical Programming with Data Perturbations I, ed. A.V. Fiacco (Dekker, New York, 1982) pp. 69–89.

Solving Strategies and Well-Posedness in Linear Semi-Infinite Programming ∗ M.J. CÁNOVAS [email protected] Operations Research Center, Miguel Hernández University of Elche, E-03202 Elche (Alicante), Spain M.A. LÓPEZ ∗∗ [email protected] Department of Statistics and Operations Research, University of Alicante, E-03071 Alicante, Spain J. PARRA [email protected] Operations Research Center, Miguel Hernández University of Elche, E-03202 Elche (Alicante), Spain M.I. TODOROV [email protected] Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias Físico-Matemáticas, Apdo. postal 1152, C.P. 72000 Puebla, Pue., Mexico

Abstract. In this paper we introduce the concept of solving strategy for a linear semi-infinite programming problem, whose index set is arbitrary and whose coefficient functions have no special property at all. In particular, we consider two strategies which either approximately solve or exactly solve the approximating problems, respectively. Our principal aim is to establish a global framework to cope with different concepts of well-posedness spread out in the literature. Any concept of well-posedness should entail different properties of these strategies, even in the case that we are not assuming the boundedness of the optimal set. In the paper we consider three desirable properties, leading to an exhaustive study of them in relation to both strategies. The more significant results are summarized in a table, which allows us to show the double goal of the paper. On the one hand, we characterize the main features of each strategy, in terms of certain stability properties (lower and upper semicontinuity) of the feasible set mapping, optimal value function and optimal set mapping. On the other hand, and associated with some cells of the table, we recognize different notions of Hadamard well-posedness. We also provide an application to the analysis of the Hadamard well-posedness for a linear semi-infinite formulation of the Lagrangian dual of a nonlinear programming problem. Keywords: stability, Hadamard well-posedness, semi-infinite programming, feasible set mapping, optimal set mapping, optimal value function AMS subject classification: 90C34, 15A39, 49J53, 52A40

1.

Introduction

In this paper we present the concept of solving strategy in order to offer an unified treatment of different notions of Hadamard well-posedness for the linear optimization ∗ This research was partially supported by grants PB96-0335 and PB98-0975 from DGES and GV-C-CN-

10-067-96 from Generalitat Valenciana.

∗∗ Corresponding author.

172

problem, in Rn ,

CÁNOVAS ET AL.

π : Inf c x | at x bt , t ∈ T ,

where c, x and at belong to Rn , bt ∈ R, and y denotes the transpose of y ∈ Rn . π is represented by the pair (c, σ ), where the constraints system, σ := {at x bt , t ∈ T }, is alternatively represented by ((at , bt )t ∈T ). We shall not assume any structure for T , the index set of σ (so, the functions t → at and t → bt have no particular property). When T is infinite, π is a linear semi-infinite programming problem (LSIP). The set of all the problems π = (c, σ ), with c = 0n , and whose constraint systems have the same index set T , will be denoted by . When different problems are considered in , they and their associated elements will be distinguished by means of sub(super)scripts. So, if π1 also belongs to , we write π1 = (c1 , σ1 ) and σ1 := {(at1 ) x bt1 , t ∈ T }. Obviously, the parameter space can be identified with (Rn \{0n }) × (Rn × R)T , where the set of possible constraint systems is itself identified with (Rn × R)T . The solving strategies for π , formally introduced in section 3, are based on the idea of approaching π by means of sequences of problems, in , converging to π . The notion of convergence in is leaned on the extended distance δ : × → [0, +∞], given by 1 1 at at δ(π1 , π ) := max c − c∞ , sup b1 − bt . t ∈T ∞ t In this way, is endowed with the uniform convergence topology. (, δ) is a Hausdorff space, whose topology satisfies the first axiom of countability (i.e., convergence is established by means of sequences, since each point has a countable base of neighbourhoods). Given π ∈ , we will denote by F its feasible set, by v its optimal value, and by F ∗ its optimal set. We also use the (lower) level set L(α) := {x ∈ F | c x α}, α ∈ R (obviously, L(v) = F ∗ ). Since F and L(α), α ∈ R, are given as intersection of closed half-spaces, they are obviously closed and convex sets in Rn . We consider, in , the subsets c , of consistent problems (i.e., having a non-empty feasible set), b , of bounded problems (i.e., with finite optimal value), and s , of solvable problems (i.e., whose optimal value is attained). We will write v = −∞ if π is unbounded (i.e., when c x is not bounded from below on F ), and v = +∞ when π is inconsistent (i.e., when F = ∅). This paper approaches the stability and well-posedness of the LSIP problem, following the tradition of the MPDP Symposia (see, for instance, [12], presented to the first symposium, held on May 24–25, 1979). In section 3 we present two particular solving strategies for a solvable problem π , by means of proximal bounded problems or solvable problems, respectively. We also introduce three desirable properties for a general solving strategy. The first two ones are analyzed, for both strategies, in section 4, and the last one is studied in section 5, in connection with certain notions of well-posedness of π . Section 6 organizes the main results of the paper in a summary-table, emphasizing

SOLVING STRATEGIES

173

the high relationship held between the notions of well-posedness provided in the paper and some stability properties of the problem already analyzed in [7] and [3]. We make use of this relationship in an application to the analysis of the Hadamard well-posedness of the Lagrangian dual associated to a nonlinear programming problem. 2.

Preliminaries

This section collects some results needed later. First, we introduce some notation used throughout the paper. Given ∅ = X ⊂ Rp , by conv(X), cone(X), span(X), O + (X) and X o we denote the convex hull of X, the conical convex hull of X, the linear hull of X, the recession cone of X (assumed that X is convex), and the dual cone of X (i.e., X o = {y ∈ Rp | y x 0 for all x ∈ X}), respectively. It is assumed that cone(X) always contains the zero-vector, 0p, and, so, cone(∅) = {0p }. The Euclidean and Chebyshev norms of x ∈ Rp , will be x and x∞ , respectively. The unit open ball, in Rp , for the Euclidean norm is represented by B. From the topological side, if X is a subset of any topological space, int(X), cl(X) and bd(X) represent the interior, the closure and the boundary of X, respectively. Finally, limr should be interpreted as limr→∞ , and {zr } is used to represent a sequence. At this moment, we recall some stability properties of π . More precisely, we will refer to some continuity properties of the feasible set mapping, F, the optimal value function, ϑ, and the optimal set mapping, F ∗ . The first one assigns to each problem π its feasible set (i.e., F(π ) = F ), the second one assigns to π its optimal value (i.e., ϑ(π ) = v), and the last one assigns to π the (possibly empty) optimal set (i.e., F ∗ (π ) = F ∗ ). Next, we recall some well-known continuity concepts for set-valued mappings. If Y and Z are two topological spaces and M : Y ⇒ Z is a set-valued mapping, we shall consider the following properties of M: If both spaces verify the first axiom of countability, we say that M is closed at y ∈ Y if for all sequences {y r } ⊂ Y and {zr } ⊂ Z satisfying limr y r = y, limr zr = z and zr ∈ M(y r ), one has z ∈ M(y). The mapping M is lower semicontinuous (lsc, for short) at y ∈ Y if for each open set W ⊂ Z such that W ∩ M(y) = ∅ there exists an open set U ⊂ Y, containing y, such that W ∩ M(y 1 ) = ∅ for each y 1 ∈ U . M is said to be upper semicontinuous (usc, in brief) at y ∈ Y if for each open set W ⊂ Z such that M(y) ⊂ W there exists an open neighbourhood of y in Y, U , such that M(y 1 ) ⊂ W for every y 1 ∈ U . It has been established in [7] that F is closed at any consistent problem π . Moreover, it is shown in [8] that the boundedness of F implies the upper semicontinuity of F at π . The following theorem gathers some characterizations of the lower semicontinuity of F at π , given in [7, theorem 3.1]. The last statement in this theorem refers to the so-called strong Slater condition, which is said to be satisfied by a problem π ∈ c if

174

CÁNOVAS ET AL.

there exist ρ > 0 and x ∈ Rn such that at x bt + ρ for all t ∈ T . Then, x is called an SS-element of π . Theorem 2.1. If π = (c, σ ) ∈ c , then the following statements are equivalent: (i) F is lsc at π ; (ii) π ∈ int(c ); at / cl conv , t ∈T ; (iii) 0n+1 ∈ bt (iv) π satisfies the strong Slater condition. The next theorem [6, corollary 9.3.1] characterizes the boundedness of the optimal set. In it, M denotes the first moment cone associated to σ , given by M := cone({at , t ∈ T }). It can immediately be checked that all the non-empty level sets, L(α), (and, in particular, F ∗ if π is solvable) have the same recession cone, given by {at , t ∈ T ; −c}o . Theorem 2.2. Let π ∈ c . The following statements are equivalent: (i) F ∗ is non-empty and bounded; (ii) {at , t ∈ T ; −c}o = {0n }; (iii) c ∈ int(M). The boundedness of the optimal set entails itself a nice stability property of the problem π , according to the following lemma [3, lemma 4.1], where intc (s ) denotes the interior of s in the topology relative to c . Lemma 2.3. π ∈ intc (s ) if and only if F ∗ is a non-empty bounded set. The following results [3, theorems 4.2 and 5.1] deal with the stability properties of the optimal value function and the optimal set mapping. Theorem 2.4. Let π = (c, σ ) ∈ c . Then: (i) ϑ is usc at π if and only if F is lsc at π . (ii) If F ∗ is a non-empty bounded set, ϑ will be lsc at π . If π ∈ b , the converse statement holds. Theorem 2.5. Given π ∈ s , the following propositions hold: (i) F ∗ is closed at π if and only if either F is lsc at π or F = F ∗ . (ii) If F ∗ is usc at π , then F ∗ is closed at π . The converse statement holds if F ∗ is bounded. (iii) F ∗ is lsc at π if and only if F is lsc at π and F ∗ is a singleton.

SOLVING STRATEGIES

175

Section 4 in [3] establishes the connection between the mentioned stability properties of π and certain concept of Hadamard well-posedness for this problem, which was traced out from [4]. Given {πr = (cr , σr )} ⊂ b such that limr πr = π , the sequence {x r } is said to be an asymptotically minimizing sequence (a.m.s., in brief) for π , associated with {πr }, if x r ∈ Fr for all r, and limr cr x r − vr = 0, i.e., as r increases, x r approximately solves the approximating problem πr . The problem π ∈ s will be Hadamard well-posed (Hwp, for short) if for each x ∗ ∈ F ∗ and for each possible sequence {πr } ⊂ b converging to π , there exists at least an associated a.m.s. converging to x ∗ . The following theorem (obtained from [3, theorem 4.3]) characterizes this property. Here, ϑb denotes the restriction of ϑ to b . Theorem 2.6. Let π = (c, σ ) ∈ s . Then, π is Hwp if and only if ϑb is continuous at π and, either F is lsc at π or F is a singleton. Finally, we recall a concept to be applied in section 5. Given a consistent system σ := {at x bt , t ∈ T }, with solution set F , we say that a x b is a consequence of σ if it is satisfied at each point of F , i.e., a z b for every z ∈ F . The so-called nonhomogeneous Farkas lemma [11], characterizes the linear inequalities a x b which are consequences of a consistent system σ := {at x bt , t ∈ T } as those satisfying 0n a at . (2.1) , t ∈ T; ∈ cl cone bt −1 b ) If we introduce the cone, R(T + , of all the functions λ : T → R+ taking positive values only at finitely many points of T , (2.1) is equivalent to the existence of sequences ) {λr } ⊂ R(T + and {µr } ⊂ R+ , such that

a 0n a t r , λt + µr = limr bt −1 b t ∈T

and where λr = (λrt )t ∈T , r = 1, 2, . . . . 3.

Solving strategies

Let π ∈ s be given. Let & be a non-empty subset of c such that π is an accumulation point of &, and let A& denote the set of all the sequences {πr } ⊂ & converging to π . We define a solving strategy for π based on & as a set-valued mapping N S : A& ⇒ Rn

176

CÁNOVAS ET AL.

satisfying the following properties: (S1) {x r } ∈ S ({πr }) implies x r ∈ Fr , for all r ∈ N; (S2) If {x r } ∈ S({πr }) and {x rk } is a subsequence of {x r }, then {x rk } ∈ S({πrk }). In this paper we consider two particular solving strategies for the problem π based on b and s , motivated, respectively, by the idea of solving either approximately or exactly proximal problems. Note that, for an arbitrarily chosen π = (c, σ ) ∈ s , both, b and s , satisfy the conditions required to & in the previous definition (just consider πr = ((1 + 1/r)c, σ ), r ∈ N). For the sake of brevity, we write Ab and As instead of Ab and As . In the first strategy, N Sb : Ab ⇒ Rn , Sb ({πr }) represents the set of all the asymptotically minimizing sequences associated with {πr }. The second one, N Ss : As ⇒ Rn , is defined by Ss ({πr }) = {{x r } ⊂ Rn | x r ∈ Fr∗ , r = 1, 2, . . .}. We approach the well-posedness of the problem π in terms of the behaviour of these two strategies, which is qualified by means of the following definitions. If S is a solving strategy for π based on &, we say that S is admissible if, for all {πr } ∈ A& , any cluster point of any sequence {x r } ∈ S({πr }), belongs to F ∗ . S will be efficient if, for all {πr } ∈ A& , any sequence {x r } ∈ S({πr }) has at least a cluster point in F ∗ . Finally, S is said to be complete if, for all x ∗ ∈ F ∗ and for all {πr } ∈ A& , there exists a sequence {x r } ∈ S({πr }), which has x ∗ as a cluster point. As a straightforward consequence of these definitions, we observe that every efficient solving strategy for π (based on &), S, is admissible. In fact, let us consider an arbitrary sequence {πr } ∈ A& , and suppose that x is a cluster point of certain {x r } ∈ S({πr }), i.e., x = limk x rk for some subsequence {x rk } of {x r }. Applying condition (S2) in the definition of solving strategy and the current assumption, we conclude x ∈ F ∗ . 4.

Admissibility and efficiency

The first theorem of this section characterizes the admissibility of the strategies under consideration, Sb and Ss . Theorem 4.1. Let π ∈ s and consider the solving strategies, for π , Sb and Ss . Then the following statements are equivalent: (i) Sb is admissible; (ii) Ss is admissible; (iii) F ∗ is closed at π .

SOLVING STRATEGIES

177

Proof. First we prove (i) ⇒ (ii). Let {πr } ∈ As , and take {x r } ∈ Ss ({πr }). Since, As ⊂ Ab and, obviously, {x r } ∈ Sb ({πr }), we conclude from (i) that every cluster point of {x r } belongs to F ∗ . The statement (ii) ⇒ (iii) is a trivial consequence of the definitions. Finally, we prove (iii) ⇒ (i). Let {πr } ∈ Ab and {x r } ∈ Sb ({πr }). If x is a cluster point of {x r }, we may assume from condition (S2), and without loss of generality, that x = limr x r . By statement (i) in theorem 2.5, we first suppose F = F ∗ . Then, the closedness of F at π (established in [7]) implies x ∈ F = F ∗ , and we obtain (i) in this case. Now, assume that F is lsc at π . Since {x r } is an a.m.s. for π , associated with {πr }, one has c x = limr cr x r = limr vr . Applying theorem 2.4(i), we have c x v, and then x ∈ F ∗ .

The equivalence between the efficiency of Sb and Ss is established in the next theorem. Theorem 4.2. Let us consider the solving strategies, for π ∈ s , Sb and Ss . Then the following statements are equivalent: (i) Sb is efficient; (ii) Ss is efficient; (iii) F ∗ is closed at π and F ∗ is bounded; (iv) ϑb is continuous at π and F ∗ is bounded. Proof. The proposition (i) ⇒ (ii) is immediate and follows from the same idea of (i) ⇒ (ii) in the previous theorem. Theorem 4.1 allows us to state that (ii) implies that F ∗ is closed at π (remember that efficiency entails admissibility). If F ∗ were unbounded, then we could consider the constant sequence πr = π , for all r ∈ N, and a sequence {x r } ⊂ F ∗ such that limr x r = +∞. Obviously, {πr } ∈ As and {x r } ∈ Ss ({πr }); however {x r } has no cluster points, which contradicts (ii). Hence, we have already established (ii) ⇒ (iii). Next we prove (iii) ⇒ (iv). If {πr } ⊂ b converges to π , lemma 2.3 establishes the existence of r0 such that πr is solvable if r r0 . For each r r0 , we take x r ∈ Fr∗ . Thus, vr = (cr ) x r if r r0 , and we are going to prove that limr vr = v. First we prove that {x r }rr0 is bounded, entailing the boundedness of {vr }rr0 . In fact, applying theorem 2.5(ii), F ∗ will be usc at π . So, if W is any bounded neighbourhood of F ∗ , we may assume r0 taken such that x r ∈ W , for all r r0 . Now, we prove that if {vrk } (r1 r0 ) is any convergent subsequence of {vr }, then there must be limk vrk = v. Hence, we have limr vr = lim infr vr = lim supr vr = v and, so, continuity of ϑb at π .

178

CÁNOVAS ET AL.

Assume that {vrk } converges to v. We write vrk = (crk ) x rk , with x rk ∈ Fr∗k . The sequence {x rk } is bounded, and we assume w.l.o.g. that limk x rk = x. The closedness of F ∗ implies x ∈ F ∗ and we get v = limk vrk = limk crk x rk = c x = v. Finally, we are going to prove (iv) ⇒ (i). Let us consider {πr } ∈ Ab , and take {x r } ∈ Sb ({πr }). In a first step, we see that {x r } is bounded. Otherwise, we would have a subsequence {x rk } such that limk x rk = ∞ (so, we can assume x rk = 0n , for all k). The sequence {x rk −1 x rk } will contain a subsequence, denoted in the same way for the sake of brevity, converging to y ∈ bd(B). Since {x rk } is an a.m.s. for π , associated with {πrk }, we have −1 r r c k x k − vrk = c y, 0 = limk x rk since limk vrk = v. Moreover, for each t ∈ T , one has −1 −1 at y = limk atrk x rk x rk limk x rk btrk = 0, because limk btrk = bt . Thus y ∈ O + (F ∗ )\ 0n , contradicting the boundedness of F ∗ . Once we have proved {x r } is bounded, it will have, at least, a cluster point x. We write x = limk x rk , for some subsequence {x rk } of {x r }, and c x = limk crk x rk = limk vrk = v. So, x ∈ F ∗ .

Properties of the solving strategies Sb and Ss can be seen as properties of the problem π itself. In order to emphasize this approach, we give the following definition. Definition 4.3. The problem π ∈ s is called efficiently Hadamard well-posed (e-Hwp, for short) if it verifies any one of the equivalent statements given in theorem 4.2. We finish this section with an immediate corollary of the previous results. Corollary 4.4. Let π ∈ s . If F ∗ is bounded, then the following conditions are equivalent: (i) Sb is admissible; (ii) Ss is admissible; (iii) Sb is efficient; (iv) Ss is efficient.

SOLVING STRATEGIES

5.

179

Completeness

This section is devoted to characterize the completeness of the solving strategies Sb and Ss in connection with two notions of well-posedness. We shall start with the study of Sb . Theorem 5.1. Let π ∈ s , and consider the solving strategy Sb for the problem π . Then, Sb is complete if and only if π is Hwp. Proof. The “if” part is an immediate consequence of the definitions. Now, assuming that Sb is complete, we will prove that π is Hwp; which is equivalent to show that ϑb is continuous at π and, either F is lsc at π or F is a singleton (see theorem 2.6). If ϑb is not continuous at π , there will exist {πr } ∈ Ab , such that the sequence {vr } does not converge to v. Consequently, there exist a subsequence of {vr }, {vrk }, and ε > 0, such that |vrk − v| ε, for k = 1, 2, . . . . Let x ∗ ∈ F ∗ be given. By hypothesis, there will exist a sequence {x rk } ∈ Sb ({πrk }) having x ∗ as a cluster point. So, for some subsequence {x rks } of {x rk }, one has x ∗ = lims x rks , and then lims vrks = lims crks x rks = c x ∗ = v, which contradicts the assumption about {vrk }. Next, assuming that F is not lsc at π and, simultaneously, F is not a singleton, we shall get a contradiction. Since F is assumed to be non-lsc at π , condition the (iii) in p ) , verifying λ = 1, orem 2.1 must fail. Then, there exists a sequence {λp } ⊂ R(T + t ∈T t p = 1, 2, . . . , and such that p a t λt . (5.1) 0n+1 = limp bt t ∈T

First, we prove that F ∗ has to be bounded. Suppose that it is not the case, and take x ∗ ∈ F ∗ and u ∈ O + (F ∗ ) with u = 1. Then define µr = 1/(u x ∗ + r), with r sufficiently large, say r r0 for certain r0 ∈ N, to guarantee the positiveness of the denominator, and take, for r r0 , cr := c − µr u and y r := x ∗ + ru. Obviously, y r ∈ F ∗ and (cr ) y r = v − 1. Define also the systems 1 r v−1 at + c x bt + , t ∈ T , r r0 , σr := kr kr where the constants kr , r r0 , are chosen in such a way that r c < 1 and v − 1 < 1 . k r k r r ∞ r Finally, we shall introduce the associated problems πr := (cr , σr ), r r0 , which obviously verify limrr0 πr = π and πr ∈ c (because y r ∈ Fr ).

180

CÁNOVAS ET AL.

Then we have, for each r r0 , r p at + 1 cr 1 c kr , λt = limp v−1 v −1 bt + kr kr t ∈T and the non-homogeneous Farkas lemma allows us to conclude that (cr ) x v − 1 is a consequence of σr , which in fact entails y r ∈ Fr∗ and vr = v − 1. Thus, we have attained a contradiction with the continuity of ϑb at π . On the other hand, since we are assuming that F is not a singleton, we can take an optimal point x ∗ ∈ F ∗ and an arbitrary y ∈ F \{x ∗ }. Define w := y − x ∗ and, associated with each r ∈ N, take a positive scalar lr satisfying 1 w < 1 and 1 w y < 1 . r l r lr r ∞ Let us introduce, for each r ∈ N, the problem π r = (c, σ r ) with 1 1 σ r := at + w x bt + w y, t ∈ T . lr lr Obviously δ(π r , π ) < 1/r and, so, limr π r = π . Moreover, y ∈ F r (= F(π r )), for every r, and w x w y is a consequence of each σ r , since (5.1) implies p at + 1 w 1 w lr = . λt limp lr w y bt + l1r w y t ∈T According to lemma 2.3, the boundedness of F ∗ entails that {π r }rr0 ⊂ s , for a certain r0 , and, hence, {π r }rr0 ∈ Ab . However, the set W := {x ∈ Rn | w x < w y} is an open neighbourhood of x ∗ such that F r ∩ W = ∅, for all r ∈ N. So, x ∗ cannot be a cluster point of any sequence {x r } ∈ Sb {π r }, and we attain the aimed contradiction with the completeness of Sb . By means of the following two results, it turns out that, under the existence of at least n constraints, the completeness of Ss implies the unicity of the optimal solution. Lemma 5.2. Let us consider the solving strategy Ss for a given π ∈ s . If |T | n and Ss is complete, then F ∗ contains no lines. Proof. Assume that |T | n, Ss is complete and F ∗ contains, at least, a line. Fix x ∗ ∈ F ∗ and take u ∈ Rn , u = 1, such that x ∗ + λu ∈ F ∗ , for all λ ∈ R. Since c x v is a consequence of σ , we can apply the non-homogeneous Farkas lemma, and ) (2.1) leads us to the existence of sequences {λr } ⊂ R(T + and {µr } ⊂ R+ satisfying at 0n c r . (5.2) λt + µr = limr bt −1 v t ∈T

SOLVING STRATEGIES

181

Multiplying both sides of (5.2) by

x∗

we get ∗ r ∗ λt at x − bt + µr , 0 = c x − v = limr −1

t ∈T

and then limr µr = 0. So, we can eliminate the last term in (5.2). We can also assume w.l.o.g. that, for all r ∈ N, c at < 1. λrt v − bt ∞ r t ∈T In the following paragraphs we shall consider a fixed index r. At this time, let us note that dim span{at : t ∈ T } < n (because u is orthogonal to this set) and, thus, dim span{ abtt : t ∈ T } < n + 1. According to Carathéodory s theorem we can suppose that |supp λr | n (where supp λr is the support of λr , i.e., supp λr = {t ∈ T : λrt > 0}). Pick n different indices t1r , t2r , . . . , tnr such that supp λr ⊂ {t1r , t2r , . . . , tnr }, and let us define cr :=

n

λrtr atir . i

i=1

We can redefine, if necessary, {λrtr }i=1,2,...,n , adding to each one a sufficiently small posi itive number, to get r λtir > 0, i = 1, 2, . . . , n, n c

atir r < 2. λt r v − r i b r ti i=1 ∞ In particular, we have c − cr ∞ < 2/r. Let kr be a positive number such that kr r, u x ∗ + kr > 0, and µri < 1/r, for all i = 1, 2, . . . , n, where µri :=

(atir ) x ∗ − btir u x ∗ + kr

,

i = 1, 2, . . . , n.

So, if we define y r := x ∗ + kr u, we have (atir − µri u) y r = btir , for i = 1, 2, . . . , n. Now, let us define, for i = 1, 2, . . . , n, wir := atir − µri u. So, r w − at r = µr u∞ < 1 , i = 1, 2, . . . , n. i i i ∞ r r r We can slightly modify the set {w1 , . . . , wn } to get a linearly independent system of vectors {atrr , . . . , atrnr }. The process runs as follows: 1 r if w1r = 0n , w1 , atrr : = 1 1 (1, 0, . . . , 0) , if w r = 0 , n 1 r

182

CÁNOVAS ET AL.

atrr = j+1

r wj +1 , wjr +1 +

if wjr +1 ∈ / span{atrr , . . . , atrr }, 1

j

1 r u , if wjr +1 ∈ span{atrr , . . . , atrr }, j 1 (kr )2 j +1

where urj +1 is any vector belonging to {atrr , . . . , atrr }⊥ ∩ bd(B), and j = 1, 2, . . . , n − 1. 1 j Moreover, we can observe that r a r − at r < 2 , i = 1, 2, . . . , n. ti i ∞ r The next step consists of slightly modifying the set {bt1r , . . . , btnr } in order to get a new set {btrr , . . . , btrnr }, such that (atrr ) y r = btrr , i = 1, 2, . . . , n. Hence, we define 1 i i r r r r r r bt r := at r − wi y + wi y = btir + atrr − wir y r . i

i

=

i

(in which case = btir ), or r 1 r ∗ 1 r ∗ 1 r r r u (x + k u) = x + u u u. at r − wi y = r i i i (kr )2 (kr )2 kr i

Note that, either

atrr i

wir

btrr i

In the second case, we have ∗ r b r − bt r x + 1 . ti i (kr )2 kr

Finally, we define atr := at and btr := bt , if t ∈ T \ {t1r , . . . , tnr }. In this way we obtain a system σr := {(atr ) x btr , t ∈ T } verifying ar 2 x ∗ 1 at t max , + . supt ∈T r − bt bt ∞ r (kr )2 kr Next, we define cr :=

n

λrtr atrr . i

i

i=1

Remember that {atrr , . . . , atrnr } is a basis of Rn , and λrtr > 0, for i = 1, 2, . . . , n. We can 1 i also observe n n 2 2 c − cr c − cr + cr − cr < + 1+ λrtr atir − atrr ∞ λrtr . ∞ ∞ ∞ i i i r r i=1 i=1

So, if we are able to prove that the sequence { ni=1 λrtr }r∈N is bounded, and if we define i πr := (cr , σr ), r ∈ N, we shall obtain limr πr = π . By assumption, Ss is complete and F ∗ is unbounded. Next we shall prove that F has to be lsc at π . If it is not the case, proceeding as in the proof of theorem 5.1, we can vr = v − 1 for r = 1, 2, . . . , so, x ∗ cannot be a find a sequence { πr } ∈ As such that r πr }), which represents a contradiction. cluster point of any sequence { x } ∈ Ss ({

SOLVING STRATEGIES

183

Applying theorem 2.1, the lower semicontinuity of F at π entails the existence of an SS-element, x, of σ ; i.e., there exists a scalar ρ > 0 such that at x − bt ρ, for all t ∈ T . Since n atir c r λt r , = limr i btir v i=1

one has c x − v = limr

n

n λrtr (atir ) x − btir ρ lim supr λrtr . i

i

i=1

i=1

Hence, lim supr ni=1 λrtr (c x − v)/ρ, which implies the boundedness of { ni=1 λrtr }r∈N. i i At this moment, we summarize what we have. We have built a sequence {πr } ⊂ , such that limr πr = π . Also by construction, we have y r ∈ Fr , for all r ∈ N. On the other hand, r n at r cr r i λt r = , i (cr ) y r btrr i=1 i

= (atrr ) y r , i r r

i = 1, 2, . . . , n. According to the non-homogeneous Farkas lemma since r (c ) x (c ) y turns out to be a consequence of σr . Hence, y r ∈ Fr∗ , for all r ∈ N. In fact, Fr∗ = {y r }, for all r ∈ N, because the system σ r := {(atrr ) x btrr : i = 1, 2, . . . , n} i i has y r as the only point satisfying the Kuhn–Tucker conditions for the ordinary LP∗ problem π r = (cr , σ r ). So, F r = {y r }, which implies Fr∗ = {y r }, for all r ∈ N. Let us finish the proof of the lemma. It is obvious that limr y r = +∞. Hence, r {y } has no cluster points. In particular, x ∗ is not a cluster point of {y r }. Since {y r } is the unique element of Ss ({πr }), we reach a contradiction with the completeness of Ss . btrr i

Theorem 5.3. Let us consider the solving strategy Ss for a given π ∈ s . If |T | n and Ss is complete, then F ∗ is a singleton. Proof. If we suppose that F ∗ contains more than one point, namely x ∗ and y ∗ , we shall get a contradiction. Because of the previous lemma, we may assume that F ∗ contains no lines. This fact implies that the dimension of span{at , t ∈ T } is n (observe that F ∗ contains a line if and only if F does, since

n π ∈ s ⊂ b ). Let {at1 , at2 , . . . , atn } be a basis of span{at , t ∈ T }, and define d := i=1 ati . It is obvious that the homogeneous system at y 0, t ∈ T ; d y 0 has no non-trivial solution (if y = 0n were a solution, one would conclude y ∈ {at , t ∈ T }⊥ ). Now let us consider the system σ := at x bt , t ∈ T ; d x d y ∗ , σ ). provided that d y ∗ d x ∗ (otherwise, we shall replace y ∗ by x ∗ , in

184

CÁNOVAS ET AL.

σ is a system, in Rn , with index set T := T ∪ {t0 }, t0 ∈ / T , and whose solution ) and bounded, since , is non-empty (y ∗ ∈ F set, F ) = y ∈ Rn | at y 0, t ∈ T , d y 0 = {0n }. O + (F , will be usc at Accordingly, the corresponding feasible set mapping, F σ , entailing the boundedness of the solution set, F1 , of the system σ1 := at x bt , t ∈ T ; (d + εu) x (d + εu) y ∗ , where u = x ∗ − y ∗ and ε is taken positive and sufficiently small. Next, we consider the sequence {πr := (c + (1/r)w, σ )}, where w := d + εu. Obviously, limr πr = π and πr is solvable, for all r, as consequence of the non-emptiness and boundedness of the associated (lower) level sets 1 ∗ 1 ∗ 1 Lr v + w y = x ∈ F c + w x v + w y , r r r 1 . which are all contained in F Finally, let us take the open set W = {x ∈ Rn | w x > w y ∗ }. It can be easily seen that the assumption d y ∗ d x ∗ implies x ∗ ∈ W . Moreover, if x ∈ F ∩ W , we have 1 1 c + w x > c y ∗ + w y ∗ = cr y ∗ , r r and, so, Fr∗ ∩ W = ∅. Hence, x ∗ cannot be a cluster point of any sequence {x r } ∈ Ss ({πr }), contradicting the completeness of Ss . Some authors consider that any kind of well-posedness should entail the unicity of the optimal solution, which will be approximated by optimal solutions of proximal problems. Next, we are going to establish the equivalence between the completeness of the solving strategy Ss , for the problem π ∈ s , viewed as a stability property of the problem itself, and certain concept of Hadamard well-posedness of this problem (more restrictive at a first glance), which can be found, for instance, in [10]. As a remarkable fact, we recall that the uniqueness of the optimal solution of π , assuming the existence of, at least, n constraints, is not an hypothesis in the completeness of the solving strategy Ss , but a consequence. We give the following definition: Definition 5.4. The problem π ∈ s is called strongly Hadamard well-posed (s-Hwp, in brief) if F ∗ is a singleton (i.e., F ∗ = {x ∗ }) and, for every {πr } ∈ As and every sequence {x r } ∈ Ss ({πr }), one has limr x r = x ∗ . Theorem 5.5. Let us consider the solving strategy Ss for a given π ∈ s . Assume |T | n. Then, the following statements are equivalent: (i) π is s-Hwp; (ii) Ss is complete.

SOLVING STRATEGIES

185

Proof. The statement (i) ⇒ (ii) is a trivial consequence of the definitions. Now, assume the completeness of Ss . Since |T | n, theorem 5.3 establishes the uniqueness of the optimal solution. Put F ∗ = {x ∗ }, and fix any {πr } ∈ As and any {x r } ∈ Ss ({πr }). We prove that x ∗ = limr x r through the following reasoning in two steps: Step 1. The sequence {x r } is bounded. Otherwise, it will have a subsequence {x rk }, such that limk x rk = ∞ and {x rk −1 x rk } converges to a certain non-zero vector z belonging to O + (F ) (following the same reasoning that in the proof of implication (iv) ⇒ (i) in theorem 4.2). Applying (ii), there must exist a sequence {y rk } ∈ Ss ({πrk }), having x ∗ as a cluster point. We can assume, without loss of generality, that {y rk } converges to x ∗ . So, −1 −1 c z = limk crk x rk x rk = limx rk crk x rk k r −1 r r k k k = limk x c y = 0, and z belongs actually to O + (F ∗ ), contradicting the boundedness of F ∗ . Step 2. Let us prove that every convergent subsequence of {x r } converges to x ∗ and, consequently, the sequence itself converges to x ∗ . If we suppose that {x rk } converges to x, we can repeat the previous argument and take a sequence {y rks } converging to x ∗ , and then c x = lims (crks ) x rks = lims (crks ) y rks = c x ∗ . Thus x is optimal for π , i.e., x = x∗. The following corollary gathers some equivalent statements for a problem π with a unique optimal solution. Corollary 5.6. Let us consider π ∈ s such that F ∗ = {x ∗ }. Then the following statements are equivalent: (i) Ss is efficient (or admissible); (ii) Ss is complete; (iii) π is s-Hwp; (iv) Sb is efficient (or admissible); (v) Sb is complete; (vi) π is Hwp; (vii) π is e-Hwp. Proof. It is immediate that, under the assumption, F ∗ = {x ∗ }, every efficient solving strategy for π is complete. So, we have (i) ⇒ (ii) and (iv) ⇒ (v). The uniqueness of the optimal solution also implies |T | n, and then, we have (ii) ⇔ (iii) (according to theorem 5.5). The statement (iii) ⇒ (i) is a trivial consequence of the definitions.

186

CÁNOVAS ET AL.

Corollary 4.4 provides (i) ⇔ (iv). Moreover, these two properties are equivalent to (vii), by definition. Theorem 5.1 states the equivalence between (v) and (vi). Finally, [3, corollary 4.4] establishes that, if π is Hwp, then the limit of any convergent a.m.s. for π is an optimal point. This property, together with condition (S2) in the definition of solving strategy, ensures the admissibility of Sb , i.e., we have (vi) ⇒ (iv). Next, we are going to study the completeness of Ss in the remaining case, i.e., when |T | < n. So, let us consider π = (c, σ ) ∈ s , with σ = {ai x bi , 1 i p}, p p < n. We have, for some λ = (λi )1ip ∈ R+ , p ai c λi . = bi v

(5.3)

i=1

Denoting by H the (possibly empty) set {x ∈ Rn | ai x = bi , 1 i p}, we obtain H ⊂ F ∗ . In fact, (5.3) shows that every point of H is a Kuhn–Tucker point of the LP-problem π . The following theorem provides a characterization of the completeness of Ss when |T | < n, which, roughly speaking, says that F ∗ must be “as small as possible”. Theorem 5.7. Assume |T | < n. Then Ss is complete if and only if H = F ∗ and {a1 , . . . , ap } is a linearly independent set. Proof (Sketch). The proof of the “if” condition is routine. For the converse statement, assume that, either H F ∗ , or the set {a1 , . . . , ap } is linearly dependent. In any case, we obtain that at least one of the multipliers, say λp , is equal to zero. Pick two different points x ∗ and y ∗ in F ∗ , and take u := y ∗ − x ∗ . Now, let us consider, for all r ∈ N, the system 1 1 ∗ σr = ai x bi , 1 i p − 1; ap + u x bp + u y , r r for which y ∗ is a solution. Let us define r 1 ap + 1r u c c := + vr v r bp + 1r u y ∗ p−1 1 ap + 1r u ai λi + , = bi r bp + 1r u y ∗

r = 1, 2, . . . .

(5.4)

i=1

Putting πr = (cr , σr ), we have limr πr = π . (5.4) shows that πr ∈ s , for all r ∈ N. In fact, y ∗ ∈ Fr∗ , and so v r is the optimal value of πr . It can easily be realized that, if x ∈ Rn is a cluster point of any sequence in Ss ({πr }), then it must be u x u y ∗ . Since, obviously, u x ∗ < u y ∗ , we attain a contradiction with the completeness of Ss .

SOLVING STRATEGIES

6.

187

Conclusions. Application to the Lagrangian dual problem in nonlinear programming

At this moment we underline the fact that the three desirable properties of both strategies have been entirely characterized in terms of stability properties of the problem, most of them easily checkable in practice (see section 2 and references therein). For instance, when the strong Slater condition and the boundedness (and non-emptiness) of the optimal set are simultaneously satisfied at the nominal problem, π , one has all the desirable properties of both strategies, unless the completeness of Ss , which requires, in addition, the uniqueness of the optimal solution (note that the boundedness and non-emptiness of the optimal set entails |T | n). Moreover, the uniqueness of the optimal solution is dealt in [6, section 10.5]. We summarize the main results given in the paper by means of table 1. This approach also allows us to analyze the Hadamard well posedness of continuous problems, i.e., those in which T is assumed to be a compact Hausdorff space and the functions a(·) and b(·) are continuous on T . The stability theory of the feasible set mapping, optimal value function and optimal set mapping in this context has been developed in [2,5]. When a continuous problem π turns out to be Hwp (in any of the senses given in the table), it can be solved via discretization techniques, by means of repeating a suitable finite set of constraints in order to keep the cardinality of T (note that we can lose the continuity of the coefficient functions). Next, we are going to apply our approach in order to analyze the Hadamard wellposedness of a linear semi-infinite continuous problem, which comes from reformulating the Lagrangian dual of a nonlinear programming problem (inspired in [1, section 6.4]). Let us consider the (primal) nonlinear programming problem Inf f (t) s.t. g(t) 0m ,

(P) t ∈ C,

where C is a compact subset of Rn and the functions f : C → R and g : C → Rm are continuous on C. Assume that the set {t ∈ C | g(t) 0m } is non-empty. The Lagrangian dual of (P) is given by (D) Sup inf f (t) + λ g(t) λ0m t ∈C

Table 1 Well-posedness of the LSIP problem. π ∈ s Admissible Efficient Complete

Sb

Ss F ∗ is closed at π F ∗ is closed at π and F ∗ is bounded (π is e-Hwp) (If |T | n) π is s-Hwp π is Hwp F ∗ = {x ∈ Rn | at x = bt , t ∈ T }, (If |T | < n) {at , t ∈ T } is linearly independent.

188

CÁNOVAS ET AL.

whose value, vD , coincides with the optimal value of the semi-infinite problem Sup z s.t. z f (t) + λ g(t), λ 0m .

(D ) t ∈ C,

The problem (D ) can be translated into the LSIP problem π : Inf c x | at x bt , t ∈ T , where we have used the following notation: x := λz ∈ Rm+1 , T := C ∪{s 1 , s 2 , . . . , s m }, provided that C ∩{s 1 , s 2 , . . . , s m } = ∅ (note that T is compact with the topology induced by Rn ); and g(t) −1 , t ∈ C, 0m , at : = c := −1 e j , t = s j , 1 j m, 0 −f (t), t ∈ C, bt : = 0, t = s j , 1 j m, where ej is the j -th vector of the usual basis of Rm . It is immediate that the coefficient functions t → at and t → bt are continuous on T and, so, π is a continuous problem. Moreover the optimal value of π , v, is equal to −vD . It is easily checked that π is consistent, since, if we arbitrarily choseλ 0m , the λ ∈ F. In function t → f (t)+λ g(t) attains its global minimum on T , z(λ); and, so, z(λ) fact, π is bounded, since the weak duality theorem (see, for instance, [1, theorem 6.2.1]) entails the boundedness of (D). λ is an SS-element of π for any On the other hand, it is immediate that z(λ)−1 λ > 0n (coordinate by coordinate) and, so, F is lsc at π (theorem 2.1). We devote the rest of this section to characterize the boundedness of the optimal set of π . This property, together with the lower semicontinuity of F at π , entails nice stability and well-posedness properties of π (as we commented at the beginning of the section). First we shall establish that the so called characteristic cone associated to σ (the constraint system of π ), 0m+1 at , , t ∈ T; K := cone bt −1 is closed. Because of (2.1), cl(K) is sometimes called the cone of consequences of σ . A linear inequality system whose characteristic cone is closed is called Farkas– Minkowski system. For those consistent problems π = (c, σ ) such that σ is a Farkas– Minkowski system, theorems 5.3(i) and 7.1 in [6] state that π is solvable if and only π

SOLVING STRATEGIES

189

satisfies the Karush–Kuhn–Tucker condition, i.e., there exist a point x ∗ ∈ F and certain indices t1 , . . . , tk ∈ T such that c ∈ cone {ati , 1 i k} and (ati ) x ∗ = bti , for all i = 1, . . . , k. In order closedness of K, it will be sufficient to establish that X := m+1 to show the }), is a compact set which does not contain 0m+2 (see [9]). conv({ abtt , t ∈ T ; 0−1 The compactness of X is a consequence of Mazur’s other hand, if there at Onthe

theorem. (T ) 0m+1 exist λ ∈ R+ and µ 0 such that 0m+2 = t ∈T λt bt + µ −1 , then, looking at the (m + 1)-th coordinate, it must be λt = 0 for all t ∈ C. Now, looking at the j -th coordinate, 1 j m, it must be λs j = 0. Finally, looking at the (m+ 2)-th coordinate, / X. we must have µ = 0. So, 0m+2 ∈ Theorem 6.1. Let π be the problem introduced above. The following statements are equivalent: (i) F ∗ is non-empty and bounded; (ii) cone({g(t), t ∈ C}) contains some element whose coordinates are, all of them, negative. Proof.

(i) ⇒ (ii). By virtue of theorem 2.2, statement (i) is equivalent to g(t) ej 0m ∈ int cone , t ∈ C; , j = 1, . . . , m . c= −1 −1 0

Projecting both sides on its first m coordinates space, and since the projection is an open function, 0m ∈ int(cone{g(t), t ∈ C; ej , j = 1, . . . , m}). So, cone g(t), t ∈ C; ej , j = 1, . . . , m = Rm , and, hence, there exist certain indices t1 , . . . , tk ∈ C and non-negative scalars λt1 , . . . , λtk , µ1 , . . . , µm such that −1m =

k

λti g(ti ) +

m

µj ej ,

j =1

i=1

where −1m denotes the vector of Rm whose coordinates are, all of them, equal to −1. Thus, ki=1 λti g(ti ) has all its coordinates negative. (ii) ⇒ (i). Let us suppose that there exist t1 , . . . , tk ∈ C and certain non-negative scalars λt1 , . . . , λtk such that ki=1 λti g(ti ) has all its coordinates negative. We may

assume, w.l.o.g, that ki=1 λti = 1 (by means of dividing each coefficient by the sum of all of them, which is obviously non-zero). Denoting by −µj to the j -th coordinate of

k i=1 λti g(ti ), 1 j m, we obtain k m 0m g(ti ) ej = . (6.1) λt i µj + 0 −1 −1 i=1

j =1

190

CÁNOVAS ET AL.

Note that µj > 0, j = 1, 2, . . . , m, and there exists certain i0 ∈ {1, . . . , k} such that the whole space Rm+1 . λti0 > 0. Obviously, { g(t−1i0 ) ; e0j , j = 1, . . . , m generates 0m Finally, by means of [6, theorem A.7], (6.1) implies −1 ∈ int(M), and, hence, F ∗ is a non-empty bounded set. References [1] M.S. Bazaraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming: Theory and Algorithms (Wiley, New York, 1993). [2] B. Brosowski, Parametric semi-infinite linear programming I. Continuity of the feasible set and of the optimal value, Math. Programming Study 21 (1984) 18–42. [3] M.J. Cánovas, M.A. López, J. Parra and M.I. Todorov, Stability and well-posedness in linear semiinfinite programming, SIAM J. Optim. 10 (1999) 82–98. [4] A.L. Dontchev and T. Zolezzi, Well-Posed Optimization Problems (Springer, Berlin, 1993). [5] T. Fischer, Contributions to semi-infinite linear optimization, in: Approximation and Optimization in Mathematical Physics, eds. B. Brosowski and E. Martensen (Peter Lang, Frankfurt-am-Main, 1983) pp. 175–199. [6] M.A. Goberna and M.A. López, Linear Semi-Infinite Optimization (Wiley, Chichester, UK, 1998). [7] M.A. Goberna, M.A. López and M.I. Todorov, Stability theory for linear inequality systems, SIAM J. Matrix Anal. Appl. 17 (1996) 730–743. [8] M.A. Goberna, M.A. López and M.I. Todorov, Stability theory for linear inequality systems II: upper semicontinuity of the solution set mapping, SIAM J. Optim. 7 (1997) 1138–1151. [9] R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, NJ, 1970). [10] M.I. Todorov, Generic existence and uniqueness of the solution set to linear semi-infinite optimization problems, Numer. Funct. Anal. Optim. 8 (1985–86) 27–39. [11] Y.J. Zhu, Generalizations of some fundamental theorems on linear inequalities, Acta Math. Sinica 16 (1966) 25–40. [12] S. Zlobec, R. Gardner and A. Ben-Israel, Regions of stability for arbitrarily perturbed convex programs, in: Mathematical Programming with Data Perturbations I, ed. A.V. Fiacco (Dekker, New York, 1982) pp. 69–89.