Nội dung

Yugoslav Journal of Operations Research 27 (2017), Number 2, 205–218 DOI: https://doi.org/10.2298/YJOR170121010S OPTIMALITY AND DUALITY FOR NONSMOOTH SEMI-INFINITE MULTIOBJECTIVE PROGRAMMING WITH SUPPORT FUNCTIONS Yadvendra SINGH Department of Mathematics,Banaras Hindu University, Varanasi-221005, India ysinghze@gmail.com S.K.MISHRA Department of Mathematics,Banaras Hindu University, Varanasi-221005, India bhu.skmishra@gmail.com K.K.LAI Department of Management Sciences, City University of Hong Kong, Kowloon, Hong Kong, China,Jockey Club School of Public Health and Primary Care, Faculty of Medicine,The Chinese University of Hong Kong, Shatin, Hong Kong, China mskklai@cityu.edu.hk Received: January 2017 / Accepted: May 2017 Abstract: In this paper, we consider a nonsmooth semi-infinite multiobjective programming problem involving support functions. We establish sufficient optimality conditions for the primal problem. We formulate Mond-Weir type dual for the primal problem and establish weak, strong and strict converse duality theorems under various generalized convexity assumptions. Moreover, some special cases of our problem and results are presented. Keywords: Nonsmooth Semi-infinite Multiobjective Optimization, Generalized Convexity, Duality. MSC: 90C34,90C46,26A5. 1. INTRODUCTION Semi-infinite multiobjective programming problems arise when more than one objective function is to be optimized over feasible set described by infinite 206 Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth number of inequality constraints. If there is only one objective function, then the problems are reduced to scalar semi-infinite programming problems. Semiinfinite programming problems have been an active research topic due to their applications in several areas of modern research such as in engineering design, mathematical physics, robotics, optimal control, transportation problems, see [8, 11, 16, 23]. Optimality conditions and duality results for semi-infinite programming problems have been studied, see [9, 12, 17, 18, 20, 24, 34, 36]. Caristi et al. [3] obtained optimality and duality results for semi-infinite multiobjective programming problems that involved differentiable functions. Kanzi and Nobakhtian [19] obtained several kinds of constraints qualifications, necessary and sufficient optimality conditions for nonsmooth semi-infinite multiobjective programming problems. Recently, Chuong and Kim [7] and Son and Kim [37] obtained optimality and duality for nonsmooth semi-infinite multiobjective programming problems. Many authors have discussed optimality conditions and duality results for nonlinear programming problems containing the square root of a positive semidefinite quadratic function, for example those discussed by Mond [31] and Zang and Mond [38]. Mishra et al. [25] proved necessary and sufficient optimality conditions for nondifferential semi-infinite programming problems involving square root of quadratic functions, see, for more details [6, 32, 33, 35]. Furthermore, the term with the square root of a positive semidefinite quadratic function has been replaced by a more general function, namely, the support function of a compact convex set, whose the subdifferential can be simply expressed. Mond and Schechter [30] have constructed symmetric duality of both Wolfe and MondWeir types for nonlinear programming problems where the objective contains the support function. Husain et al. [13] have obtained optimality and duality for a nondifferentiable nonlinear programming problem involving support function, see for more details [1, 14, 21, 22] and references therein. Convexity and their generalizations play an important role in optimization theory. The class of invex functions was introduced by Hanson [10] and named by Craven [4] as a generalization of convexity. Jayekumar and Mond [15] generalized Hanson’s definition to vectorial case. Later, several other generalizations of invex functions have been introduced, for details see Mishra at el. [26, 27] and references therein. This article is organized as follows: In Section 2, definitions and preliminaries are given. In Section 3, we establish the sufficient optimality conditions for multiobjective semi-infinite programming problems involving support functions. In Section 4, we formulate Mond-Weir type dual for multiobjective semi-infinite programming problems involving support functions and establish weak, strong and strict-converse duality theorems under generalized convexity assumptions. In Section 5, we discuss some special cases of the primal and dual problems. 2. DEFINITIONS AND PRELIMINARIES In this section, we present some definitions and results which will be needed in the sequel. Let Rn be the n-dimensional Euclidean space and R+n be the nonnegative orthant of Rn . Let h., .i denotes the Euclidean inner product and k.k be Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth 207 Euclidean norm in Rn . Given a nonempty set D ⊆ Rn , we denote the closure of D by D̄ and convex cone (containing origin) by cone(D). The native polar cone and the strictly negative polar cone are defined respective by D≤ := {d ∈ Rn |hx, di ≤ 0, ∀x ∈ D}, D< := {d ∈ Rn |hx, di < 0, ∀x ∈ D}. Definition 2.1. [5] Let D ⊆ Rn . The contingent cone T(D, x) at x̄ ∈ D̄ is defined by T(D, x̄) := {d ∈ Rn |∃ tk ↓ 0, ∃ dk → d : x̄ + tk dk ∈ D ∀k ∈ N}. Definition 2.2. [5] A function f : Rn → R is said to be Lipschitz near x ∈ Rn , if there exist a positive constant K and a neighborhood N of x such that for any y, z ∈ N, one has | f (y) − f (z)| ≤ K k y − z k The function f is said to be locally Lipschitz on Rn if it is Lipschitz near x for every x ∈ Rn . Definition 2.3. [5] The Clarke generalized directional derivative [5] of a locally Lipschitz function f at x ∈ Rn in the direction d ∈ Rn , denoted by f o (x; d), is defined as f o (x; d) = lim sup t↓0, y→x f (y + td) − f (y) t where y is a vector in Rn . Definition 2.4. [5] The Clarke generalized subdifferential of f at x ∈ Rn is denoted by ∂c f (x), defined as ∂c f (x) = {ξ ∈ Rn : f o (x; d) ≥ hξ, di, ∀d ∈ Rn }. Definition 2.5. [26] A locally Lipschitz function f : Rn → R is said to be invex at x∗ ∈ Rn if there exists an n-dimensional vector valued function η : Rn × Rn → Rn such that f (x) − f (x∗ ) ≥ hξ, η(x, x∗ )i, for each x ∈ Rn and every ξ ∈ ∂c f (x∗ ). The function f is said to be invex near x∗ ∈ Rn if it is invex at each point of neighborhood of x∗ ∈ Rn . Definition 2.6. [26] A locally Lipschitz function f : Rn → R is said to be strictly invex at x∗ ∈ Rn if there exists an n-dimensional vector valued function η : Rn × Rn → Rn such that f (x) − f (x∗ ) > hξ, η(x, x∗ )i, for each x ∈ Rn , x , x∗ and every ξ ∈ ∂c f (x∗ ). The function f is said to be strictly invex near x∗ ∈ Rn if it is strictly invex at each point of neighborhood of x∗ ∈ Rn . 208 Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth Definition 2.7. [26] A locally Lipschitz function f : Rn → R is said to be pseudo invex at x∗ ∈ Rn if for all x ∈ Rn , there exists an n-dimensional vector valued function η : Rn × Rn → Rn such that hξ, η(x, x∗ )i ≥ 0, for some ξ ∈ ∂c f (x∗ ) ⇒ f (x) ≥ f (x∗ ). Definition 2.8. [26] A locally Lipschitz function f : Rn → R is said to be strictly pseudo invex at x∗ ∈ Rn if for all x ∈ Rn , x , x∗ , there exists an n-dimensional vector valued function η : Rn × Rn → Rn such that hξ, η(x, x∗ )i ≥ 0, for some ξ ∈ ∂c f (x∗ ) ⇒ f (x) > f (x∗ ). Definition 2.9. [26] A locally Lipschitz function f : Rn → R is said to be quasi-invex at x∗ if there exists an n-dimensional vector valued function η : Rn × Rn → Rn such that f (x) ≤ f (x∗ ) ⇒ hξ, η(x, x∗ )i ≤ 0, for each x ∈ Rn and every ξ ∈ ∂c f (x∗ ). The function f is said to be quasi-invex near x∗ ∈ Rn if it is quasi-invex at each point of neighborhood of x∗ ∈ Rn . Remark 2.1. [26] 1. Every invex function is also quasi-invex for the same η, but not conversely. 2. Every invex function is also pseudo-invex for the same η, but not conversely. 3. Every strictly invex function is also strictly pseudo-invex for the same η, but not conversely. Let C be a nonempty compact convex set in Rn . The support function S(.|C) : R → R ∪ {+∞} is given by n S(x|C) = max{hz, xi : z ∈ C}. Example 2.1. If C = [0, 1], then the support function S(·|C) : R → R ∪ {+∞} is given by S(x|C) = max{zx : z ∈ C}. S(x|C) = |x| + x 2 The support function, being convex and everywhere finite, has a Clark subdifferential [5], in the sense of convex analysis. Its subdifferential is given by ∂S(x|C) = {z ∈ C : hz, xi = S(x|C)}. For any nonempty set S ⊆ Rn , the normal cone to S at the point x ∈ S is denoted by NS (x) and defined as follows: NS (x) = {y ∈ Rn : hy, z − xi ≤ 0, ∀z ∈ S}. Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth 209 It is easy to verify that for a compact convex set C, y ∈ Nc (x) if and only if S(y|C) = hx, yi or equivalently, x is in the subdifferential of S at y. In this paper, we consider the following nonsmooth semi-infinite multiobjective programming problem :   (MOSIP) min f1 (x) + S(x|C1 ), ..., fp (x) + S(x|Cp ) subject to 1i (x) ≤ 0, i∈I x∈R , n where I is an index set which is possibly infinite, f j , j = 1, 2, ..., p and 1i , i ∈ I are locally Lipschitz functions from Rn to R ∪ {+∞}. Let M denote the feasible solutions of (MOSIP). M := {x ∈ Rn |1i (x) ≤ 0 ∀i ∈ I}.  Let x∗ ∈ M. We denote I(x∗ ) = i ∈ I : 1i (x∗ ) = 0 , the index set of active constraints and let p [   F(x∗ ) := ∂c f j (x∗ ) + S(x∗ |C j ) , j=1 G(x∗ ) := [ ∂c 1i (x∗ ). i∈I(x∗ ) The following constraint qualifications are generalization of constraint qualifications from [19] for multiobjective programming problem with support functions (MOSIP). Definition 2.10. We say that: (a) The Abedie contraint qualification(ACQ) holds at x∗ ∈ M if G≤ (x∗ ) ⊆ T(M, x∗ ). (b) The Basic constraint qualification (BCQ) holds at x∗ ∈ M if T≤ (M, x∗ ) ⊆ cone(G(x̄)). (c) The Regular contraint qualification(RCQ) holds at x̄ ∈ M if F< (x∗ ) ∩ G≤ x∗ ) ⊆ T(M, x∗ ). Definition 2.11. A feasible point x∗ ∈ M is said to be weakly efficient solution for (MOSIP) if there is no x ∈ M such that f j (x) + S(x|C j ) < f j (x∗ ) + S(x∗ |C j ) for all j = 1, 2, ..., p. Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth 210 3. OPTIMALITY CONDITIONS In this section, we prove the sufficient optimality conditions for considered nonsmooth semi-infinite multiobjective programming problem (MOSIP). For this, Theorem 3.4 (ii) from Kanzi and Nobakhtian [19] can be generalized for the multiobjective semi-infinite programming problem with support functions(MOSIP) as follows: Theorem 3.1. [Necessary optimality conditions] Let x∗ be a weakly efficient solution for (MOSIP) and assume that a suitable constraints qualification from Definition 2.10 holds at x∗ . If cone(G (x*)) is closed, then there exist τ j ≥ 0 , z j ∈ C j ( for j = 1, 2, ..., p)and λi ≥ 0 (for i ∈ I(x∗ )) with λi , 0 for finitely many indices i, such that 0∈ p X λi ∂c 1i (x∗ ), (1) i∈I(x∗ ) j=1 p X X τ j [∂c f j (x∗ ) + z j ] + τ j = 1, (2) j=1 hz j , x∗ i = S(x∗ |C j ), j = 1, ..., p. (3) ∗ Theorem 3.2. [Sufficient optimality conditions] Let x be feasible for (MOSIP) and I(x∗ ) is nonempty. Assume that there exist τ j > 0, z j ∈ C j (for j = 1, 2, ..., p) and scalars λi ≥ 0 for i ∈ I(x∗ )) with λi , 0 for finitely many indices i, such that necessary optimality conditions (1)-(3) hold at x∗ . If τ j ( f j (.) + hz j , .i), for j = 1, 2, ..., p are pseudo-invex and λi 1i (·), i ∈ I(x∗ ) are quasi-invex at x∗ with respect to the same η, then x∗ is a weakly efficient solution for (MOSIP). Proof : We proceed by contradiction. Suppose, contrary to the result, that x∗ ∈ M is not a weakly efficient solution for (MOSIP). Then, there exists a feasible point x ∈ M for (MOSIP) such that f j (x) + S(x|C j ) < f j (x∗ ) + S(x∗ |C j ), for all j = 1, ..., p, thus, we have p X p h i X h i τ j f j (x) + S(x|C j ) < τ j f j (x∗ ) + S(x∗ |C j ) . j=1 j=1 (4) Since hz, xi ≤ S(x|C) and the assumption hz j , x∗ i = S(x∗ |C j ), j = 1, ..., p, we have p X p i X h i τ j f j (x) + hz j , xi < τ j f j (x∗ ) + hz j , x∗ i . j=1 j=1 h (5) From (1), there exist ξ j ∈ ∂c f j (x∗ ) and ζi ∈ ∂c 1i (x∗ ) such that p X j=1   X τj ξj + zj + λi ζi = 0. i∈I(x∗ ) (6) Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth Since x is a feasible point for (MOSIP) and λi 1i (x∗ ) = 0, i ∈ I(x∗ ) X X λi 1i (x) ≤ λi 1i (x∗ ), i∈I(x∗ ) 211 (7) i∈I(x∗ )
Thus, from pseudo-invexity of τi fi (·) + hzi , ·i , for i = 1, 2, ..., p we have p X h i τ j f j (x) + hz j , xi ≥ j=1 p X h i τ j f j (x∗ ) + hz j , x∗ i , j=1 which contradicts (5). This completes the proof. The following corollary is a direct consequence of Remark 2.1 and Theorem 3.2. Corollary 3.1. Let x∗ be feasible for (MOSIP) and I(x∗ ) is nonempty. Assume that there exist τ j > 0, z j ∈ C j (for j = 1, 2, ..., p) and scalars λi ≥ 0 (for i ∈ I(x∗ )) with λi , 0 for finitely many indices i, such that necessary optimality conditions (1)-(3) hold at x∗ . If τ j ( f j (.) + hz j , .i), for j = 1, 2, ..., p are invex and λi 1i (·), i ∈ I(x∗ ) are invex at x∗ with respect to the same η, then x∗ is a weakly efficient solution for (MOSIP). We now give an example to illustrate the above theorem for a particular multiobjective semi-infinite programming problem. Example 3.1. We consider the following problem: (MOSIP) min f1 (x) + S(x|C1 ), f2 (x) + S(x|C2 ) subject to 1i (x) ≤ 0,
∀i ∈ I x ∈ R, where, I := {2, 3, ...} and f1 , f2 , S(x|C1 ), S(x|C2 ) are functions defined as: f1 (x) = −x, f2 (x) = x2 , S(x|C1 ) = S(x|C2 ) = |x| for C1 = C2 = [−1, 1] and ( 1 i x, x ≥ 0; 1i (x) = x, x < 0. The feasible solution for problem (MOSIP) is M := (−∞, 0] and for x̄ = 0 ∈ M, I(x̄) = I. It is easy to verify that all defined functions are locally Lipschitz at x̄ = 0. Also, ∂ f1 (x̄) = −1, ∂ f2 (x̄) = 0, ∂1i (x̄) = [ 1i , 1], i = 2, 3, · · · . Clearly necessary optimality conditions (1) − (3) of Theorem 3.1 hold at x̄ ∈ M, as there exist τ1 = τ2 = 12 , z1 = −1, z2 = 0, λ = (1, 0, 0, ...), ξ1 = −1, ξ2 = 0, ζi = 1, for i ∈ I, such that 2 X   X 1 τj ξj + zj + λi ζi = (−1 − 1) + 0 + 1 = 0. 2 ∗ j=1 i∈I(x ) It is verified that τi ( fi (x) + hzi , xi), for i = 1, 2 are pseudo-invex at x̄ and λi 1i (x) are quasi-invex at x̄ with respect to η(x, x̄) = x − x̄. We observe that there is no x ∈ M, such that f j (x) + S(x|C j ) < f j (x̄) + S(x̄|C j ) for all j = 1, 2. Hence, x̄ = 0 is a weakly efficient solution for (MOSIP). Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth 212 4. DUALITY Many authors have formulated Mond-Weir type dual and established duality results in various optimization problems with support functions; see [1, 2, 13, 21, 22, 30] and the references therein. Following the above mentioned works, we formulate Mond-Weir type dual for nonsmooth semi-infinite programming problem with support function (MOSIP) and establish duality theorems.   (MOSID) Max f1 (y) + hz1 , yi, ..., fp (y) + hzp , yi 0∈ p X   X τ j ∂c f j (y) + z j + λi ∂c 1i (y), j=1 X (8) i∈I λi 1i (y) ≥ 0, (9) i∈I We now discuss the weak, strong and strict converse duality for the pair (MOSIP) and (MOSID). Theorem 4.1. [Weak Duality] Let x be feasible for (MOSIP) and (y, τ, λ, z1 , ..., zp ) be feasible for (MOSID). If τ j ( f j (·)+hz j , ·i) for j = 1, 2, ..., p are pseudo-invex and λi 1i (·), i ∈ I are quasi-invex at y with respect to the same η. Then the following cannot hold: f j (x) + S(x|C j ) < f j (y) + hz j , yi for all j = 1, ..., p. Proof: Let x be feasible for (MOSIP) and (y, τ, λ, z1 , ..., zp ) be feasible for (MOSID), then 0∈ p X   X τ j ∂c f j (y) + z j + λi ∂c 1i (y), j=1 X (10) i∈I λi 1i (y) ≥ 0, (11) i∈I According to (10), there exist ξ j ∈ ∂c f j (y) and ζi ∈ ∂c 1i (y) such that p X j=1   X τj ξj + zj + λi ζi = 0 i∈I (12) Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth 213 We proceed to the result of the theorem by contradiction. Assume that f j (x) + S(x|C j ) < f j (y) + hz j , yi for all j = 1, ..., p. Thus, we have p X p h i X h i τ j f j (x) + (S(x|C j ) < τ j f j (y) + hz j , yi . j=1 (13) j=1 Using the inequality hz, xi ≤ S(x|C) , we have p X p i X h i τ j f j (x) + hz j , xi < τ j f j (y) + hz j , yi . h j=1 (14) j=1 As x is feasible for (MOSIP) and (y, τ, λ, z1 , ..., zp ) is feasible for (MOSID), we have X X λi 1i (x) ≤ λi 1i (y). i∈I i∈I From definition of quasi-invexity, we have *X + λi ζi , η(x, y) ≤ 0, (15) i∈I for each x ∈ X and every ζi ∈ ∂c 1i (x). Multiplying (12) by η(x, y) and using (15), we get *X p   + τ j ξ j + z j , η(x, y) ≥ 0, j=1 for each x ∈ X and some ξ j ∈ ∂c f j (y). Thus, from definition of pseudo-invexity, we have p X j=1 p i X h i τ j f j (x) + hz j , xi ≥ τ j f j (y) + hz j , yi , h j=1 which contradicts (14). This completes the proof. The following corollary is a direct consequence of Remark 2.1 and Theorem 4.1. 214 Y., Singh, S.K., Mishra, K.K., Lai / Optimality and Duality for Nonsmooth Corollary 4.1. Let x be feasible for (MOSIP) and (y, τ, λ, z1 , ..., zp ) be feasible for (MOSID). If τ j ( f j (·) + hz j , ·i) for j = 1, 2, ..., p and λi 1i (·), i ∈ I are invex at y with respect to the same η. Then the following cannot hold: f j (x) + S(x|C j ) < f j (y) + hz j , yi for all j = 1, ..., p. The following example shows that the generalized invexity imposed in the above theorem is essential. Example 4.1. We consider the following problem:
min f1 (x) + S(x|C1 ), f2 (x) + S(x|C2 ) (MOSIP) subject to 1i (x) ≤ 0, i∈I x ∈ R, where, I := N and f1 , f2 , S(x|C1 ), S(x|C2 ) are functions defined as: f1 (x) = −2x, f2 (x) = x2 , S(x|C1 ) = S(x|C2 ) = |x| for C1 = C2 = [−1, 1] and 1i (x) = −i|x|, for i ∈ I. The feasible solution for problem (MOSIP) is M := R and let set x̄ = 1 ∈ M. The Mond-Weir dual for (MOSIP) can be given as:   (MOSID) max −2y + z1 , y2 + z2 y 0∈ 2 X   X τ j ∂ f j (y) + z j + λi ∂1i (y), j=1 i∈I X λi 1i (y) ≥ 0, i∈I P y ∈ Rn , τ j ≥ 0, 2j=1 τ j = 1, λi ≥ 0 with λ = (λi )i∈I , 0 for finitely many indices i ∈ N and z j ∈ C j , for j = 1, 2. By choosing ȳ = 0, τ1 = τ2 = 21 , z1 = 1, z2 = 0 and λ = (1, 0, ...). We have (y, τ, λ, z1 , z2 ) as a feasible point of (MOSID). Observe that λi 1i (·) at y is not quasi-invex with respect to η(y, ȳ) = y − ȳ and that f1 (x̄) + S(x̄|C1 ) = −1 < f1 (y) + hz1 , yi = −y + y = 0 holds. This means that quasi-invexity and pseudo-invexity are essential for weak duality as described in Theorem 4.1 . The following theorem gives strong duality relation between the primal problem (MOSIP) and the dual problem (MOSID). Theorem 4.2. [Strong Duality] Let x be a weakly efficient solution for (MOSIP) at which a suitable constraints from Definition 2.10 holds at x∗ and cone(G(x)) is closed. If the pseudo-invexity and quasi-invexity assumptions of the weak duality theorem are satisfied, then there exists (τ, λ, z1 , ..., zp ) such that (x, τ, λ, z1 , ..., zp ) is a weakly efficient solution for (MOSID) and the respective objective values are equal.