Some relations between variational-like inequalities and efficient solutions of certain nonsmooth optimization problems

SOME RELATIONS BETWEEN VARIATIONAL-LIKE INEQUALITIES AND EFFICIENT SOLUTIONS OF CERTAIN NONSMOOTH OPTIMIZATION PROBLEMS LUCELINA BATISTA SANTOS, MARKO A. ROJAS-MEDAR, AND ANTONIO RUFI ´ AN-LIZANA Received 28 November 2005; Revised 4 June 2006; Accepted 21 June 2006 We study the equivalence between the solutions of the variational-like inequality problem and the solutions of certain nonsmooth and nonconvex vectorial optimization problem. Copyright © 2006 Hindawi Publishing Corporation. All rights reserved. 1. Introduction The connections between variational inequalities and optimization problems is well known, and many investigators have discussed them along many years; see, for instance, [1,8,10,13]. This last article, which was authored by Giannessi, in particular, is one of the main works that study these connections in the finite-dimensional context. In recent years, the interest in the investigation on the relationships between these two classes of problems has increased, resulting in several different conditions for the existence of solutions for many variational-type inequalities (e.g., [5,16,19,20]). Connections among variational inequalities and vectorial optimization problems have also been studied in [11,18,25], for instance. By using a variational-like inequality, Lee et al. [19] obtained some results of existence of solutions for nonsmooth invex problems, which are generalizations of those obtained by Chen and Craven [4]fordifferentiable convex problems. Recently, Giannessi [11] showed the equivalence between efficient solutions of a differentiable and convex optimization problem and the solutions of a variational inequality of Minty type. He also proved the equivalence between weak efficient solutions of a differentiable convex optimization problem and solutions of a variational inequality of weak Minty type. Following this last line of investigation, Lee [17] was able to establish the equivalence between the solutions of the inequalities of Minty and Stampacchia types for subdifferential (in the convex analysis sense) and efficient solutions and weakly efficient solutions, respectively, in the case of vectorial nonsmooth convex optimization problems. Moreover, using these characterizations, he proved a theorem on existence of weakly efficient solutions for the vectorial nonsmooth convex optimization problem, under hypothesis of compactness. Hindawi Publishing Corporation International Journal of Mathematics and Mathematical Sciences Volume 2006, Article ID 26808, Pages 1–16 DOI 10.1155/IJMMS/2006/26808 2Efficient solutions In this work, we extend the results obtained early by Lee [17] for the nonsmooth invex context. This paper is organized as follows. In Section 2, we fix some basic notation and terminology. In Section 3, we prove some connections between efficient solutions and vectorial optimization problems; in Section 4,weconsiderthecaseofweaklyefficient solutions. Finally, in Section 5, we use the results of the previous sections to show an existence result of the weakly efficient solutions of nonsmooth invex vectorial optimization problem, under weak hypothesis of compactness. 2. Preliminaries In this section we recall some notions of nonsmooth analysis; for more details, see, for instance, Clarke [6]. Let Rnbe the n-dimensional Euclidean space and Rn +its nonnegative orthant. In the sequel Ωwill be a nonempty open subset of Rn. A function f:Ω→Ris said to be Lipschitz near x∈Ωif, for some K>0,  f(y)−f(z) ≤Ky−z, (2.1) for all y,zwithin some neighborhood of x.Wesaythat fis locally Lipschitz on Ωif fis Lipschitz near any given point of Ω.Thegeneralized directional derivative of fat xin the direction v, denoted by f0(x,v), is defined as follows: f0(x,v)=limsup y→x t↓0 1 tf(y+tv)−f(y).(2.2) The generalized gradient of fat x, denoted by ∂f(x), is the subset of Rngiven by ∂f(x)=ξ∈Rn:f0(x,v)≥ξ,v,∀v∈Rn, (2.3) where ·,· is the usual scalar product in Rn. The set ∂f(x)isnonemptywhen fis Lipschitz near x∈Ω. Let Xbe a nonempty subset of Rn.Thedistance function related to Xis the function dX:Rn→R,definedby dX(x)=inf x−y:y∈X.(2.4) The distance function is not differentiable everywhere but is globally Lipschitz. Let x∈X;avectorv∈Rnis said to be tangent to Xat xif d0 X(x,v)=0 and the set of the tangent vectors to Xat xis called Clarke tangent cone and denoted by TX(x). This set is a closed convex cone in Rn.TheClarke normal cone to Xat xcan be defined by polarity with TX(x): NX(x)=ξ∈Rn:ξ,v≤0, ∀v∈TX(x).(2.5) Lucelina Batista Santos et al. 3 Suppose that fis a locally Lipschitz function on Ωand attains a minimum over Xat x.Then, 0∈∂f(x)+NX(x).(2.6) We say that x∈Xis a Clarke stationary point of fover Xif (2.6)holds. Hanson [14] considered the differentiable functions f:Rn→Rsuch that for all x,y∈ Rn, there exists η(y,x)∈Rnsuch that f(y)−f(x)≥∇f(x),η(y,x).(2.7) Nowadays, such functions are generally known as invex functions due to Craven and Glover [7], who first named them so. This invexity notion generalizes the concept of convexity and allows to extend sufficient conditions of optimality and duality results to nonconvex optimization problems (see, e.g., [2,12,21]). Invexity has now been extended to nondifferentiable locally Lipschitz functions. See, for example, Craven and Glover [7], Reiland [23], and Phuong et al. [22]. We use the definition provided in [22]: let Xbe a nonempty subset of Ωand suppose that f:Ω→Ris a locally Lipschitz function on Ω. We say that fis invex on Xif, for every x,y∈X, there is η(y,x)∈TX(x)suchthat f(y)−f(x)≥f0x,η(y,x).(2.8) The above notion of invexity is very powerful because it allows to treat smooth and nonsmooth constrained problems, in the presence of an abstract constraint. In later sections we will deal with this subject. An important result obtained by Phuong et al. is the following invexity characterization; see [22]. Proposition 2.1. Let Xbe a nonempty subset of Ω. A locally Lipchitz function fis invex on Xif and only if every Clarke stationary point of fover Xis a global minimum. 3. Efficient solutions and variational-like inequalities Let Xbe a nonempty subset of Rnand let fi:Rn→R,i=1,...,p, be the given functions. We consider the following vectorial optimization problem: minimize f(x): =f1(x),...,fp(x)subject to x∈X. (P) As it is well known, differently from the case of scalar optimization problems, there is not a unique concept of solution for vectorial optimization problems. Amongst the numerous definitions of solutions for such problems existing in the literature, we will consider the followings. Definition 3.1. Apointy∈Xis said to be (i) an efficient solution of (P) if there is no other point x∈Xsuch that f(x)≤f(y), or equivalently, f(x)−f(y)/∈−Rn +\{0},∀x∈X; (3.1) 4Efficient solutions (ii) a weakly efficient solution of (P) if there is no other point x∈Xsuch that f(x)< f(y), or equivalently, f(x)−f(y)/∈−intRn +,∀x∈X; (3.2) (iii) a properly efficient solution of (P)ifitisefficient and if there exists M>0suchthat for each i, fi(x)−fi(y) fj(y)−fj(x)≤M(3.3) for some jsuch that fj(x)>f j(y), when x∈Xand fi(x)<f i(y). Remark 3.2. Some authors call the efficient solution as Pareto optimal solution. Also, weakly efficient solutions are also called weak-Pareto optimal solution or weak minimum. Remark 3.3. Kuhn and Tucker noted that some efficient solutions presented an undesirable property with respect to the ratio between the marginal profit of an objective function and the loss of some other functions. To these solutions, they introduced the concept of the noninferior proper solution. Subsequently, Geoffrion [9]modifiedthe concept slightly and defined the properly efficient solutions. Now, we assume that fiare locally Lipschitz and invex functions on Xwith respect to η. We consider in this section the following variational-like inequalities. Minty-type vectorial variational-like inequality (MVLI). Find y∈Xsuch that for each x∈Xand any ξi∈∂f i(x), i=1,...,p, ξT 1η(x,y),...,ξT pη(x,y)/∈Rn +\{0}.(3.4) Stampacchia-type vectorial variational-like inequality (SVLI). Find y∈Xsuch that for each x∈Xthere exist ξi∈∂f i(y), i=1,...,p,suchthat ξT 1η(x,y),...,ξT pη(x,y)/∈Rn +\{0}.(3.5) Proposition 3.4. Assume that XisanonemptysubsetofRnand fi:Rn→R,i=1,...,p, are invex locally Lipschitz functions on Xwith respect to η.Ify∈Xis a weakly efficient solution of (P), then it is a solution of MVLI. Proof. Let y∈Xbe an efficient solution of (P). Then, for any x∈X,wehave f(x)−f(y)/∈−Rn +\{0}.(3.6) Since fiis invex with respect to η,f0 i(x,η(y,x)) ≤fi(y)−fi(x); therefore, ξT iη(y,x)≤f0 ix,η(y,x)≤fi(y)−fi(x), ∀ξi∈∂f i(x).(3.7) From (3.6)and(3.7), we obtain that y∈Xis a solution of MVLI.  Lucelina Batista Santos et al. 5 Theorem 3.5. Let Xbe a nonempty subset of Rnand fi:Rn→R,i=1,...,p,areinvex locally Lipschitz functions on Xwith respect to η.Ify∈Xis a solution of SVLI, then yis an efficient solution of (P). Proof. Let y∈Xbe a solution of SVLI. Then for each x∈X, there exist ξi∈∂f i(y), i= 1,...,p,suchthat ξT 1η(x,y),...,ξT pη(x,y)/∈Rn +\{0}.(3.8) Since the functions fiareinvex,wehaveforeachx∈X, fi(x)−fi(y)≥f0 iy,η(x,y)≥ξT iη(x,y).(3.9) Hence, from (3.8)and(3.9)weobtain f1(x)−f1(y),...,fp(x)−fp(y)/∈Rn +\{0}, (3.10) and so y∈Xis an efficient solution of (P).  From Proposition 3.4 and Theorem 3.5, we have the following corollary. Corollary 3.6. Let Xbe a nonempty subset of Rnand fi:Rn→R,i=1,...,p,areinvex locally Lipschitz functions on Xwith respect to η.Ify∈Xis a solution of SVLI, then yis a solution of MVLI. Thus, SVLI is a sufficient condition for efficiency in (P). However, this condition is not necessary (see, e.g., [17, page 172]). We will show that it is a necessary condition for proper efficiency in (P). To prove the last assertion we will make use of the following result due to Jeyakumar [15]. Lemma 3.7. Let Γbe an arbitrary set, Ya Hausdorfftopological vector space, Dacompact subset of Y,andF:Γ×D→Ra function such that F(x,·)is concave and upper semicontinuous on Dfor each x∈Γfixed and F(·,y)is convex, for each y∈Dfixed. Then, inf x∈Γmax y∈DF(x,y)≥0⇐⇒ sup y∈D inf x∈Γ F(x,y)≥0.(3.11) Proposition 3.8. Let Xbe a compact subset of Rnand fi:Rn→R,i=1,...,p,areinvex locally Lipschitz functions with respect to ηon X. Consider the following assertions: (a) y∈Xis a properly efficient solution of (P); (b) there exist λi>0,i=1,...,p, such that yis a solution of the following scalar variational-like inequality: find y∈Xsuch that there exists ξi∈∂f i(y),i=1,...,p,such that for each x∈X, λ1ξ1+···+λpξpTη(x,y)≥0; (3.12) 6Efficient solutions (c) there exist λi>0,i=1,...,p, such that yis solution of the following scalar variationallike inequality: find y∈Xsuch that for each x∈X,thereexistsξi∈∂f i(y),i= 1,...,p, such that λ1ξ1+···+λpξpTη(x,y)≥0.(3.13) Then (a) and (b) are equivalent, and if η(·,y)is linear for each y∈X, then (a), (b), and (c) are equivalent. Proof. (a)⇒(b). If y∈Xis a properly efficient solution of (P). It follows from the invexity of the functions fion Xthat there exist λi>0, i=1,...,p, (see Brand˜ ao et al. [3]) such that y∈Xis a solution of the scalar optimization problem: minimize λ1f1(x)+···+λpfp(x)subjecttox∈X. (SP) We observe that the function λ1f1+···+λpfpis invex and thus 0∈∂p  i=1 λifi(y)+NX(y)⊂ p  i=1 λi∂f i(y)+NX(y).(3.14) Then, there exist μ∈NX(y)andξi∈∂f i(y), i=1,...,p,suchthat 0=μ+ p  i=1 λiξi.(3.15) On the other hand, η(x,y)∈TX(y), for all x∈Xand, furthermore, μ,η(x,y)≤0, ∀x∈X. (3.16) From (3.15)and(3.16)followsp i=1λiξi,η(x,y)≥0, for all x∈X, that is, λ1ξ1+···+λpξpTη(x,y)≥0.(3.17) Hence, (b) is proved. (b)⇒(a). We assume that there exists y∈Xsuch that ξi∈∂f i(y), i=1,...,p,suchthat for each x∈X(λ1ξ1+···+λpξp)Tη(x,y)≥0 is verified. We will assume that it is not a properly efficient solution of (P) and then exhibiting a contradiction. Suppose yis not a solution of the following scalar minimization problem (see [9]): minimize λ1f1(x)+···+λpfp(x), subject to x∈X(3.18) that is, there exists x∈Xsuch that p i=1λifi(x)<p i=1λifi(y) and, furthermore, p  i=1 λifi(x)−fi(y)<0.(3.19) Lucelina Batista Santos et al. 7 Now, using the invexity of the functions fi,weobtain p  i=1 λifi(x)−fi(y)≥ p  i=1 λif0 iy,η(x,y)≥ p  i=1 λiξT iη(x,y)≥0, (3.20) which contradicts (3.18). Hence, yis a properly efficient solution of (P). (b)⇔(c). We suppose that y∈Xand that there exist λi>0 such that there are ξi∈ ∂f i(y), i=1,...,p,suchthat,foreachx∈X,(λ1ξ1+···+λpξp)Tη(x,y)≥0isverified. Equivalently, max ξi∈∂f i(y)inf x∈Xλ1ξ1+···+λpξpTη(x,y)≥0.(3.21) Define D:= p  i=1 ∂f i(y), Γ:=X, F(x,ξ): =λ1ξ1+···+λpξpTη(x,y). (3.22) The function Fsatisfies the hypotheses of Lemma 3.7.Infact,forx∈Γfixed, F(x,·)is continuous on D(because it is a linear form defined between finite-dimensional spaces and, in particular, is upper semicontinuous). Moreover, F(x,·) is simultaneously concave and convex. Consequently, (3.21)isequivalentto inf x∈Xmax ξi∈∂f i(y)λ1ξ+···+λpξpTη(x,y)≥0 (3.23) and this last inequality is exactly the statement (b). Thus, (b) and (c) are equivalent.  From Proposition 3.8, we get the following theorem. Theorem 3.9. Let Xbe a compact and nonempty subset of Rnand fi:Rn→R,i=1,...,p, are invex locally Lipschitz functions on Xwith respect to η.Ifyis a properly efficient solution of (P), then yis a solution of SVLI. Proof. If yis a properly efficient solution of (P), then using Proposition 3.8, there exist λi>0, ξ∈∂f i(y), i=1,...,p,suchthat λ1ξ+···+λpξpTη(x,y)≥0, ∀x∈X. (3.24) In fact, assume that there exists x∈Xsuch that for each ξi∈∂f i(y), we have ξT 1η(x,y),...,ξT pη(x,y)∈−Rp +\{0}(3.25) 8Efficient solutions and we show a contradiction. Since λiare all strictly positive, we conclude p  i=1λiξiTη(x,y)<0, (3.26) which contradicts (3.24). Hence, yis solution of SVLI.  4. Weakly efficient solutions and variational-like inequalities In this section, we will consider variational-like inequalities of weak Minty and weak Stampacchia types, which we formulate as follows. Weak Minty variational-like inequality (WMVLI). Find y∈Xsuch that, for each x∈X and each ξi∈∂f i(x), i=1,...,p,wehave ξT 1η(x,y),...,ξT pη(x,y)/∈−intRp +.(4.1) Weak Stampacchia variational-like inequality (WSVLI). Find y∈Xsuch that for each x∈X, there exist ξi∈∂f i(y), i=1,...,p,suchthat ξT 1η(x,y),...,ξT pη(x,y)/∈−intRp +.(4.2) Under certain hypotheses, it is possible to show that the solutions of WMVLI and WSVLI are equals. Before, we prove this, will recall the following definition: given the function η:S×S→Rnwhere Sis a nonempty subset of Rn,wesaythatSis invex with respect to ηat x∈Sif for each y∈Sand each t∈[0,1], we have x+tη(y,x)∈S;wesay that Sis invex if it is invex for all x∈S. Theorem 4.1. Let XbeanonemptysubsetofRn, invex with respect to ηand fi:Rn→R, i=1,...,p, are invex locally Lipschitz functions with respect to η. (1) If yis a solution of WMVLI, then yis a solution of WSVLI. (2) Assume that the function ηis antisymmetric (i.e., η(x,y)=−η(y,x),∀x,y∈X)and that y∈Xis a solution of WSVLI. Then yis a solution of WMVLI. Proof. (1) We suppose that y∈Xis solution of WSVLI. Then, for each x∈X,thereare ξi∈∂f i(y), i=1,...,psuch that ξT 1η(x,y),...,ξT pη(x,y)/∈−intRp +.(4.3) Let  ξi∈∂f i(x), i=1,...,p.Weclaimthat(ξi− ξi)Tη(x,y)≤0, i=1,...,p.Infact,from the antisymmetry of ηand (4.3), we have ξi− ξiTη(x,y)=ξiη(x,y)− ξiη(x,y)=ξiη(x,y)+ ξiη(y,x).(4.4) Also, since fiis invex, ξT iη(x,y)≤f) iy,η(x,y)≤fi(x)−fi(y), i=1,...,p,  ξi Tη(y,x)≤f0 ix,η(y,x)≤fi(y)−fi(x), i=1,...,p, (4.5) Lucelina Batista Santos et al. 9 and adding (4.5), we obtain ξi− ξiTη(x,y)≤0, i=1,...,p, (4.6) that is, for each x∈Xand each  ξi∈∂f i(x), i=1,...,p,wehave  ξ1 Tη(x,y),..., ξp Tη(x,y)≥ξT 1η(x,y),...,ξT pη(x,y)/∈−intRp +(4.7) and, consequently,  ξ1 Tη(x,y),..., ξp Tη(x,y)/∈−intRp +; (4.8) thus, yis a solution of WMVLI. (2) We will prove the statement (2). For that, we suppose that y∈Xis a solution of WMVL. In this case, for each x∈Xand each ξi∈∂f i(x), i=1,...,p,wehave(ξT 1η(x,y), ...,ξT pη(x,y)) /∈−intRp +.Forz∈Xfixed, we consider the sequence (αk)⊂(0,1], with αk→0whenk→∞and we define zk:=y+αkη(z,y). Since Xis invex with respect to η, then the sequence (zk)belongstoX. The set ∂f i(zk) is nonempty and therefore we can take ξk i∈∂f i(zk), i=1,...,p,foreachk∈N.Butyis a solution of WMVLI and therefore ξkT 1η(x,y),...,ξkT pη(x,y)/∈−intRp +.(4.9) Without loss of generality, we can suppose that all the functions fihavethesameLipschitz constant K.Sinceξk i∈∂f i(zk), for each k,wehaveξk i≤K,fori=1,...,p.For each i,(ξk i)k∈Nis a bounded sequence in Rnand we can assume that ξk i→ ξiwhen k→∞, for some  ξi∈Rn.Also,ξk i∈∂f i(zk)foreachkand zk→yand since the set-valued mapping ∂f iis closed (see [6]), we obtain  ξi∈∂f i(y), i=1,...,p.Takingk→∞in (4.9)and observing that the set (−intRp +)cis closed in Rp,weobtain  ξ1 Tη(x,y),..., ξp Tη(x,y)/∈−intRp +.(4.10) Hence, y∈Xis a solution of WSVLI.  Theorem 4.2. Let XbeanonemptysubsetofRn, invex with respect to ηand fi:Rn→R, i=1,...,p, invex locally Lipschitz functions with respect to ηon X. Then (1) if y∈Xis a solution of WSVLI, then yis a weakly efficient solution of (P); (2) if ηis antisymmetric, then y∈Xis a weakly efficient solution of (P)if and only if y is a solution of WSVLI. Proof. Initially suppose that y∈Xis not a weakly efficient solution of (P). Then there exists z∈Xsuch that fi(y)>f i(z), i=1,...,p. (4.11) 16 Efficient solutions [10] F. Giannessi, Theorems of alternative, quadratic programs and complementarity problems, Variational Inequalities and Complementarity Problems (Proc. Internat. School, Erice, 1978) (R. W. Cottle, F. Giannessi, and J.-L. Lions, eds.), Wiley, Chichester, 1980, pp. 151–186. [11] ,On Minty variational principle, New Trends in Mathematical Programming, Appl. Optim., vol. 13, Kluwer Academic, Massachusetts, 1998, pp. 93–99. [12] G. Giorgi and A. Guerraggio, Various types of nonsmooth invex functions, Journal of Information & Optimization Sciences 17 (1996), no. 1, 137–150. [13] R. Glowinski, J.-L. Lions, and R. Tr´ emoli` eres, Numerical Analysis of Variational Inequalities, North-Holland, Amsterdam, 1976. [14] M. A. Hanson, On sufficiency of the Kuhn-Tucker conditions, Journal of Mathematical Analysis and Applications 80 (1981), no. 2, 545–550. [15] V. Jeyakumar, A generalization of a minimax theorem of Fan via a theorem of the alternative, Journal of Optimization Theory and Applications 48 (1986), no. 3, 525–533. [16] I. V. Konnov and J. C. Yao, On the generalized vector variational inequality problem,Journalof Mathematical Analysis and Applications 206 (1997), no. 1, 42–58. [17] G. M. Lee, On relations between vector variational inequality and vector optimization problem, Progress in Optimization (Perth, 1998) (X. Q. Yang, A. I. Mees, M. E. Fisher, and L. S. Jennings, eds.), Appl. Optim., vol. 39, Kluwer Academic, Dordrecht, 2000, pp. 167–179. [18] G. M. Lee, D. S. Kim, and H. Kuk, Existence of solutions for vector optimization problems,Journal of Mathematical Analysis and Applications 220 (1998), no. 1, 90–98. [19] G. M. Lee, D. S. Kim, B. S. Lee, and N. D. Yen, Vector variational inequality as a tool for studying vector optimization problems, Nonlinear Analysis 34 (1998), no. 5, 745–765. [20] G. M. Lee and S. H. Kum, On implicit vector variational inequalities, Journal of Optimization Theory and Applications 104 (2000), no. 2, 409–425. [21] S. Park, Some coincidence theorems on acyclic multifunctions and applications to KKM theory, Fixed Point Theory and Applications (Halifax, NS, 1991), World Scientific, New Jersey, 1992, pp. 248–277. [22] T.D.Phuong,P.H.Sach,andN.D.Yen,Strict lower semicontinuity of the level sets and invexity of a locally Lipschitz function, Journal of Optimization Theory and Applications 87 (1995), no. 3, 579–594. [23] T. W. Reiland, Nonsmooth invexity, Bulletin of the Australian Mathematical Society 42 (1990), no. 3, 437–446. [24] R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, no. 28, Princeton University Press, New Jersey, 1970. [25] X. Q. Yang, Generalized convex functions and vector variational inequalities,JournalofOptimization Theory and Applications 79 (1993), no. 3, 563–580. Lucelina Batista Santos: Departamento de Matem´ atica, Universidade Federal do Paran´ a, CP 19081 CEP, 81531-990 Curitiba, Paran´ a, Brazil E-mail address:luc[email protected].br Marko A. Rojas-Medar: Departamento de Matem´ atica Aplicada, Universidade Estadual de Campinas, CP 6065, 13083-859 Campinas, S˜ ao Paulo, Brazil E-mail address:mark[email protected] Antonio Rufi´ an-Lizana: Departamento de Estad´ ıstica e Investigaci´ on Operativa, Universidad de Sevilla, 41012 Sevilla, Spain E-mail address:[email protected]