Duality in Nondifferentiable Vector Programming

Ž. Journal of Mathematical Analysis and Applications 259, 462᎐475 2001 doi:10.1006rjmaa.2000.7417, available online at http:rrwww.idealibrary.com on Duality in Nondifferentiable Vector Programming R. Osuna-Gomez, A. Rufian-Lizana, and P. Ruız-Canales ´´ ´ Departamento de Estadıstica e In¨estigacion Operati¨a, Fac. de Matematicas, ´´ crTaeria srn 41012 Se¨ille, Spain E-mail: [email protected] Submitted by Augustine Esogbue Received January 8, 1998 In this paper we study the saddle point optimality conditions and Lagrange duality in multiobjective optimization for generalized subconvex-like functions. We obtain results which will allow us to characterize the solutions for multiobjective programming problems from the saddle point conditions and allow us to relate them to the dual problem solutions which will be adequately defined. We also define a new dual problem for the multiobjective programming problem with the special property of being a scalar programming problem. 䊚 2001 Academic Press 1. INTRODUCTION Lagrange duality is an attractive topic in optimization theory. In the past few years, several studies have been dedicated to this subject, discussing it wx within the multiobjective optimization theory framework 1, 2, 5, 9, 11, 12 . One of the basic questions is how to weaken the assumptions of the known results, as well as defining adequate dual problems that might facilitate the search for solutions of multiobjective optimization problems. The vector optimization problem considered in this paper can be formulated as VOP Min fx Ž. Ž. s.t. gxO0, Ž. n xgS:⺢, where f:S:⺢nª⺢pand g:S:⺢nª⺢m. Let us denote by Xthe set of feasible points for this problem, that is,  nŽ. 4 XsxgS:⺢such that gxO0. 462 0022-247Xr01 $35.00 Copyright 䊚2001 by Academic Press All rights of reproduction in any form reserved. NONDIFFERENTIABLE VECTOR DUALITY 463 There does not exist a unique solution concept for vectorial programming problems such as occurs for scalar programming problems. Amongst the numerous definitions of solutions for multiobjective optimization problems which exist in the literature, we will emphasize those we consider the most important, and those will be the ones used in this work. Ž DEFINITION 1.1. xgXis said to be an efficient solution a weakly .Ž. efficient solution of Problem VOP if there exists no other feasible x Ž. Ž.ŽŽ. Ž.. such that fxFfx fx-fx. 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. To these solutions, they introduced the concept of the noninferior proper solution. Subsewx quently, Geoffrion 6 modified the concept slightly and defined the properly efficient solutions for a multiobjective problem as follows. DEFINITION 1.2. xgXis said to be a properly efficient solution of Ž. Problem VOP if it is efficient and if there exists a scalar M)0 such that, for each i, we have fxyfx Ž. Ž. ii -M fxyfx Ž. Ž. jj Ž. Ž. Ž. Ž. for some jsuch that fx)fxwhenever xgXand fx-fx. jj ii This paper consists of six parts. In Section 2, some basic definitions and theorems are first introduced. Sections 3 and 4 discuss saddle point theorems for multiobjective programming problems. Section 5 addresses the Lagrange duality, and Section 6 introduces a new dual problem for the multiobjective problem with the special property of being a scalar programming problem. Some conclusions are given in Section 7. 2. BASIC RESULTS AND PRELIMINARIES First, we introduce a few notations and definitions. Ž. TŽ. Tp Let xsx,..., x,ysy,..., yg⺢, then 1p1p xsyiff xsy,is1,..., p; ii xOyiff xFy,is1,..., p; ii xFyiff xFy,is1,..., p, ii with strict inequality holding for at least one i; x-yiff x-y,is1,..., p. ii OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES ´´ ´ 464 If f:S:⺢nª⺢p, we denote by fthe ith component of f; i.e., i Ž. Ž Ž. Ž.. T fxsfx,..., fx . 1p wx Yang 15 defined the concept of generalized subconvex-like functions and provided an alternative theorem for these functions. DEFINITION 2.1. Let f:S:⺢nª⺢p.fis said to be generalized pŽ. subconvex-like on Sif ᭚ug⺢,u)0, such that ᭙ ␣ g0, 1 , ᭙x,xgS, 12 and ᭙ ⑀ )0, ᭚xgS,᭚ ␳ )0 such that 3 ⑀ uq ␣ fx q1y ␣ fx G ␳ fx . Ž. Ž .Ž. Ž. 123 For these functions was proved the following generalized alternative wx theorem 15 . Ž. THEOREM 2.1 Generalized Alternative Theorem . Let S be a nonempty set in ⺢nand let f:Sª⺢pbe a generalized subcon¨ex-like function on S. Then either Ž. Ž . ifx-0has a solution x gS,or Ž. TŽ. p ii wfxG0for all x gS,for some w g⺢,wG0, but both alternati¨es are ne¨er true. Note 2.1. In the previous theorem, we can suppose that wTes1 since Žp.T if not, defining ¨swrÝw, we have that ¨es1, and this ¨verifies js1j TŽ. that ¨fxG0᭙xgS. Now we show some useful properties of the generalized subconvex-like functions that will be used subsequently. LEMMA 2.1. If f is a generalized subcon¨ex-like function and M )0, then Mf is a generalized subcon¨ex-like function with respect to the same point. pŽ. Proof. If there exists ug⺢,u)0, such that ᭙ ␣ g0, 1 , ᭙x,xgS, 12 and ᭙ ⑀ )0, ᭚xgSand ᭚ ␳ )0 such that 3 ⑀ uq ␣ fx q1y ␣ fx G ␳ fx , Ž. Ž .Ž. Ž. 123 then for u⬘sMu )0 and ␳ ⬘sM ␳ )0, Mf is generalized subconvex-like on Swith respect to the same point x. 3 LEMMA 2.2. Let f:Sª⺢pbe a generalized subcon¨ex-like function on S.Then for all i,js1,..., p,fqf is a generalized subcon¨ex-like function ij with respect to the same point. Proof. If fis generalized subconvex-like, then for any i,js1,..., p Ž. there exist u,u)0 such that ᭙ ␣ g0, 1 , ᭙x,xgS, and ᭙ ⑀ )0 ij 12 ᭚xgS,᭚ ␳ )0 such that 3 ⑀ uq ␣ fx q1y ␣ fx G ␳ fx Ž. Ž .Ž. Ž. ii1i2i3 NONDIFFERENTIABLE VECTOR DUALITY 465 and ⑀ uq ␣ fx q1y ␣ fx G ␳ fx. Ž. Ž .Ž. Ž. jj1j2j3 Then, taking usuqu)0 we have that fqfis generalized subconij ij vex-like. Generalized subconvex-like functions present a special type of irregularity, which no other generalized convex function presents. If fis generalized subconvex-like and ag⺢p, then the function aqfdoes not have to be a generalized subconvex-like function, as is shown in the following example. Ž.Ž. EXAMPLE 2.1. Let fx,ysx,y, and fbe generalized subconvex-like 2 4 Ž.Ž.Ž . on Ss⺢y0FxF1, 0 FyF1 . But fx,yy1, 1 sxy1, yy1 qŽ. is not a generalized subconvex-like function on Sbecause for x,ys 11 1 Ž.Ž .Ž. 1, 0 , x,ys0, 1 , and ␣ sthere would have to exist a u)0 and a 22 2 ␳ )0 such that ᭙ ⑀ )0, 11 ⑀ u,uqy ,yG ␳ xy1, yy1 with x,ygS. Ž. Ž .Ž. 12 3 3 33 ž/ 22 But this is impossible. 3. EFFICIENCY CONDITIONS In order to operationalize the concept of solutions for a multiobjective programming problem we should relate them to familiar concepts. The most common strategy is to characterize them in terms of optimal soluwx tions of appropriate scalar optimization problems 3, 10 . Among the many Ž. possible ways of obtaining a scalar problem associated with VOP , the following is known as a scalar weighting problem. VP Min ␭ Tfx Ž. Ž. ␭ s.t. gxO0, Ž. n xgS:⺢,  pp 4 where ␭ gL Ls ␭ g⺢r ␭ G0 and Ý ␭ s1. jjs1j wx Geoffrion 6 established the following fundamental result. Ž. Ž. THEOREM 3.1. Let ␭ )0 ␭ G0be fixed.If x is optimal in VP , then x ␭ Ž.Ž. is properly efficient weakly efficient in VOP . Assuming that fand gare convex functions and that Sis a convex set, Geoffrion also established the converse of the above theorem. This result OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES ´´ ´ 466 is based on Gordan’s alternative theorem. Hence by replacing Gordan’s Ž alternative theorem with the Generalized Alternative Theorem Theorem . 2.1 we obtain the following result. Ž. THEOREM 3.2. Let x be a properly efficient solution in VOP and let p Ž. fyf x be generalized subcon¨ex-like on X.Then there exists ␭ g⺢, Ž. ␭ )0, such that x is optimal in VP . ␭ Proof. If xis properly efficient, then there exists a scalar M)0 such that, for each is1,..., p, the system fx-fx, Ž. Ž. ii fxqMf x -fxqMf x for all j/i Ž. Ž. Ž. Ž. iji j admits no solution in X. By Lemma 2.1 and Lemma 2.2 and the Generalized Alternative Theorem, for each is1,..., pthere exist wig⺢,wiG0, with Ýpwis1, such that js1j ii ii wf x qwfxqMf x Gwf x qwfxqMf x , Ž. Ž. Ž. Ž. Ž. Ž. Ž. Ž. ÝÝ ii j i j ii j i j j /ij/i or equivalently ii fxqMwfxGfxqMwfx,2 Ž. Ž. Ž. Ž. Ž. ÝÝ ijjijj j /ij/i for each is1,..., pand for all xgX. Ž. Summing 2 over iyields, after some rearrangement, pp ii 1qMwfxG1qMwfx, Ž. Ž. ÝÝ ÝÝ jj jj ž/ ž/ j s1i/jjs1i/j for all xgX. i Ž. Ž. Then, taking ␭ s1qMÝw,xis optimal in VP . ji/jj ␭ The next theorem proves an analogous result for weakly efficient solutions. Ž. THEOREM 3.3. Let x be a weakly efficient solution in VOP , and let p Ž. fyf x be generalized subcon¨ex-like on X.Then there exists ␭ g⺢, Ž. ␭ G0, such that x is optimal in VP . ␭ Proof. If xis a weakly efficient solution, then the system fxyfx-0, is1,..., p, Ž. Ž. ii has no solution at xgX. By the Generalized Alternative Theorem, there exists ␭ G0 such that T ␭ fxyfx G0᭙xgX, Ž. Ž. Ž. NONDIFFERENTIABLE VECTOR DUALITY 467 which implies that TT ␭ fxG ␭ fx ᭙xgX. Ž. Ž. Ž. Thus xis the optimal solution for VP . ␭ We remark that no assumption on the convexity of the set Xis made in the above theorems. 4. SADDLE POINTS CONDITIONS For scalar mathematical programming the relationships between the solutions of a constrained scalar programming problem and the points which fulfill certain conditions known as the saddle point optimality wx criteria are well known 8 . In this section we extend these results to multiobjective programming problems. To do this we begin by giving new definitions of saddle points for the vector case. npm Ž. DEFINITION 4.1. x,r,¨g⺢)⺢)⺢is said to be a ¨ector Ž.Ž. Fritz᎐John saddle point for Problem VOP if r,¨G0, and the following inequalities hold ᭙¨P0 and ᭙xgS: TTTTTT rf x q¨gxFrf x q¨gxFrf x q¨gx.3 Ž. Ž. Ž. Ž. Ž. Ž. Ž. npm Ž. DEFINITION 4.2. x,r,¨g⺢)⺢)⺢is said to be a ¨ector Ž.Ž. Kuhn᎐Tucker saddle point for Problem VOP if r,¨G0, r/0, and the following inequalities hold ᭙¨P0 and ᭙xgS: TTTTTT rf x q¨gxFrf x q¨gxFrf x q¨gx.4 Ž. Ž. Ž. Ž. Ž. Ž. Ž. Let us note that Definition 4.1 and Definition 4.2 coincide with the Fritz᎐John and Kuhn᎐Tucker saddle-point definitions if fis a numerical function. The above definitions have several advantages over those already existwx ing in the literature 2, 4, 7, 13, 14, 16 . First, the multiplier for the restrictions is a vector and not a function or a matrix. Second and more important, the vector saddle point conditions are scalar conditions, not vector conditions. Thus, it is not necessary to solve any vector problem in order to find the vector saddle points, which simplifies the task. Ž. Problem VOP is said to satisfy the generalized Slater constraint Ž. qualification if there exists a xgXsuch that gx-0. We use this ˆˆ constraint qualification to prove the following result that relates vector Kuhn᎐Tucker saddle points with vector Fritz᎐John saddle points. OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES ´´ ´ 468 Ž. LEMMA 4.1. If x,r,¨is a ¨ector Fritz᎐John saddle point and the Ž. generalized Slater constraint qualification is satisfied,then x,r,¨is a ¨ector Kuhn᎐Tucker saddle point. Proof. Let us suppose that rs0, then the vector Fritz᎐John saddle point conditions are TTT ¨gxF¨gxF¨gx,5 Ž. Ž. Ž. Ž. Ž. ᭙¨P0 and ᭙xgS. For ¨s0, the inequalities 5 become TT 0F¨gxF¨gx,6 Ž. Ž. Ž. TŽ. ᭙xgS. Therefore, 0 F¨gx for all xgS. Since the generalized Slater constraint qualification is satisfied, there T Ž. Ž. Ž. exists a xgSsuch that gx-0. Then for this x,¨gx-0. But, by 6 , ˆˆ ˆˆ TŽ. ¨gxG0, and this is a contradiction. ˆ The following result proves that vector Kuhn᎐Tucker saddle points are Ž. weakly efficient points for VOP without requiring additional conditions, as in the scalar case. Ž. THEOREM 4.1. If x,r,¨is a ¨ector Kuhn᎐Tucker saddle point,then x is Ž. weakly efficient for VOP . Ž. Ž . Proof. If r/0, by 4 , x,rsolves a Kuhn᎐Tucker saddle point Ž. problem for the scalar programming problem VP , and thus xis optimal r Ž. for VP . As rG0, from Theorem 3.1, xis a weakly efficient point for r Ž. VOP . Under a certain convexity condition the following result shows the reverse of the above theorem. ŽŽ.. THEOREM 4.2. Let f yfx,g be a generalized subcon¨ex-like function Ž. on S,and let x be a weakly efficient solution to VOP . Then there exists Ž. Ž . Ž . r,¨G0such that x,r,¨is a ¨ector Fritz᎐John saddle point for VOP . Ž. Proof. If xis a weakly efficient solution for VOP then the system fxyfx-0 Ž. Ž. gxO0 Ž. has no solution in S, therefore the system fxyfx-0 Ž. Ž. gx-0 Ž. has no solution in S. NONDIFFERENTIABLE VECTOR DUALITY 469 pqm Ž. Ž. By Theorem 2.1, there exist r,¨g⺢with r,¨G0 such that TTT rf x q¨gxGrf x ᭙xgS.7 Ž. Ž. Ž. Ž. In particular, we have that T ¨gxG0. 8 Ž. Ž. Because xis feasible we also have T ¨gxF0. 9 Ž. Ž. T Ž. Ž. Ž . Ž. By 8 and 9 we have that ¨gxs0. Hence, by 7 TTTTTTT rf x q¨gxGrf x q¨gxsrf x Grf x q¨gx Ž. Ž. Ž. Ž. Ž. Ž. Ž. ᭙xgSand ᭙¨P0, and thus xis a vector Fritz᎐John saddle point. From Lemma 4.1 and Theorem 4.2 we have the following. ŽŽ.. THEOREM 4.3. Let f yfx,g be a generalized subcon¨ex-like function Ž. and let x be a weakly efficient solution.Suppose that the Problem VOP Ž. satisfies the generalized Slater constraint qualification.Then there exists r,¨ Ž. Ž. G0such that x,r,¨is a ¨ector Kuhn᎐Tucker saddle point for VOP . From Theorem 3.1 it is easy to show the following result for properly efficient solutions. Ž. THEOREM 4.4. Let x,r,¨be a ¨ector Kuhn᎐Tucker saddle point with Ž. r)0, then x is a properly efficient solution for VOP . As before, under generalized convexity conditions, we prove the reverse. THEOREM 4.5. Suppose that x is a properly efficient solution of Problem Ž.Ž Ž.. VOP . If f yfx,g is generalized subcon¨ex-like on S and the generalized Slater qualification constraint is satisfied,then there exist r )0and ¨P0 Ž. Ž. such that x,r,¨is a ¨ector Kuhn᎐Tucker saddle point for VOP . Ž. Proof. If xis a properly efficient solution for VOP , the system fxyfx-0 Ž. Ž. ii fxqMf x yfxyMf x -0 for all j/i Ž. Ž. Ž. Ž. ijij gx-0 Ž. admits no solution in Sfor each is1,..., p. Thus there exist rig⺢p im Žii .pi and ¨g⺢, with r,¨G0, and Ýrs1, for each is1,..., p, such js1j that ii i fxqMrfxq¨gxGfxqMrfx ᭙xgS.10 Ž. Ž. Ž. Ž. Ž. Ž . ÝÝ ijj ijj j /ij/i OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES ´´ ´ 470 i Ž. Ž. From 10 , xsx«¨gxG0 for all is1,..., p. On the other hand, iŽ. ¨gxF0 for all is1,..., p. Therefore i ¨gxs0. 11 Ž. Ž . Ž. Ž. Summing over iyields 10 , and by 11 we get pp ii 1qMrfxq¨gx Ž. Ž. ÝÝ Ý jj ž/ j s1i/jis1 pp ii G1qMrfxq¨gx. Ž. Ž. ÝÝ Ý jj ž/ ž/ j s1i/jis1 i Assuming that rs1qMÝr)0 for each js1,..., pand ¨s ji/jj Ýp¨i, we have is1 TTTT rf x q¨gxGrf x q¨gx Ž. Ž. Ž. Ž. TT T srf x Grf x q¨gx, Ž. Ž. Ž. n for all xgSand for all ¨g⺢with ¨P0. 5. LAGRANGE DUALITY FOR A MULTIOBJECTIVE PROBLEM We define the vector-valued Lagrange function with respect to Problem Ž. VOP as Lx, ␭ sfxq ␭ Tgxe,x, ␭ gS=L L, Ž.Ž. Ž. Ž. Ž. p  mT 4 where es1,...,1 g⺢and L Ls ␭ g⺢r ␭ G0, ␭ es1. i Ž. Let us denote by W W ␭ the set of weakly efficient solutions for the following vectorial programming problem: Min Lx, ␭ Ž. s.t. xgS. Ž.  Ž. TŽ. Ž. 4 Let ⍀ ␭ sfxq ␭ gxewith xgW W ␭ . Ž. For VOP , the corresponding Lagrange dual problem is the following: DVP Max ⍀ ␭ Ž. Ž. s.t. ␭ gL L. Ž.Ž. Now we prove the classical duality theorems between VOP and DVP .