Đề tài Some qualitative probilems in optimization

37 Chapter 3 Characterizations of solution sets of convex infinite problems and extensions 3.1 Introduction Characterizations of solution sets of a class of convex programming problems were in- troduced by Mangasarian [65] nearly two decades ago. In over the years, there were several results concerning characterizations of solution sets of optimization problems such as [12], [38], [48], [69],... Recently, characterizing solution sets of convex programs via Lagrange multipliers has attracted many authors (see [19], [45], [46]). Character- izing solution sets help us to understand the properties and the behavior of solution methods for problems that have multiple solutions, especially, nonlinear (convex or non-convex) optimization problems. In the first part of this chapter we concern characterizations of solution set of the problem (P) considered in the previous chapter: (P) Minimize f(x) subject to ft(x) ≤ 0,∀t ∈ T, x ∈ C. 38 Firstly, we establish that Lagrange multiplier characterizations of solution set of the problem model of (P) for the case where a solution of the problem is known. The results, in particular, covers the ones for cone-constrained convex problems [46]. Then, we consider the case where an exact solution of the problem is known. We also present characterization of solution set of (P) when a minimizing sequence is known instead (this is often the case when numerical methods are applied). The next part of this chapter is left for the consideration of a class of non-convex problems. Concretely, we consider the class of semi-convex programs under a number of infinite of convex constraints. We establish necessary and sufficient optimality conditions for a feasible point of the problem to be a solution of the problem. These optimality conditions are then used to derive several characterizations of solution sets for the problems under consideration. Finally, we introduce a characterization of solution set of a different class of problems, the linear fractional problems. Unlike the methods used before, characterization of solution set of the class of this problem is established via a duality scheme. We now give a description for the chapter. In the next section, based on the fact that Lagrangian function with a fixed Lagrange multiplier associated with a known solution of (P) is constant on the solution set of (P), we establish several character- izations of solution set of (P). Next, we give characterization of solution set of (P) via a minimizing sequence of (P). Consequences for cone-constrained convex programs are also obtained. In Section 3.3, we establish the optimality conditions for a class of non-convex problems: the class of semi-convex programs under a set constraint and a number of infinite of convex constraints. Then characterizations of solution set of the problem are established. Illustrative examples are also given. Section 3.4 is devoted to the characterization of solution sets of linear fractional problems. 39 3.2 Characterizations of solution sets of convex in- finite programs Throughout this chapter (except Section 3.4), X denotes a locally convex Hausdorff topological vector space, X∗ is its topological dual endowed with weak∗-topology. 3.2.1 Characterizations of solution set via Lagrange multipli- ers We assume that the solution set of (P), Sol(P ) := {x ∈ A | f(x) ≤ f(y),∀y ∈ A}, is nonempty where A stands for the feasible set of (P), A := {x ∈ X | x ∈ C, ft(x) ≤ 0,∀t ∈ T}. It is known that, under some constraint qualification condition (see Theorem 2.4.1), z ∈ A is a solution of (P) if and only if there exists λ = (λt) ∈ R(T )+ such that 0 ∈ ∂f(z) + ∑ t∈T λt∂ft(z) +NC(z), λtft(z) = 0, ∀t ∈ T. (3.1) The element λ ∈ R(T )+ satisfying (3.1) is called a Lagrange multiplier corresponding to the solution z. For a solution z of (P), the λ in (3.1) may not be unique. Denote by M(z) the set of all Lagrange multipliers corresponding to a solution z of (P). We recall the Lagrangian function associated with (P): L(x, λ) := { f(x) + ∑ t∈T λtft(x), if x ∈ C, λ ∈ R(T )+ , +∞ otherwise. For the cone-constrained convex problems and pseudo-linear problems, the La- grange function with a fixed Lagrange multiplier associated with a known solution is 40 constant on the solution set of the problem in consideration. This conclusion still holds for the class of the problems of model (P) and will be given in the next lemma. Its proof is quit similar to that ones in the mentioned papers and will be omitted. Lemma 3.2.1 For the problem (P), suppose that z ∈ Sol(P ) and (3.1) holds with λ ∈M(z). The following statements hold. (i) L(., λ) is a constant function on Sol(P ); (ii) λtft(x) = 0 for all t ∈ T (λ) and for all x ∈ Sol(P ). For λ ∈ R(T )+ , we denote T˜ (λ) := T \ T (λ). Theorem 3.2.1 For the problem (P), suppose that z ∈ Sol(P ) and (3.1) holds with λ ∈ R(T )+ . Then Sol(P ) = S1 = S¯1, where S1 = {x ∈ C | ∃u ∈ ∂f(z) ∩ ∂f(x), u(x− z) = 0, ft(x) = 0,∀t ∈ T (λ), ft(x) ≤ 0,∀t ∈ T˜ (λ)}, S¯1 = {x ∈ C | ∃u ∈ ∂f(x), u(x− z) = 0, ft(x) = 0,∀t ∈ T (λ), ft(x) ≤ 0,∀t ∈ T˜ (λ)}. Proof. We will prove that Sol(P ) ⊂ S1 ⊂ S¯1 ⊂ Sol(P ). It is obvious that S1 ⊂ S¯1. Firstly, we show that S¯1 ⊂ Sol(P ). Let x ∈ S¯1. Then x ∈ A and there exists u ∈ ∂f(x) such that u(x− z) = 0. Since f(z) − f(x) ≥ u(z − x) = 0, f(x) ≤ f(z), which proves x ∈ Sol(P ). So, S¯1 ⊂ Sol(P ). We now prove that Sol(P ) ⊂ S1. It follows from (3.1) that there exist u ∈ ∂f(z), v ∈∑t∈T (λ)λt∂ft(z), w ∈ NC(z) such that u+v+w = 0, and ft(z) = 0 for all t ∈ T (λ). As w ∈ NC(z), w(y − z) ≤ 0 for all y ∈ C. Moreover, since v ∈ ∑ t∈T (λ)λt∂ft(z) ⊂ ∂( ∑ t∈T (λ)λtft)(z), we get∑ t∈T (λ) (λtft)(y)− ∑ t∈T (λ) (λtft)(z) ≥ v(y − z),∀y ∈ X. (3.2) Observe that if y ∈ A then the left-hand side of (3.2) is less than or equal to zero as λ = (λt) ∈ R(T )+ and λtft(z) = 0 for all t ∈ T . Hence, v(y − z) ≤ 0 for all y ∈ A. This, 41 together with the facts that u + v + w = 0 and w(y − z) ≤ 0 for all y ∈ C, implies u(y − z) = −(v + w)(y − z) ≥ 0 for all y ∈ A. If x ∈ Sol(P ) then x ∈ A and f(x) = f(z). Hence, 0 = f(x) − f(z) ≥ u(x− z) ≥ 0, which ensures u(x− z) = 0. Moreover, for all y ∈ X, f(y)− f(x) = f(y)− f(z) ≥ u(y − z) = u(y − x) + u(x− z) = u(y − x). Therefore, u ∈ ∂f(x) and hence, u ∈ ∂f(z) ∩ ∂f(x). Thus, x ∈ S1 and the inclusion Sol(P ) ⊂ S1 holds. 2 The representations of S1 and S¯1 show that the active constraints corresponding to λt > 0 (the number of such λt is finite) remain active for all other solutions x ∈ Sol(P ). 3.2.2 Characterizations of solution set via subdifferential of Lagrangian function Let z ∈ Sol(P ) and let λ ∈M(z) be such that (3.1) holds. Since T (λ) is a finite subset of T , it is clear that the following inclusion holds. 0 ∈ ∂(f + ∑ t∈T (λ) λtft)(z) +NC(z), λtft(z) = 0,∀t ∈ T, or equivalently, ∂xL(z, λ) ∩ (−NC(z)) 6= ∅, λtft(z) = 0,∀t ∈ T. This suggests a characterization of the solution set of (P) in term of subdifferential of the Lagrangian function associated with (P). For this, we need the following lemma. 42 Lemma 3.2.2 For the problem (P), suppose that z ∈ Sol(P ) and (3.1) holds with λ ∈M(z). Then for each x ∈ Sol(P ), the following equality holds. ∂xL(x, λ) ∩ (−NC(x)) = ∂xL(z, λ) ∩ (−NC(z)). Proof. Let x ∈ Sol(P ) and let u ∈ ∂xL(x, λ) ∩ (−NC(x)). Then u ∈ ∂Lx(x, λ) and u ∈ −NC(x). Hence, f(y) + ∑ t∈T (λ) λtft(y)− f(x)− ∑ t∈T (λ) λtft(x) ≥ u(y − x),∀y ∈ X, u(y − x) ≥ 0,∀y ∈ C. (3.3) Since L(., λ) is constant on Sol(P ) (Theorem 3.2.1) and z ∈ Sol(P ), it follows from (3.3) that u(z− x) = 0. Thus, u(y− x) = u(y− z) + u(z− x) = u(y− z) for all y ∈ X and  f(y) + ∑ t∈T (λ) λtft(y)− f(z)− ∑ t∈T (λ) λtft(z) ≥ u(y − z),∀y ∈ X, u(y − z) ≥ 0,∀y ∈ C. Hence, u ∈ ∂xL(z, λ) ∩ (−NC(z)) and the inclusion ∂xL(x, λ) ∩ (−NC(x)) ⊂ ∂xL(z, λ) ∩ (−NC(z)) holds. The converse inclusion holds by a similar argument. 2 Theorem 3.2.2 For the problem (P), suppose that z ∈ Sol(P ) and (3.1) holds with λ ∈M(z). Then Sol(P ) = Sˆ, where Sˆ := {x ∈ C | ∂xL(x, λ) ∩ (−NC(x)) = ∂xL(z, λ) ∩ (−NC(z)), ft(x) = 0,∀t ∈ T (λ), ft(x) ≤ 0,∀t ∈ T˜ (λ)}. Proof. By Theorem 3.2.1 and Lemma 3.2.2, it is clear that Sol(P ) ⊂ Sˆ. It suffices to prove that Sˆ ⊂ Sol(P ). Let x ∈ Sˆ. Then x ∈ A. Since z ∈ Sol(P ), ∂xL(z, λ) ∩ (−NC(z)) 6= ∅ and ∂xL(x, λ) ∩ (−NC(x)) = ∂xL(z, λ) ∩ (−NC(z)) 6= ∅. 43 There exists u ∈ ∂xL(x, λ) such that u ∈ −NC(x). We get f(z) + ∑ t∈T (λ) λtft(z)− f(x)− ∑ t∈T (λ)λtft(x) ≥ u(z − x), u(z − x) ≥ 0. (3.4) By assumption, ft(x) = ft(z) = 0 for all t ∈ T (λ) and hence, ∑ t∈T (λ)λtft(z) =∑ t∈T (λ)λtft(x) = 0. It follows from (3.4) that f(x) ≤ f(z) which ensures x ∈ Sol(P ). 2 Example Let X = l2, the Banach space of all real sequences x = (ξn)n with ‖x‖ := ∑∞ 1 ξ 2 n < +∞. Let further C := {x = (ξn)n ∈ l2 | 0 ≤ ξn ≤ n,∀n ∈ N}. It is clear that C is a closed convex subset of X. Consider the problem Minimize f(x) := ∑∞ n=2 ξn n3 . subject to 1 − tξ1 ≤ 0, t ∈ (2,+∞), x ∈ C. Let T := (2,+∞) and ft(x) := 1 − tξ1 for all t ∈ T . It is obvious that f is continuous and convex on C. The feasible set of the problem is A := {(ξn) ∈ l2 | 1/2 ≤ ξ1 ≤ 1, 0 ≤ ξn ≤ n, n = 2, 3, ...} It is easy to see that z = (1, 0, ...) is a minimizer of f on C. On the other hand, for x ∈ C, ∂f(z) = {(0, 1/23, 1/33, ....)}, (0, 1/23, 1/33, ....) ∈ l2, ∂ft(z) = {(−t, 0, 0, ...)}, (−t, 0, 0, ...) ∈ l2, NC(z) = {u = (un) ∈ l2 | u(x− z) ≤ 0,∀x ∈ C} = {(un) ∈ l2 | u1(ξ1 − 1) + u2(ξ2 − 0) + ..... ≤ 0, (ξn) ∈ C}. Let (λ) = (λt) with λt = 0 for all t ∈ T . Let further u1 = 0, un = −1/n3 for all n ≥ 2. Then (un)n ∈ NC(z) and the following formula holds 0 ∈ ∂f(z) + ∑ t∈T λt∂ft(z) +NC(z). 44 By Theorem 3.2.2, the solution set of the problem is S = {x = (ξn) ∈ C | u(x− z) = 0, u ∈ ∂f(z), ft(x) ≤ 0,∀t ∈ T} = {x = (ξn) ∈ A | u1(ξ1 − 1) + ∑+∞ n=2 unξn = 0, (un) ∈ ∂f(x)} = {(ξn)n ∈ l2 | 1/2 ≤ ξ1 ≤ 1, ξi = 0,∀i ≥ 2}. Let consider the another problem posed on R2. Minimize √ x2 + y2 − x subject to t(x− 1) + y2 ≤ 0, t ∈ [0, 1], (x, y) ∈ C := {(x, y) | y ≥ 0, x ∈ R}. Let f(x, y) := √ x2 + y2 − x, ft(x, y) := t(x − 1) + y2 for all t ∈ T := [0, 1]. The problem in consideration has the model of (P). Firstly, we can check that the feasible set of the problem is A = {(x, y) ∈ R2 | x ≤ 1, y = 0} and that (0, 0) is a solution of the problem. The optimal value of the problem is equal to zero. A simple computation gives ∂f(0, 0) = {(u, v) ∈ R2 | (u+ 1)2 + v2 ≤ 1}, ∂ft(0, 0) = {(t, 0)}, ∀t ∈ [0, 1] ∂δC(0, 0) = NC(0, 0) = {(u, v) | u = 0, v ≤ 0}. Let us take λ ∈ R(T ) such that λ0 = 1, λt = 0 for all t ∈ (0, 1]. Then (3.1) holds since (0, 0) = (0, 0) + 1.(0, 0) + (0, 0) and λtft(0, 0) = 0,∀t ∈ [0, 1]. We now determine the solution set of the problem. Note thatf0(x, y) = 0,ft(x, y) ≤ 0, t ∈ (0, 1] ⇔ y 2 = 0, t(x− 1) + y2 ≤ 0, t ∈ (0, 1]. 45 The last system has solutions (x, y) with x ≤ 1, y = 0. On the other hand, if (x, y) 6= (0, 0) then ∂f(x, y) = ( x√ x2+y2 − 1, y√ x2+y2 ) . Hence, for (u, v) ∈ ∂f(x, y), (u, v) ( (x, y)− (0, 0)) = 0 ⇔ ( x√ x2+y2 − 1)x+ y2√ x2+y2 = 0 ⇔√x2 + y2 = x ⇔ y = 0, x ≥ 0. Note that f0(x, y) = 0 is equivalent to y = 0. We have {(x, y) ∈ C | (u, v) ∈ ∂f(x, y), (u, v)(x, y) = 0, f0(x, y) = 0, ft(x, y) ≤ 0, t ∈ (0, 1]} = {(x, y) | 0 ≤ x ≤ 1, y = 0}. Consequently, the solution set of the problem is {(x, y) ∈ R2 | 0 ≤ x ≤ 1, y = 0}. 3.2.3 Characterizations of solution set via minimizing sequence The characterizations of solution set Sol(P ) given in Theorem 3.2.1 and 3.2.2 (also in [12], [19], [46], [48], [65]) base on an essential assumption that a solution of problem in consideration is known. Suppose that Inf(P ) = α is finite and we do not know an exact solution of (P) but a minimizing sequence (an)n of (P), i.e., limn→+∞f(an) = α. This is often the case where some numerical method applies. In such a situation, we propose to characterize solution set of (P) based on a minimizing sequence as known in the next theorem. 46 Theorem 3.2.3 For Problem (P), assume that Inf(P ) = α is finite. If (an) is a minimizing sequence of (P) and epif∗ + epiδ∗A is weak ∗-closed . Then Sol(P ) is {x ∈ C | ∃u ∈ ∂f(x), u(an − x) ≥ 0,∀n ∈ N, ft(x) ≤ 0,∀t ∈ T}. Proof. Let x ∈ B := {x ∈ C | ∃u ∈ ∂f(x), u(an − x) ≥ 0, ft(x) ≤ 0,∀t ∈ T}. We get x ∈ A and there exists u ∈ ∂f(x) such that u(an − x) ≥ 0 for all n ∈ N. Since u ∈ ∂f(x), f(y)− f(x) ≥ u(y − x),∀y ∈ X. Hence, f(an)− f(x) ≥ u(an − x),∀n ∈ N. Since u(an − x) ≥ 0 for all n ∈ N, f(x) ≤ f(an). Letting n → +∞, we get f(x) ≤ α. Thus, x ∈ Sol(P ). The rest of the proof is to show that Sol(P ) ⊂ B. Let x ∈ Sol(P ). Then 0 ∈ ∂(f + δA)(x). (3.5) Since epif∗ + epiδ∗A is weak ∗-closed, by Corollary 1 in [10] (see also Lemma 2 in [21]), (3.5) is implies 0 ∈ ∂f(x) +NA(x). Therefore, there exists u ∈ ∂f(x) such that u(y−x) ≥ 0 for all y ∈ A. Since (an) ⊂ A, u(an − x) ≥ 0 for all n ∈ N. Thus, x ∈ B. Consequently, Sol(P ) ⊂ B. 2 3.2.4 Application As an application of previous results, we consider the cone-constrained convex mini- mization problem: (P1) Minimize f(x) subject to g(x) ∈ −S, x ∈ C 47 where f,X,C are as in Section 2.1, Y is a locally convex Hausdorff topological vector space, S is a closed convex cone in Y , and g : X → Y is a continuous and S-convex mapping. Let A1 and Sol(P1) be the feasible set and the solution set of (P1), respec- tively. Assume that Sol(P1) 6= ∅. By (1.4), g(x) ∈ −S if and only if µg(x) ≤ 0 for all µ ∈ S+, where S+ is the positive polar cone of S. Here, we note that, for µ ∈ S+, µg(x) is written for 〈µ, g(x)〉. Problem (P1) can be rewritten in the form of (P), (P˜1) Minimize f(x) subject to µg(x) ≤ 0, µ ∈ S+, x ∈ C. The optimality condition (3.1) becomes 0 ∈ ∂f(z) + ∑ µ∈T (λ) λµ∂(µg)(z) +NC(z), µg(z) = 0, ∀µ ∈ T (λ) (3.6) for some λ ∈ R(S+)+ , where T (λ) := {µ ∈ S+ | λµ > 0}. Theorem 3.2.1 now applies directly (to (P˜1)) to get characterizations of solution set of (P1). Corollary 3.2.1 Suppose that z is a solution of (P1) and λ ∈ R(S+)+ satisfying (3.6). Then Sol(P1) = S2 = S¯2, where S2 = {x ∈ C | ∃u ∈ ∂f(z) ∩ ∂f(x), u(x− z) = 0, µg(x) = 0,∀µ ∈ T (λ), µg(x) ≤ 0,∀µ ∈ K+ \ T (λ)}, S¯2 = {x ∈ C | ∃u ∈ ∂f(x), u(x− z) = 0, µg(x) = 0,∀µ ∈ T (λ), µg(x) ≤ 0,∀µ ∈ S+ \ T (λ)}. Observe that for each µ ∈ S+, µg is continuous and convex, and λµ ≥ 0. We have∑ µ∈T (λ) λµ∂(µg)(z) = ∂( ∑ µ∈T (λ) λµµg)(z). 48 Set λ¯ = ∑ µ∈T (λ)λµµ. Then λ¯ ∈ S+ and (3.6) can be rewritten in the form 0 ∈ ∂f(z) + ∂(λ¯g)(z) +NC(z), λ¯g(z) = 0. (3.7) We now can derive characterizations of the solution set Sol(P1) of (P1) in term of the Lagrange multiplier λ¯ ∈ S+ as follows. Corollary 3.2.2 For the Problem (P1), assume that z ∈ A1 is a solution and (3.7) holds with some λ¯ ∈ K+. Then Sol(P1) = S3 = S¯3, where S3 := {x ∈ A1 | ∃u ∈ ∂f(z) ∩ ∂f(x), u(x− z) = 0, λ¯g(x) = 0}, S¯3 := {x ∈ A1 | ∃u ∈ ∂f(x), u(x− z) = 0, λ¯g(x) = 0}. Proof. Repeat the argument in the proof of Theorem 3.2.1, using (3.7) instead of (3.1). 2 It is worth observing that the characterizations of the solution set Sol(P1) of (P1) given in Corollary 3.2.2 were established recently in [43] for the case where X is a Banach space and f : X → R is continuous, convex function. The Corollary 3.2.2 relaxes these conditions. The following corollary is a direct application of Theorem 3.2.3 into the case of the class of cone-constrained convex programs. The proof is similar to that one of Theorem 3.2.3 so it is omitted. Corollary 3.2.3 For Problem (P1), assume that (an) is a minimizing sequence of (P1) and epif∗ + epiδ∗A1 is weak ∗-closed. Then Sol(P1) is {x ∈ A1 | ∃u ∈ ∂f(x), u(an − x) ≥ 0,∀n ∈ N}. 3.3 Characterizations of solution sets of semi-convex programs We now modify the method presented in the previous sections to give characterizations of solution sets for a class of non-convex problems. We consider the class of semi-convex 49 problems with a number of infinite of convex constraints. Optimality conditions for the problems are established and then characterizations of solution sets are given. 3.3.1 Some basic results concerning semiconvex function The Lemma 3.3.1 below was proved in [67] (Theorem 8) with C is a convex subset of Rn. The conclusion holds for an arbitrary convex subset C of a Banach space X without any changes in the proof. Lemma 3.3.1 Suppose that f is semi-convex on a convex set C ⊂ X. Then for x ∈ C, d ∈ X with x+ d ∈ C, f(x+ d) ≤ f(x) =⇒ f ′(x; d) ≤ 0. Let us consider the semi-convex minimization problem under a set constraint and a number of infinite of convex constraints: (SP) Minimize f(x) subject to ft(x) ≤ 0, t ∈ T, x ∈ C, where C is a closed convex set of Banach space X, f : X → R is a semi-convex function on an open subset containing C, T is an arbitrary (possibly infinite ) index set, ft : X → R ∪ {+∞}, t ∈ T are proper, convex and l.s.c functions. The notion A stands for the feasible set of (SP) and Sol(SP ) indicates the solution set of (SP). Assume that Sol(SP ) 6= ∅. We recall that the system σ := {ft(x) ≤ 0, t ∈ T, x ∈ C} is said to be a Farkas Minkowski (FM) system if the cone: cone{∪t∈Tepif∗t ∪ epiδ∗C} is weak∗-closed. Note that A is the solution set of the system σ. The following lemma can be derived from Corollary 2 in [21] where the corollary was proved by using some optimality condition for a convex infinite problem established therein. Here we give a direct proof. 50 Lemma 3.3.2 Suppose that z ∈ A and σ is (FM). Then v ∈ NA(z) if and only if v ∈ ∑ t∈T (λ) λt∂ft(z) +NC(z) for some λ = (λt) ∈ R(T )+ satisfying ft(z) = 0 for all t ∈ T (λ). Proof. Let v ∈ NA(z). Then x ∈ A =⇒ v(x) ≤ v(z). (3.8) Since σ is (FM), it follows from Farkas’ lemma (see Theorem 2.2, see also Theorem 4.1 in [20]) that (3.8) is equivalent to (v, v(z)) ∈ cone{∪t∈Tepif∗t ∪ epiδ∗C}. It follows from (1.3) that there exists λ = (λt) ∈ R(T )+ such that (v, v(z)) ∈ ∑ t∈T (λ) λtepif ∗ t + epiδ ∗ C. Using representation (1.5) for epif∗t and epiδ ∗ C, there exist ut, w ∈ X∗, t, ρ ∈ R+, t ∈ T (λ) such that (v, v(z)) = ∑ t∈T (λ) λt(ut, ut(z) + t − ft(z)) + (w,w(z) + ρ− δC(z)) where ut ∈ ∂tft(z) and w ∈ ∂ρδC(z). Hence, v = ∑ t∈T (λ) λtut + w, v(z) = ∑ t∈T (λ) λt[ut(z) + t − ft(z)] + w(z) + ρ− δC(z). This implies that ∑ t∈T (λ) λtt − ∑ t∈T (λ) λtft(z) + ρ = 0. Since z ∈ A, ft(z) ≤ 0 for all t ∈ T . Moreover, λt ≥ 0 for all t ∈ T . We get from the last equality that ρ = 0, λtt = 0, and λtft(z) = 0 for all t ∈ T (λ). Since λt > 0 for 51 all t ∈ T (λ), it follows that ρ = 0, t = ft(z) = 0 for all t ∈ T (λ) which ensure that w ∈ ∂δC(z) = NC(z), ut ∈ ∂ft(z). Consequently, v ∈ ∑ t∈T (λ) λt∂ft(z) +NC(z). Conversely, let v ∈ ∑t∈T (λ)λt∂ft(z) + NC(z) with the mentioned λ = (λt) ∈ R(T )+ satisfying ft(z) = 0 for all t ∈ T (λ). Then v ∈ ∂( ∑ t∈T (λ) λtft + ∂δC)(z). Hence, ( ∑ t∈T (λ) λtft + ∂δC)(x)− ( ∑ t∈T (λ) λtft + ∂δC)(z) ≥ v(x− z),∀x ∈ X. If x ∈ A then δC(x) = 0 and ft(x) ≤ 0 for all t ∈ T . Taking the fact that ft(z) = 0 for all t ∈ T (λ) into account, the last inequality implies that v(x− z) ≤ 0 for all x ∈ A which proves that v ∈ NA(z). The proof is complete. 2 We are now in a position to establish a necessary and sufficient optimal condition for the Problem (SP). Theorem 3.3.1 For Problem (SP ), assume that σ is (FM). A point z ∈ A is a solution of (SP ) if and only if there exists λ ∈ R(T )+ such that 0 ∈ ∂cf(z) + ∑ t∈T (λ) λt∂ft(z) +NC(z), ft(z) = 0, ∀t ∈ T (λ). (3.9) Proof. We prove that z is a solution of (SP ) if and only if 0 ∈ ∂cf(z)+NA(z). Suppose that z minimizes (SP ), that is, z is a minimizer of f over A. Since f is locally Lipschitz, it is well-known that (see [15], page 52) 0 ∈ ∂cf(z) +NA(z), (3.10) where NA(z) is the Clarke normal cone of A at z which coincides with the normal cone of A at z in the sense of convex analysis since A is a convex set. 52 Conversely, suppose that (3.10) holds. Then there exists u ∈ ∂cf(z) such that x ∈ A⇒ u(x− z) ≥ 0. Since f is semi-convex, it follows from Remark 1.1.1 that f(x) ≥ f(z) and this inequality holds for all x ∈ A. Thus, z is a solution of (SP ). Since σ is (FM), the conclusion follows from (3.10) and Lemma 3.3.2. 2 It is worth observing that a special case of Problem (SP) where C = X and T is a finite set was considered in [40] and an asymptotic optimality condition (without any constraint qualification condition) was proposed there as well. It is easy to check that if for such a problem satisfies the (FM) condition which, in this case, means that the cone: cone{∪t∈Tepif∗t } is weak∗-closed, holds then this asymptotic condition collapses to 0 ∈ ∂cf(z) + ∑ t∈T λt∂ft(z), ft(z) = 0, ∀t ∈ T (λ), which is exactly what we get from (3.9) for this special case. 3.3.2 Characterizations of solution sets of semiconvex pro- grams The following result gives a characterization of the solution set of Problem (SP ) in terms of directional derivatives of the objective functional f . Theorem 3.3.2 For the problem (SP ), assume that z is a solution and there exists λ ∈ R(T )+ satisfying (3.9). Then Sol(SP ) = S4 where S4 := {x ∈ C | f ′(x, z − x) ≥ 0, ft(x) = 0,∀t ∈ T (λ) and ft(x) ≤ 0,∀t ∈ T˜ (λ)}. Proof. Let x ∈ S4. Then x ∈ A and f ′(x; z−x) ≥ 0. Since z = x+(z−x) ∈ A, it follows from the definition of semi-convex function that f(z) ≥ f(x). Hence, x ∈ Sol(SP ) since z is a solution of (SP). 53 Conversely, let x ∈ Sol(SP ). Then x ∈ A. Since z ∈ S and λ ∈ R(T )+ satisfying (3.9), there exists u ∈ X∗ such that u ∈ ∂cf(z), −u ∈∑t∈T (λ) λt∂ft(z) + ∂δC(z), ft(z) = 0, ∀t ∈ T (λ). Thus, −u ∈ ∂( ∑ t∈T (λ) λtft + ∂δC)(z), ft(z) = 0, ∀t ∈ T (λ), which implies that ∑ t∈T (λ) λtft(y) ≥ −u(y − z),∀y ∈ X. (3.11) In particular, with y = x ∈ Sol(SP ) (note that λtft(x) ≤ 0 for all t ∈ T ), we get u(x− z) ≥ 0. (3.12) Since u ∈ ∂cf(z) and f is semi-convex at z, f◦(z, d) = f ′(z, d), and u(d) ≤ f ′(z, d) for all d ∈ X. On the other hand, x and z are solutions of (SP), f(z + (x− z)) = f(x) = f(z). By Lemma 3.3.1, f ′(z;x− z) ≤ 0. Hence, u(x− z) ≤ 0. Combining this with (3.12), we get u(x− z) = 0. It now follows from (3.11) that λtft(x) = 0 for all t ∈ T (λ) and hence, ft(x) = 0, ∀t ∈ T (λ) and ft(x) ≤ 0, ∀T˜ (λ). (3.13) On the other hand, since A is convex and x, z ∈ A, x + t(z − x) = (1 − t)x + tz ∈ A for all t ∈ (0, 1). We get f ′(x; z − x) = lim t↓0 f [x+ t(z − x)]− f(x) t ≥ 0 as x is a solution of (SP ). This inequality, together with (3.13), implies that x ∈ S4. The proof is complete. 2 It is easy to verify that if the objective function is convex and locally Lipschitz near x ∈ X then f is semi-convex at x. In such a case, one may expect that the 54 characterization of solution set Sol(SP ) given in Theorem 3.3.2 (Sol(SP ) = S4) can be rewritten in terms of subdifferentials of f as those in Theorem 3.2.1. This is true as we will see below. We start with an elementary proposition. Proposition 3.3.1 For Problem (SP ), suppose that the objective function f is convex locally Lipschitz on an open set containing A. Let z be a solution of (SP ) and (3.9) holds for some λ ∈ R(T )+ . Then for any feasible point x ∈ A, it holds (∃u ∈ ∂f(x) ∩ ∂f(z), u(x− z) = 0) ⇔ (f ′(x; z − x) ≥ 0). Moreover, in this case, x is also a solution of (SP). Proof. Suppose that there exists u ∈ ∂f(x) ∩ ∂f(z) such that u(x − z) = 0. Then, u ∈ ∂f(x) and u(x− z) = 0 and hence, f(z) − f(x) ≥ u(z − x) = 0. So, f(z) ≥ f(x) which proves that x is a solution of (SP). Now, it is easy to verify that f ′(x; z−x) ≥ 0. Conversely, assume that f ′(x; z − x) ≥ 0. Since f is semi-convex at x , we have f(x+ z−x) = f(z) ≥ f(x) which shows that x is also a solution of (SP). On the other hand, it follows from (3.9) that there exists u ∈ ∂cf(z) = ∂f(z) such that −u ∈ ∑ t∈T (λ) λt∂ft(z) +NC(z), ft(z) = 0, ∀t ∈ T (λ). By the same argument as in the second part of the proof of Theorem 3.2.1 we get u ∈ ∂f(x) and u(x− z) = 0. The proof is complete. 2 Due to Proposition 3.3.1 when f is locally Lipschitz and convex on C then the set S4 in Theorem 3.3.2 is the same as the set S1 defined in Theorem 3.2.1: S1 = {x ∈ C | ∃u ∈ ∂f(x) ∩ ∂f(z), u(x− z) = 0, ft(x) = 0,∀t ∈ T (λ) ft(x) ≤ 0,∀t ∈ T˜ (λ)}. So Theorem 3.3.2 can be considered as an extension of Theorem 3.2.1 to the (non- convex) semi-convex problems. 55 We now consider a semi-convex optimization problem under a cone-constraint and a geometrical set constraint. (SP1) minimize f(x) subject to g(x) ∈ −S, x ∈ C, where Y is a locally convex Hausdorff topological vector space, S is a closed convex cone in Y , g : X → Y is a continuous and S-convex mapping, C and f are as in Problem (SP). The solution set and the feasible set of (SP1) are denoted by Sol(SP1) and A1, respectively. Assume that Sol(SP1) 6= ∅. By a similar way as in the last part of Section 2.2 (for Problem (P1)), the Problem (SP1) can be rewritten in the form of (SP), say Problem (S˜P1), with T = S+ and for each µ ∈ T , fµ defined by fµ(x) := 〈µ, g(x)〉. (S˜P1) minimize f(x) subject to fµ(x) := µg(x) ≤ 0,∀µ ∈ S+, x ∈ C. If the system σ′ := {µg(x) ≤ 0,∀µ ∈ K+;x ∈ C} is (FM), that is, cone{∪µ∈S+epi(µg)∗ ∪ epiδ∗C} is weak∗-closed then by Theorem 3.3.1, a point z ∈ A1 is a minimizer of (SP1) if and only if there exists γ = (γµ) ∈ R(S +) + such that 0 ∈ ∂cf(z) + ∑ µ∈suppγ γµ∂(µg)(z) +NC(z), µg(z) = 0,∀µ ∈ suppγ. Using a similar argument as in Theorem 3.3.1, we arrive at the assertion that z ∈ A1 is a minimizer of (SP1) if and only if there exist λ ∈ S+ such that 0 ∈ ∂cf(z) + ∂(λg)(z) +NC(z), λg(z) = 0. (3.14) We now give a characterization of solution set of (SP1). 56 Corollary 3.3.1 For the problem (SP1), assume that z is a solution and there exists λ ∈ S+ such that (3.14) holds then Sol(SP1) = S5 where S5 := {x ∈ A1 | f ′(x; z − x) ≥ 0, λg(x) = 0}. Proof. The proof is the same as the proof of Corollary 3.2.2, using Theorem 3.3.2 instead of Theorem 3.2.1. 2 If, in addition, f is convex on C then by Proposition 3.3.1, f ′(x; z − x) ≥ 0 is equivalent to the fact that there exists u ∈ ∂f(x) ∩ ∂f(z) such that u(x− z) = 0 for any x ∈ A1. So Corollary 3.3.1 can be considered as an extension of Corollary 3.2.2 to semi-convex problems with convex constraints. Example Minimize sin(x− y) subject to ty − x ≤ 0, t ∈ (0, 1 2 ], (x, y) ∈ C := {(x, y ∈ R2 | x2 + y2 ≤ 1, y ≤ x}. Let f(x, y) := sin(x − y), ft(x, y) := ty − x for all t ∈ T := (0, 12]. It is easy to verify that feasible set of the problem is {(x, y) ∈ R2 | x2 + y2 ≤ 1, y ≤ x, x ≥ 0}, f is semi-convex on the feasible set, and z = (0, 0) is a minimizer of the problem. For any feasible point (x, y) and each point (d1, d2) ∈ R2, a simple computation gives f ′((x, y); (d1, d2)) = (d1 − d2) cos(x− y). Moreover, ∂f c(0, 0) = {(u1, u2) | u1d1 + u2d2 ≤ d1 − d2,∀(d1, d2) ∈ R2}. and ∂ft(0, 0) = {(−1, t)},∀t ∈ (0, 12 ], NC(0, 0) = {(u, v) ∈ R2 | u = −v, v ≥ 0}. 57 Since (1,−1) ∈ ∂f c(0, 0) and (−1, 1) ∈ NC(0, 0), (0, 0) ∈ ∂f c(0, 0) +NC(0, 0). Choose λ ∈ R(T )+ with λt = 0 for all t ∈ (0, 12], we get (0, 0) ∈ ∂f c(0, 0) + ∑ t∈(0, 1 2 ] λt∂ft(0, 0) +NC(0, 0), λtft(0, 0) = 0,∀t ∈ (0, 1 2 ]. Which means that (3.9) holds. On the other hand, if (x, y) belongs to the feasible set then cos(x − y) > 0 and hence, f ′[(x, y); (0, 0)− (x, y)] ≥ 0 ⇔−(x− y)cos(x− y) ≥ 0 ⇔ x− y ≤ 0. Thus, x = y. It follows from Theorem 3.3.2 that the solution set of the problem is characterized by the following formula: {(x, y) ∈ C | f ′[(x, y); (0, 0)− (x, y)] ≥ 0, and ty − x ≤ 0, t ∈ (0, 1 2 ]}. So, the solution set of the problem is {(x, y) ∈ R2 | x = y, 0 ≤ x ≤ √ 2 2 }. 3.4 Characterization of solution sets of linear frac- tional programs In this section we introduce characterization of solution sets of a different class of prob- lems on a finite dimensional space, concretely, we consider a class of linear fractional programming problems imposed on Rn. Unlike the previous methods, in this section we deduce characterization of solution sets of the problems via a duality scheme. For this purpose, let us consider a linear fractional programming problem presented in [83]: (LF) max { f(x) := cTx+ c0 dTx+ d0 ∣∣∣ Ax ≤ b, x ≥ 0} . 58 HereA is an (m×n)-matrix; c, d, x are column vectors with n components; b is a column vector ofm components; c0, d0 are arbitrary constants; the superscript T denotes matrix transposition. Denote by F the feasible set of (LF): F = {x ∈ Rn |Ax ≤ b, x ≥ 0}. Let us consider another problem: (LD) min { f(u) := cTu+ c0 dTu+ d0 ∣∣∣ (u, v) ∈ F˜} , where the feasible set F˜ consists of all (u, v) ∈ Rn × Rm satisfying the constraints (dTu)c− (cTu)d−ATv ≤ c0d− d0c, (3.15) c0d Tu− d0cTu+ bTv ≤ 0, (3.16) u ≥ 0, v ≥ 0, (3.17) and Au ≤ b. (3.18) We note that the problem (LD) without the last constraint (3.18) is the dual problem of (LF) proposed by Seshan in [83]. It is also quoted in [84] with next three assumptions imposed on the problem (LF): (A1) dTx+ d0 > 0 for every x ∈ F ; (A2) F is a bounded set; (A3) f is not a constant function on F. These assumptions are used for proving three duality theorems presented in [83] (see also in [84]). Remark 3.4.1 Seshan [83] assumed that dTx+ d0 > 0 for all x ≥ 02. (Then (A1) is satisfied.) This strong condition guarantees that both the primal problem and the dual 2In fact, it was assumed that dTx + d0 > 0 for all x ∈ Rn. It is easy to see that this requirement cannot be fulfilled if d 6= 0. 59 problem are well defined. Stancu-Minasian [84] quoted the duality scheme of Seshan with a little modification: the condition dTx + d0 > 0 is only assumed to be satisfied for all x ∈ F . In this case, the objective function f(u) = (cTu+ c0)/(dTu+ d0) of the dual problem may not be well defined if its feasible set consists of only three constraints (3.15)–(3.17). To overcome the obstacle, the following condition has been introduced (see [84]): (A4) dTu+ d0 > 0 for every (u, v) ∈ F˜ . Remark 3.4.2 For Problem (LD), it is obvious that if (A1) is satisfied then dTu+d0 > 0 for every (u, v) ∈ F˜ . This means that (LD) is well defined if the primal problem is well defined. In this case, the assumption (A4) can be removed. Theorem 3.4.1 If (A1) is satisfied, then sup{f(x) |x ∈ F} ≤ inf{f(u) | (u, v) ∈ F˜}. (3.19) Proof. The inclusion follows from [83, Theorem 1] (see also [77], [84]) and Remark 3.4.2. 2 Theorem 3.4.2 Under the assumption (A1), it holds Sol(LF) = {u ∈ Rn | (u, v) ∈ F˜}. (3.20) where Sol(LF) is the solution set of the problem (LF). Proof. Denote by PrRn(F˜ ) the set {u ∈ Rn | (u, v) ∈ F˜}. On one hand, the inclusion PrRn(F˜ ) ⊂ F yields sup{f(x) |x ∈ F} ≥ sup{f(x) |x ∈ PrRn(F˜ )}, so sup{f(x) |x ∈ F} ≥ f(u) (∀u ∈ PrRn(F˜ )). 60 On the other hand, Theorem 3.4.1 gives sup{f(x) |x ∈ F} ≤ inf{f(u) | (u, v) ∈ F˜}, which implies that sup{f(x) |x ∈ F} ≤ f(u) (∀u ∈ PrRn(F˜ )). Consequently, sup{f(x) |x ∈ F} = f(u) (∀u ∈ PrRn(F˜ )). (3.21) Hence PrRn(F˜ ) ⊂ Sol(LF). To prove the reverse inclusion, we fix any x¯ ∈ Sol(LF) and apply the arguments in the first part of the proof of Theorem 2 in [83] (see also [77], [84]) to find a pair (u¯, v¯) ∈ F˜ which belongs to the solution set of (LD). The inclusion x¯ ∈ PrRn(F˜ ) now follows from the equality x¯ = u¯ by the construction in the proof of Theorem 2 in [83]. 2 Example Let us consider the following problem: (LF1) max { f(x) = x1 + 2x2 x1 + x2 + 1 ∣∣∣ 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1} we have F˜ = (u, v) ∈ R2 ×R2 ∣∣∣ u = (u1, u2) ≥ 0, v = (v1, v2) ≥ 0, u2 + v1 ≥ 1, v2 − u1 ≥ 2u1 + 2u2 ≥ v1 + v2, 0 ≤ u1, u2 ≤ 1  . By Theorem 3.4.2, Sol(P ) = PrR2(F˜ ) = {(u1, u2) |u2+v1 ≥ 1, v2−u1 ≥ 2, u1+2u2 ≥ v1+v2, 0 ≤ u1, u2 ≤ 1}. The optimal value of (LF ) is 1 and Sol(LF) = {(1, 1), (0, 1)}.