Luận văn Some qualitative problems in optimization

6Chapter 1 Preliminaries 1.1 Notations and basic concepts Most of the following basic concepts are able to be found in many books concerning convex analysis or convex optimization (see, e.g., [9], [36], [71], [86]). Let X be a locally convex Hausdorff topological vector space and X∗ be its topological dual endowed with weak∗-topology. For a nonempty subset C of X, C is said to be a convex set if for any x, y ∈ C and any θ ∈ [0, 1], we have θx+ (1− θ)y ∈ C, a cone if for any x ∈ C and θ ≥ 0 we have θx ∈ C, and a convex cone if it is convex and a cone, which means that for any x, y ∈ C and for any θ1, θ2 ≥ 0, we have θ1x+ θ2y ∈ C. Let x1, x2, ...., xk ∈ C. A point of the form θ1x1 + θ2x2 + .... + θkxk, where θi ≥ 0, i = 1, 2, ..., k and θ1 + θ2 + ...+ θk = 1 is called a convex combination of the points x1, x2, ...., xk. The convex hull of the set C, denoted by coC, is the set of all convex combinations of points in C. That means coC := {θ1x1 + θ2x2 + ....+ θkxk, xi ∈ C, θi ≥ 0, i = 1, 2, ..., k, θ1 + θ2 + ...+ θk = 1}. The closure of C, denoted by clC, is the intersection of all closed subsets containing C of X . 7The cone generated by C, denoted by cone C, is defined by ⋃ α≥0 αC. A closed convex cone K is called the closed convex pointed cone ifK∩(−K) = {0}. For a non-empty subset D of X, span (D − x) is the small subspace of X containing D − x, aff D, affin hull of D, is x+ span(D − x), for any fixed x ∈ D, core D is defined by {d ∈ D : ∀x ∈ X,∃ > 0,∀λ ∈ [−, ], d+ λx ∈ D}, icr D, called intrinsic core of D, is the core of D relative to affD, sqriD, the strong quasi-relative interior of convex set D, is the set of those x ∈ D for which cone(D − x) is a closed subspace, qriD, the quasi-relative interior of D, is the set of those x ∈ D for which cone cl(cone(D − x)) is a subspace. When X is finite dimensional, we have sqriD=qriD=riD=icrD. Let I be an arbitrary index set, {Xi, i ∈ I} be a family of subsets of X. Let = be the collection of all nonempty finite subsets of I, then (see [20]) cone( ⋃ i∈I Xi) = ⋃ J∈= cone( ⋃ j∈J Xj) (1.2) = ⋃ J∈=( ∑ j∈J coneXj) (1.3) The function f : X → R ∪ {+∞} is said to be a convex function if f(θx+ (1 − θ)y) ≤ θf(x) + (1− θ)f(y),∀x, y ∈ X,∀θ ∈ [0, 1]. It is called to be proper if dom f is nonempty where domf := {x ∈ X | f(x) < +∞} is the effective domain of f . The epigraph of f is defined by epif := {(x, r) ∈ X ×R | f(x) ≤ r}. 8Let f : X → R∪ {+∞} be a proper lower semi-continuous (l.s.c.) convex function. The conjugate function of f , f∗, is defined by f∗ : X∗ → R ∪ {+∞}, f∗(v) := sup{v(x)− f(x) | x ∈ domf}, The set (possibly empty) ∂f(a) := {v ∈ X∗ | f(x)− f(a) ≥ v(x− a),∀x ∈ X} is subdifferential of the convex function f at a ∈ domf . For ε ≥ 0, the ε-subdifferential of f at a ∈ domf is defined as the set (possibly empty) ∂εf(a) = {v ∈ X∗ | f(x)− f(a) ≥ v(x− a)− ε,∀x ∈ domf}. If ε > 0 then ∂εf(a) is nonempty and it is a weak ∗-closed subset of X∗. When ε = 0, ∂0f(a) collapses to ∂f(a). If C is a convex subset of X and z ∈ C then the normal cone to C at z, denoted by NC(z), is defined by NC(z) := {x∗ ∈ X∗ | x∗(x− z) ≤ 0, ∀x ∈ C}. For ε ≥ 0, the ε-normal cone to C at z, denoted by Nε(C, z), is defined by Nε(C, z) := {u ∈ X∗ | u(x− z) ≤ ε,∀x ∈ C}. It is easy to see that Nε(C, z) = ∂εδC(z) where δC is the indicator function of a subset C of X, i.e., δC(x) :=  0, x ∈ C, +∞, x /∈ C. Let RT be the product space with product topology, where T is an arbitrary (pos- sibly infinite) index set. Denote by R(T ) the generalized finite sequence space which 9consists of all sequences λ = (λt)t∈T such that λt ∈ R for each t ∈ T . The supporting set of λ, T (λ) := {t ∈ T | λt 6= 0}, is a finite subset of T . Let us denote R(T )+ := {λ = (λt) ∈ R(T ) | λt ≥ 0, t ∈ T}. R(T )+ is a convex cone of R(T ) (see [29] page 48). For each λ ∈ R(T )+ , for any x ∈ RT , we understand that 〈λ, x〉 = ∑ t∈T λtxt := ∑ t∈T (λ) λtxt, ∀x ∈ RT , ∀λ ∈ R(T ). Let ft : X → R ∪ {+∞}, t ∈ T (T is as above), be the proper l.s.c and convex functions. Given λ ∈ R(T ), we define∑ t∈T λtft(x) := ∑ t∈T (λ) λtft(x). Let Y be another locally convex Hausdorff topological vector space and Y ∗ be its dual space. Let S be a convex cone in Y , not necessarily solid (i.e., with nonempty interior). A mapping g : X → Y is called S-convex if g ( ξx+ (1 − ξ)y)− ξg(x)− (1− ξ)g(y) ∈ −S for every x, y ∈ X and every ξ ∈ [0, 1]. If g, S-convex mapping, is continuous then g−1(−S) := {x ∈ X | g(x) ∈ −S} is a closed convex subset of X. From now on, we assume that g is an S-convex and continuous mapping on X. For a closed convex cone S of Y , the nonnegative polar cone (dual cone) of S, denoted by S+, is defined by S+ := {y∗ ∈ Y ∗ | 〈y∗, k〉 ≥ 0, ∀k ∈ S}. We often write y∗(k) instead of 〈y∗, k〉. It is worth noting that g(x) ∈ −S ⇔ λg(x) ≤ 0,∀λ ∈ S+, (1.4) where λg(x) is written for λ(g(x)) 10 We now recall some useful definitions and basic concepts concerning semiconvex problems, which can be found, for instance, in [15], [67]. Let X be a Banach space. Let f : X → R be a locally Lipschitz function at x ∈ X. The generalized directional derivative of f at x in the direction d ∈ X, denoted by f◦(x; d), is defined by (see [15], page 25) f◦(x; d) := lim sup h→0 t↓0 f(x+ h+ td)− f(x+ h) t . For d ∈ X, if the limit lim t↓0 f(x+ td)− f(x) t exists then it is called the directional derivative of f at x in the direction d and is denoted by f ′(x; d). The Clarke subdifferential of f at x, denoted by ∂cf(x), is defined by ∂cf(x) := {u ∈ X∗ | u(d) ≤ f◦(x; d),∀d ∈ X}. When f is convex, ∂cf(x) coincides with the subdifferential ∂f(x) of Convex Analysis. The function f is said to be regular1 at x (in the sense of F.H. Clarke) if f ′(x; d) exists and equals to f◦(x; d) for each d ∈ X ([15], Definition 2.3.4). The following definition is proposed by R. Mifflin in [67]. Definition 1.1.1 [67] Let C be a subset of X. The function f : X → R is said to be semi-convex at x ∈ C if f is locally Lipschitz, regular at x, and x+ d ∈ C, f ′(x; d) ≥ 0 =⇒ f(x+ d) ≥ f(x). The function f is said to be semi-convex on C if f is semi-convex at any x ∈ C. Remark 1.1.1 Suppose that f is semi-convex at x. It is easy to see that if there exists u ∈ ∂cf(x) such that u(z − x) ≥ 0 then f(z) ≥ f(x). 1It is called quasidifferentiable in [66] 11 Let ε ≥ 0. The function f is said to be ε-quasidifferentiable (or ε- regular) [60] at x if for each d ∈ X, f ′(x; d) exists and 0 ≤ f◦(x; d)− f ′(x; d) ≤ √ε‖d‖. When ε = 0, f◦(x; d) = f ′(x; d) and the function f is called quasidifferentiable [67] (or regular [15]). Let A be a closed subset ofX and let f be as above. We recall a concept of ε-semiconvex function. Definition 1.1.2 The function f is said to be ε-semiconvex at z ∈ A if: (i) f is locally Lipschitz at z, (ii) f is ε-quasidifferentiable at z, and (iii) If z + d ∈ A and f ′(z; d) +√ε‖d‖ ≥ 0 then f(z + d) +√ε‖d‖ ≥ f(z). f is said to be ε-semiconvex on A if f is ε-semiconvex for all x ∈ A. Remark 1.1.2 A convex function on X is an ε-semiconvex function for any ε ≥ 0 (see [57], [60]). When ε = 0, we find again the concept of semiconvexity defined by R. Mifflin in [67]. Now we recall several definitions of approximate solutions [60] to the problem (Q) Minimize f(x) subject to x ∈ A, where f is a locally Lipschitz function on X and A is a nonempty closed subset of X. Definition 1.1.3 For ε ≥ 0, a point z ∈ A is said to be an (i) ε-solution of (Q) if f(z) ≤ f(x) + ε, for all x ∈ A, (ii) ε-quasisolution of (Q) if f(z) ≤ f(x) +√ε‖x− z‖, for all x ∈ A, (iii) regular ε-solution of (Q) if it is an ε-solution and an ε-quasisolution of (Q). 12 Remark 1.1.3 If z is an ε-quasisolution of (Q) then there exists a ball B around z with radius equal to √ ε such that f(z) ≤ f(x) + ε for all x ∈ B ∩A. In this case, we can say that z is a locally ε-solution of (Q). Remark 1.1.4 An “ε-solution” is called an “ε-optimal solution” in [79] and an “ap- proximate solution up to ε” in [60]. By convention, we understand that 0.(+∞) = 0. 1.2 Some basic results Let f : X → R ∪ {+∞} be a proper and convex function where X is a locally convex Hausdorff topological vector space. For any a ∈ domf , the epigraph of the conjugate function of f , epif∗, has a representation as follows (see [40]): epif∗ = ⋃ ε≥0 {(v, v(a) + ε− f(a)) | v ∈ ∂εf(a)}. (1.5) Let f, g : X → R ∪ {+∞} be proper and convex functions. For ε1, ε2 ≥ 0 and z ∈ domf ∩ domg, we have ∂ε1f(z) + ∂ε2g(z) ⊂ ∂ε1+ε2(f + g)(z), (1.6) and µ∂εf(z) = ∂µε(µf)(z) (1.7) (see [86], page 83) for µ > 0, ε ≥ 0, z ∈ domf. Lemma 1.2.1 Let f, g : X → R ∪ {+∞} be proper l.s.c. and convex functions such that at least one of them is continuous at some point of domf∩domg. Then epif∗+epig∗ is weak∗-closed. Proof. If, for instance, f is continuous at c ∈ domg, it is clear that c ∈ int(domf) ∩ domg, and this implies that 0 belongs to the core of domf − domg, which, in turn, 13 entails that cone(domf −domg) is a closed space. It then follows from [10, Proposition 3.1] that the set epif∗ + epig∗ is weak∗-closed. 2 For f and g as in Lemma 1.2.1, we have ∂f(a) + ∂g(a) ⊂ ∂(f + g)(a) for all a ∈ domf ∩ domg, where the inclusion can be strict. The following lemma was established in [10, Theorem 3.1] assuming that X is a Banach space, but the proof is exactly the same for locally convex vector spaces. Lemma 1.2.2 Let f, g : X → R ∪ {+∞} be proper l.s.c. and convex functions. If epif∗ + epig∗ is weak∗-closed then for each a ∈ domf ∩ domg, ∂(f + g)(a) = ∂f(a) + ∂g(a). The use of the next calculus rule is crucial in our developments. Let X be a Banach space. Theorem 1.2.1 ([39] Theorem 3 p.201). Let T be a compact topological space, and let f(t, x) be a function on T×X convex in x for every t ∈ T and upper semicontinuous in t for every x ∈ X. We set g(x) = sup t∈T f(t, x) and T (x) = {t ∈ T | f(t, x) = g(x) }. If the function x→ f(t, x) is continuous at a point x0 for any t ∈ T , then ∂g(x0) = co {∪ ∂ft(x0) | t ∈ T (x0)} where ft denotes the functions on X defined by ft(x) = f(t, x) and the closure is taken in the weak∗ topology of the space X∗. The following theorem is due to Ekeland [28] (see also [60]). It is used to prove our results later. Theorem 1.2.2 Let h : X → R ∪ {+∞} be a proper lower semi-continuous function that is bounded from below. Let ε > 0. For every point z ∈ X satisfying h(z) ≤ inf{h(x) | x ∈ X}+ ε, there exists some point zε ∈ X such that: 14 (i) h(zε) ≤ h(z) ≤ inf{h(x) | x ∈ X}+ ε, (ii) ‖zε − z‖ ≤ √ε, (iii) h(zε) ≤ h(x) +√ε ‖x− zε‖, for all x ∈ X. Corollary 1.2.1 [60] Let K be a closed subset of X. Let f : K → R be lower semicon- tinuous and bounded from below on K. If z ∈ K satisfies f(z) ≤ inf{f(x) | x ∈ K}+ ε, then there exists zε ∈ K such that (i) ‖z − zε‖ ≤ √ε, (ii) f(zε) ≤ f(x) +√ε ‖x− zε‖,∀x ∈ K. 1.3 Some known results concerning convex infinite problems Let us consider the following problem: (P) Minimize f(x) subject to ft(x) ≤ 0,∀t ∈ T, x ∈ C, (1.8) where T is an arbitrary (possibly infinite) index set, C is a non-empty closed convex subset of a locally convex Hausdorff topological vector space X, and f, ft : X → R ∪ {+∞}, t ∈ T , are proper, l.s.c and convex functions. Let A be the feasible set of (P). The constraint system of (P) is denoted by σ := {ft(x) ≤ 0, t ∈ T, x ∈ C}. The characteristic cone of σ is defined by K := cone{∪t∈Tepif∗t ∪ epiδ∗C}. We need some following results: 15 Lemma 1.3.1 [20] Supose that the cone K is weak∗-closed. Let v ∈ X∗, and α ∈ R. Then the following statements are equivalent: (i) v(x) ≥ α is consequence of σ; (ii) (−v,−α) ∈ K; (iii) There exists λ ∈ R(T )+ such that v(x) + ∑ t∈T λtft(x) ≥ α,∀x ∈ C. We also note that the notation C∞ stands for the recession cone of C where C is a non-empty closed convex set in X and f∞ stands for the recession function of f (for detail see page 3,4 [20]). We deal with the minimizers of (P). Proposition 1.3.1 [20] If X is the Euclidean space and C∞ ∩ {x ∈ X, f∞t ≤ 0, t ∈ T} = {0} then the set of minimizers of (P) is non-empty. The inclusion of the proposition above can be false even in the case that of X is a reflexive Banach space ( see Example 5.1 in [20]). The following theorem is a known result concerning minimizers of (P) where X is a locally convex Hausdorff topological vector space. Theorem 1.3.1 [20] Suppose that epif∗ + epiδ∗A and cone{∪t∈Tepif∗t ∪ epiδ∗C} are weak∗-closed sets. Then a ∈ A is a minimizer of (P) if and only if there exist v ∈ ∂f(a) and λ ∈ R(T )+ such that −v ∈ ∂( ∑ t∈T λtft + δC)(a), λtft(a) = 0,∀t ∈ T. (1.9) Moreover, if the functions ft, t ∈ T are continuous at a then (1.9) can be replaced by 0 ∈ ∂f(a) + ∑ t∈T λt∂ft(a) +NC(a), λtft(a) = 0,∀t ∈ T. (1.10)