# Pre-invex functions in multiple objective optimization, T Weir, B Mond

Tags: J. Austral, PV, constraint qualification, MOND Department of Mathematics, Australia, Optimality Conditions, programming, JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, WEIR Department of Mathematics, Australian Defence Force Academy, Australia Submitled, Objective Optimization, Bundoora VIC, Lu Trohe, Duality theory, V. Lakshmikantham, J. Optim, J. Math, A. M. GEOFFRION, convexity, Geoffrion, Xc S. Geoffrion, nonlinear programming, M. A. HANSON, B. D. CRAVEN, optimization problem, B. M. GLOVER, K. H. ELSTER, Appl
Content: JOURNAL OF MATHEMATICAL
ANALYSIS AND APPLICATIONS 136, 29-38 (1988)
Pre-invex Functions in Multiple objective Optimization T. WEIR Department of Mathematics, Australian Defence Force Academy, Campbell ACT 2600 Australia AND B. MOND Department of Mathematics, Lu Trohe Unioersit.v, Bundoora VIC 3083, Australia Submitled by V. Lakshmikantham ReceivedNovember15.1986
1. INTRODUCTION
Elster and Nehse [4] considered a class of functions f: S -+ R", S c IR", for which, if x, y E S and 0 f(z) 5 if(x) + (1 - i.)f(4')
(1.1)
and called such functions convexlike. If S is a convex set and if f is a convex function, then clearly f is convexlike. Elster and Nehse obtained a saddlepoint optimality condition for convexlike mathematical programs. Hayashi and Komiya [9] also considered convexlike functions and developed a Gordan-type theorem of the alternative involving convexlike functions and in addition considered Lagrangian duality for convexlike programs. Hanson [7] considered differentiable functions f: S + R for which there exists an n-dimensional vector function q(,q U) such that for all x, u E S
f(-~)-f(u) 3 [9(x, u)l' L7f'(u).
(1.2)
Such functions were termed invex by Craven [2]. Clearly differentiable convex functions are invex. Hanson [7] showed that if, instead of the usual convexity conditions, the objective function and each of the constraints of a nonLinear Programming problem all satisfy (1.2) for the same q(x, u), weak 29 0022-247X/88 \$3.00 Copyright t 19x8 by Academx Press. lot All rights or reproductmn I" an) form reserved
30
WEIR AND MOND
duality and the sufficiency of the Kuhn-Tucker conditions still hold. Furthermore Craven and Glover [3] (see also Ben Israel and Mond [l] and Martin [ 111) showed that the class of invex functions is equivalent to the class of functions whose stationary points are global minima. More generally, Ben Israel and Mond [ 1] and Hanson and Mond [S] considered (not necessarily differentable) functions defined on S having the property that there exists an n-dimensional vector function ~(x, U) such that, for all x, u E S and 0 < 2 < 1,
f(u + E.q(x,u)) < if(x) + (1 - E.)f(u)
(1.3)
and observed that differentiable functions satisfying (1.3) also satisfy (1.2). In view of this observation, functions satisfying (1.3) will be called pre-invex.' An m-dimensional vector valued function f: S -+ R" is pre-invex on S (with respect to q) if each of its components is pre-invex on S (with respect to q). It is implicit in the definition of (1.3) that, for all x, u ES and 0 < 1 d 1, u + \$(x, U)ES; hence pre-invex functions are convexlike. However, pre-invex functions have some interesting properties that are not generally shared by the wider class of convexlike functions. For example, as for convex functions, every local minimum of a pre-invex function is a global minimum and nonnegative linear combinations of pre-invex functions are pre-invex [ 141. As a simple example of a function which is not convex but is pre-invex, consider f(x)= - 1x1.
Then f is pre-invex with v] given by
if ~60 if ~30 if y>O if yand x 0.
Our purpose in this paper is to detail how and where pre-invex functions can replace convex functions in multiple objective optimization.
2. PRELIMINARIES The following convention for equalities and inequalities will be used. If x, y E R", then ' The authors are grateful to V. Jeyakumar for his coinage of the term "pre-invex."
PRE-INVEX FUNCTIONS
31
x=v
iff x,=y,, i= 1, 2, .... n
x 5 y iff x, < yi, i = 1, 2, ..,, n
xdy
iff xsy,
and x#y
Xx Z\$y is the negation of x d y.
A scalar valued optimization problem may be expressedas (P) minimize f(x) subject to g(x) 5 0. Heref: S-+ R and g: S+ II%",where SC W. As previously mentioned, Hayashi and Komiya [9] extended Gordan's alternative theorem (see [lo]) from convex to convexlike functions (their results are for a more general problem than (P), but may be easily specialized), and they also prove saddlepoint and Lagrangian Duality Theorems. For completeness we state and prove an extension to Gordan's alternative theorem involving pre-invex functions and then state the corresponding saddlepoint and duality theorems which follow in the same manner as in the case for convex functions (see, e.g., Geoffrion [5] and Mangasarian [lo]). The saddlepoint and duality theorems will be shown to be special casesof Theorems 4.1, 4.2, and 4.3.
THEOREM 2.1. Let S he a nonempty set in R" and let f: S + R" he a pre-invex function on S (with respect to 9). Then either
f(x) < 0 has a solution x E S or P'fb) 2 0 for all x E S, for some p E l%", p >, 0,
hut both alternatives are never true.
Proof. Following [lo], the proof depends on establishing the convexity of the set n=U {~(x):xoS}, where
A(x)= {uERm:U>f(X)},
XE s.
Under our assumptions this is immediate for if u, and u2 are in /i, then for O~~(x,)+(l-~)f(xz)
2f (x2 + Mx, >x2)). I The program (P) will be said to satisfy the generalized Slater constraint qualification if g is pre-invex (with respectto q) and there exists x, ES such that g(x,) < 0.
32
WEIRANDMOND
THEOREM 2.2. For the problem (P), assume that f is pre-invex (with respect to n) and g is pre-invex (with respect to n), and that the generalized Slater constraint qualtfication holds. If (P) attains a minimum at x=x0 E S then there exists v0 E R", v0 2 0, such that (x,, vO) is a solution of the saddlePoint problem (all x E S, v E KY"`,v 2 0),
dXO> 0) 5 dx,, d 2 d-c VII),
(2.1)
w,here qo(x, v) is the Lagrangian f(x) + v'g(x). Moreover, (f the condition
(2.1) is satisfied for some x0 and vO, then x0 is a minimum for (P).
In relation to (P), consider the problem
(D) maximize q(v) subject to v E RF, v 2 0,
where q(v) = inf,,,Y {f(x) + v'g(x)}.
THEOREM 2.3. In problem (P), assume that f is pre-invex (with respect to n) and g is pre-invex (with respect to n), and that the generalized Slater constraint qualtfication holds. Then (D) is a dual to (P). Many results for the convex scalar optimization problem have been extended to the multiple objective optimization problem, which may be expressed as (PV) minimize f(x) subject to XEX, where f: S -+ Rk, S c KY', XC UP. This is the problem of finding the set of efficient or Pareto [ 121 optimal points for (PV): x,, is said to be efficient if it is feasible for (PV) and there exists no other feasible point x such that f(x) f;(x,) whenever x is feasible for (PV) and fi(x) C Programming problem. In the following sections we will show that Geoffrion's assumptions of convexity may be replaced
PRE-INVEX FUNCTIONS
33
by pre-invexity. We shall also consider the relevant questions of vector saddlepoints and duality.
3. PROPER EFFICIENCY AND PRE-INVEXITY In relation to (PV) consider the following scalar minimization problem: (PVL) minimize Ly(x) subject to x EX, where E.EA+ = {E.ER%>o,~;= , 3.,= 1). For convenience we assume that Xc S. Geoffrion [6] established the following fundamental result: THEOREM 3.1. Let 1.,> 0 (i = 1, 2, .... k) be fixed. If x0 is optimal in (PVL), then x0 is properly efficient in (PV). Assuming f convex and X convex, Geoffrion also established the converse of Theorem 3.1. This result is based on Gordan's alternative theorem (see [lo]). Hence replacing Gordan's alternative theorem with our Theorem 2.1 gives: THEOEM 3.2. Let f be pre-invex on X (with respect to q). Then x0 is properly efficient in (PV) if and only if x0 is optimal in (PVL). Additionally, in his "Comprehensive Theorem," Geoffrion established a more complete characterization of proper efficient points for the problem (PV). It is not difficult to see that his assumptions of convexity may be replaced by pre-invexity. Here we restate the problems and Geoffrion's "Comprehensive Theorem," replacing any assumption of convexity with pre-invexity. PROBLEM 1. Find a point x0 that is a properly efficient solution of (PV). PROBLEM 2. Find a point x,, that is a locally properly efficient solution of (PV). In Problems 3-5, X is taken to be of the form X= {x: g(x) 5 O}. PROBLEM 3. Find a feasible point x0 such that none of the k systems (i= 1, 2, .... k) 24'v fi(XO) < 0 U' Ofj(X,)dO all j# i uf v gj(XlJ) d O all j such that g,(x,) = 0 has a solution u E R".
34
WEIRANDMOND
PROBLEM 4. Find a feasible point x0, a point y, E R", y, 2 0, and a point i0 E n + such that J\$,g(x,) = 0 and V [Itihf(xO) +yk g(x,] = 0.
PROBLEM 5. Find a feasible point x,,, a point yOe R", yOz 0, and a point & E /1+ such that y; g(x,) = 0 and x0 achieves the unconstrained minimum of E.&f(x) + y;g( x).
PROBLEM 6. Find a point x0 and a point &,E il+ such that x0 is optimal in (PV&). The following assumptions will be made: Assulnption P. All functions are pre-invex (with respect to q) on X. Assumption D. All functions are continuously differentiable on X. Assumption Q, . The generalized Slater constraint qualification holds. Assumption Q2. The Kuhn-Tucker constraint qualification holds [9].
THEOREM 3.3.
5-4-3 D The proof of Theorem 3.3 follows in exactly the same manner as that of the "Comprehensive Theorem" in [6], replacing convexity with pre-invexity. 4. VECTOR SADDLEPOINTS AND DUALITY Here we consider the vector valued optimization problem (PV)' minimize f(x) subject to g(x) s 0, where f: S + Rk, g: S -+ W", and the related vector saddlepoint and dual problems. By studying a natural generalization of the scalar Lagrangian S(x) + did-~) e (e=(l, l,..., I)`ERk) Tanino and Sawaragi t13] have developed a saddlepoint and duality theory for convex (PV)`, generalizing that of the scalar case. Here we take a slightly different approach (see also [15]) but the results shown have their analogs in [ 133.
PRE-INVEX FUNCTIONS
35
The vector saddlepoint problem is the problem of finding x0 ES, y, E R", y,zO, such that
f(.d + y'dxd e 2 f(xd + yb g&J e
(4.1)
f&J + yh dxd e 2 f(x) + YLg(x) e
(4.2)
for all x E S, y E R", y 2 0. The conditions (4.1) and (4.2) are always sufficient for x,, to be properly efficient for (PV)' (see [ 151). On the other hand, if x0 is a properly efficient solution of (PV)`, one requires a constraint qualification and convexity to assure the existence of y0 such that (x,, yO) is a solution of (4.1) and (4.2). We now show that this convexity requirement can be weakened to preinvexity.
THEOREM 4.1. Let x0 he a properly efficient solution for (PV)`; if the generalized Slater constraint qualification is satisfied, and if f and g are pre-invex (with respect to q), then there exists y,>=O such that (x,, y,) is a solution of the saddlepoint problem. Proof. Since x0 is a properly efficient solution for (PV)' then by Theorem 3.2, x0 minimizes Abf (x) subject to g(x) 5 0 for some lb0E/1+. Since &f is pre-invex (with respect to 4) and since the generalized Slater condition is satisfied, by Theorem 3.3, there exists y, E III", y, 10, such that y; g(x,) = 0 and
dx,, Y) 6 dx,, Yo) G dx, VCA
(4.3)
where cp(x,y) = A&[f (x) + y'g(x) e]. Consequently, if (4.1) was not true then for some i E { 1, 2, .... k I,
f;(xo) + Y'dXd >fi(%) + Y:, g(x0) and frcG3)+ Y'&cd w&J + Ybg(xd for all j # i; multiplication by &, i = 1, 2, .... k, and summing over all values of i would then contradict (4.3). A similar argument applied to (4.2) would also result in a contradiction. 1 We now turn our attention to duality and consider the problem of (see 1151) PI maximize Z = (v E Rk: (U E /i+, y ZO), 1'~ = infx(llf(x) + Ykb)l>. (D) is the problem of finding all the extreme points of E (see, e.g., C131).
36
WEIRANDMOND
THEOREM 4.2. (Weak Duality). Let x be feasible for (PV)' and let v E E. Then f (x) - v < 0.
Proof For some jti E A +, y 2 0, 3.`v = inf, (E.`f(x) +y'g(x)}. Since
g(x) 5 0, 2'f (x) 3 A'f (x) + y'g(x) 2 inf, {ILfg(x) + y'g(x)} = 2'~. So
i.`(f(x)-v)>O
and thusf(x)-v & 0. 1
THEOREM 4.3 (Strong Duality). Let x0 be a properly efficient solution of (PV)' and let the generalized Slater constraint qualifi:cation be satisfied. Then there is an extreme point co E E such that f (x,,) = co. Proqf: Since x,, is a properly efficient solution for (PV)' then x0 solves the pre-invex problem
minimize j-if(x) subject to g(x) 5 0
for some AELI+, by Theorem 3.1. Since the generalized Slater condition is satisfied, from Theorem 3.3, there exists y, 2 0 such that yt, g(xa) = 0 and for all x j-lf`(-d + y; g(x,) d IY(x) + yI, g(x).
Thus aIf < inf, (iif + yh g(x)} = i.`v for some v E [Wk. From weak duality L'f(x,) = ;l'v. If there was no extreme point &,E 5 such that f(x,)= co then there would be [EZ such that [--f(x,) ~0, [-f(x,) ~0. Hence for all 1~/1+, J.`f> l.`f(x,). Since [EZ there exist RE /1+ and .\$E R", 9 2 0, such that
inf {Ilf(x) +p'g(x)} = 1:`[> E:lf(x,) 3 ;`f(xO) +j'g(x,),
which is a contradiction. 1 As indicated earlier, Theorems 2.2 and 2.3 are special cases of Theorems 4.1, 4.2, and 4.3. Finally, we direct our attention to problem (PV)' with differentiable functions. In relation to (PV)' consider the problem
(D)' maximizef (u) + y'g(u) e
subject to L7 E"ff(u) + v y'g(u) = 0
(4.4)
~20, ikeA+.
(4.5)
(D)' is the problem of finding the properly efficient points of f +y'ge subject to the given constraints. (D)' was first given in [16] and shown to be dual for (PV)' under convex hypotheses. We now show that these hypotheses may be weakened to pre-invexity.
PRE-INVEX FUNCTIONS
37
THEOREM 4.4 (Weak Duality). Let x be feasible for (PV)' and (u, A, y) feasible for (D)`. lff and g are pre-invex (with respect to yl) for all feasible (x, u, A, y) then
Proof.
f(x) & f(u) + y'g(u) e.
jJ{f(x)-(f(u)+y'g(u)e)l
=j.`(f(x)-f(u))-y'g(u)
2 ;rl(x, u)' L7 Alf(u) - Y'dU)
3 f/(x, u)' { OiY(u) + VY'dU)) -Y'dX)
= -Yk(X)
30
(from (4.5)) (by pre-invexity off) (by pre-invexity of g) (by (4.4) since g(x) 5 0, y 2 0.
Thusf(x) 1
THEOREM 4.5 (Strong Duality). Let f and g be pre-invex (with respect to q) for all feasible (x, u, i, y) and let x,, be a properly efficient solution for (PV)' at which a constraint qualification is satisfied. Then there exist (A, y) such that (x,, A, y) is a properly efficient solution of (PV)' and the objective values of (PV)' and (D)' are equal. Proof: Since f and g are pre-invex and x0 is a properly efficient solution of (PV)' then, by Theorem 2.2, x0 is optimal in (PVA)' for some 1 E A +. Since also a constraint qualification is satisfied at x0, then by Wolfe's duality theorem [ 173, there is y 2 0 such that (x,, A, y) is optimal in the problem (Di)' maximize A'f (u) + y'g( u) subject to Oi.`f(u)+ Vy'g(u)=O J'zO,iEA+, and y'g( x0) = 0. Since (x,, A, y) is optimal for (DL)`, (x,, I., y) is properly efficient for (D)`, from Theorem 2.1. The optimal values of (PV)' and (D)' are equal since y'g(x,) = 0. 1 REFERENCES 1. A. BEN-ISRAEL AND B. MOND, What is invexity? J. Austral. Math. Sot. Ser. E 28 (1986), 1-9. 2. B. D. CRAVEN, Invex functions and constrained local minima, Bull. Auswal. Mafh. Sot. 24 (1981), 357-366.
38
WEIR AND MOND
3. B. D. CRAVEN AND B. M. GLOVER, Invex functions and duality, J. Austral. Math. Sot. Ser. A 39 (1985), l-20. 4. K. H. ELSTER AND R. NEHSE, "Optimality Conditions for Some Nonconvex Problems," Springer-Verlag, New York, 1980. 5. A. M. GEOFFRION, Duality in nonlinear programming: A simplified applications-oriented development, SIAM Rev. 13 (1971), 1-38. 6. A. M. GEOFFRION, Proper efficiency and the theory of vector maximization, J. Math. Anal. Appl. 22 (1968), 618-630. 7. M. A. HANSON, On sufficiency of the Kuhn-Tucker conditions, J. Math. Anal. Appl. 80 (1982), 545-550. 8. M. A. HANSON AND B. MOND, "Convex Transformable Programming Problems and Invexity," J. Inf Opt. Sci. 8 (1987), 201-207. 9. M. HAYASHI AND H. KOMIYA, Perfect duality for convexlike programs, J. Optim. Theory Appl. 38 (1980), 179-189. 10. 0. L. MANGASARIAN, "Nonlinear Programming," McGraw-Hill, New York, 1969. 1h D. H. MARTIN, The essence of invexity, J. Optim. Theory Appl. 47 (1985), 65-76. 12. V. PARETO, Cours d'economie Politique, Rouge, Lausanne, 1896. 13. T. TANINO AND Y. SAWARAGI, Duality theory in multiobjective programming, J. Optim. Theory Appl. 27 (1979), 509-529. 14. T. WEIR, "A Note on Invex Functions and Duality in Generalized Fractional Program- ming," Report No. 4, Department of Mathematics, Australian Defence Force Academy, 1986. 15. T. WEIR, B. MOND, AND B. D. CRAVEN, Weak minimization and duality, Numer. Funcr. Anal. Optim. 9 (1987), 181-192. 16. T. WEIR, Proper efficiency and duality for vector valued optimization problems, J. Austral. Math. Sot. Ser. A 43 (1987), 21-34. 17. P. WOLFE, A duality theorem for nonlinea; programming, Quart. Appl. Math. 19 (1961), 239-244.

T Weir, B Mond

### File:pre-invex-functions-in-multiple-objective-optimization.pdfTitle: PII: 0022-247X(88)90113-8Author: T Weir, B MondPublished: Fri Nov 28 14:36:25 2003Pages: 10File size: 0.44 Mb

Hot Stuff, 68 pages, 0.81 Mb

Singing in the Echo Chamber, 64 pages, 0.62 Mb

, pages, 0 Mb