On second order necessary optimality conditions for vector optimization problems

ON SECOND ORDER NECESSARY OPTIMALITY CONDITIONS FOR VECTOR OPTIMIZATION PROBLEMS

Gue Myung Lee and Moon Hee Kim

Abstract. Second order necessary optimality condition for prop- erly efficient solutions of a twice differentiable vector optimization problem is given. We obtain a nonsmooth version of the second order necessary optimality condition for properly efficient solutions of a nondifferentiable vector optimization problem. Furthermore, we prove a second order necessary optimality condition for weakly efficient solutions of a nondifferentiable vector optimization prob- lem.

1. Introduction and preliminaries

Vector optimization problems are those where two or more objectives are to be minimized on some set of feasible solutions. In such problems we deal with conflicts amongst objectives. Thus such problems have important applications in economics, game theory and statistical deci- sion theory (see [1]-[5]). The objective functions in the problems may be differentiable (smooth) or nondifferentiable (nonsmooth). In most cases we can not find a feasible solution which is optimal in the sense that it minimizes all the objectives simultaneously. So, in vector optimization we should use concepts of solutions different from the just mentioned requirement of optimality. For vector optimization problems, there are three kinds of solutions, that is, properly efficient solution, efficient so- lution and weakly efficient solution (see [5, 6]).

Received July 10, 2002. Revised October 9, 2002.

2000 Mathematics Subject Classification: Primary 90C29; Secondary 90C46.

Key words and phrases: vector optimization problem, properly efficient solutions, second order necessary optimality conditions, second order contingent set, second or- der adjacent set, singular approximate subdifferential, (Mordukhovich) normal cone.

This work was supported by Korea Research Foundation Grant (KRF 2001-015-

DP0049).

The concept of vector variational inequality was introduced by Gian- nessi [7] in 1980. Also, he [8] gave first order necessary optimality con- ditions, which are described by vector variational inequality, for efficient solutions or weakly efficient solutions of a differentiable convex vector optimization problem. Some authors have tried to improve Giannessi’s idea on necessary optimality conditions (for example, see [9]-[12]).

Recently, nonsmooth analysis for treating nondifferentiable scalar op- timization problems and nondifferentiable vector optimization problems has been greatly developed. Using generalized directional derivatives, generalized subgradients, derivatives for multifunctions, normal cones and tangent cones appeared in nonsmooth analysis, many authors have improved necessary optimality conditions for optimization problems (see [11]-[23] and therein references). In particular, using tangent cones and generalized directional derivatives, Ward and Lee [11, 12] obtained first order necessary optimality conditions for properly efficient solutions or weakly efficient solutions of nondifferentiable vector optimization prob- lems.

The purpose of this paper is that following proofs of first order neces- sary optimality theorems of Ward and Lee [11, 12] for nondifferentiable vector optimization problems, we obtain second order necessary opti- mality conditions for the problems. We give a second order necessary optimality condition for properly efficient solutions of a twice differen- tiable vector optimization problem, and then obtain a nonsmooth version of the second order necessary optimality condition for properly efficient solutions of a nondifferentiable vector optimization problem. Further- more, we prove a second order necessary optimality condition for weakly efficient solutions of a nondifferentiable vector optimization. Our main results can be regarded as second order versions of recent ones in Ward and Lee [11, 12].

Let S be a nonempty subset of R ⁿ and f i : R ⁿ → R, i = 1, . . . , p, functions.

Consider the following vector optimization problem (VP):

Minimize f (x) := (f 1 (x), . . . , f p (x)) (VP)

subject to x ∈ S.

Solving (VP) means finding the efficient solutions which are defined as follows:

Definition 1.1. (1) y ∈ S is said to be an efficient solution of (VP)

if for any x ∈ S, (f 1 (x) − f 1 (y), . . . , f p (x) − f p (y)) 6∈ −R ^p ₊ \ {0}, where

R ^p ₊ is the nonnegative orthant of R ^p .

(2) y ∈ S is called a properly efficient solution of (VP) if y ∈ S is efficient for (VP) and if there exists M > 0 such that for each i = 1, . . . , p, we have

f _i (y) − f _i (x) f _j (x) − f _j (y) ≦ M

for some j such that f _j (x) > f _j (y) whenever x ∈ S and f _i (x) < f _i (y).

(3) y ∈ S is said to be a weakly efficient solution of (VP) if for any x ∈ S, (f 1 (x) − f 1 (y), . . . , f p (x) − f p (y)) 6∈ − intR ^p ₊ , where intR ^p ₊ is the interior of R ^p ₊ .

The quantity _f ^f

^(y)−f

^(x)

j

(x)−f

(y) may be interpreted as the marginal trade-off for the objective functions f i and f j between y and x. Geoffrion [24]

defined the concept of the proper efficiency to eliminate the unbounded trade-off between the objective functions of (VP).

Now we introduce the normal cone and the singular approximate subdifferential studied by Mordukhovich [17].

Definition 1.2. (1) Let S be a nonempty subset of R ⁿ and x ∈ R ⁿ . Define

P (S, x) := {w ∈ clS | k x − w k= inf

z∈S k x − z k}.

Let ¯ x ∈ clS, where clS is the closure of the set S. The normal cone to S at ¯ x is defined by

N (S, ¯ x) := {y ∈ R ⁿ | ∃{y n } → y, {x n } → ¯ x, {t n } ⊂ (0, +∞), {c n } ⊂ R ⁿ with c n ∈ P (S, x n ) and y n = t n (x n − c n )}.

(2) Let f : R ⁿ → R be a function and x ∈ R ⁿ . The singular approximate subdifferential of f at x is defined by

∂ ^∞ f (x) := {x ^∗ ∈ R ⁿ | (x ^∗ , 0) ∈ N (epif, (x, f (x)))}, where epif := {(x, r) ∈ R ⁿ × R | f (x) ≦ r}.

If S is a convex set, then N (S, x) is the usual normal cone.

Remark 1.1 ([17, Proposition 2.3]). A lower semicontinuous function

f is Lipschitz near x if and only if ∂ ^∞ f (x) = {0} .

Definition 1.3. (1) Let S be a nonempty closed subset of R ⁿ and x ∈ S. The adjacent cone to S at x is defined by

T (S, x) := {v ∈ R ⁿ | ∀δ > 0, ∃λ > 0 s.t. ∀t ∈ (0, λ), ∃y ∈ B(v, δ) with x + ty ∈ S}

:= {v ∈ R ⁿ | ∀{t n } ↓ 0, ∃{v n } → v with x + t n v _n ∈ S}, where B(v, δ) = {y ∈ R ⁿ | ky − vk < δ}.

The contingent cone to the set S at x is the set

K(S, x) := {v ∈ R ⁿ | ∀δ > 0, ∃t ∈ (0, δ), y ∈ B(v, δ) with x + ty ∈ S}

:= {v ∈ R ⁿ | ∃{t n } → 0 ⁺ , {v _n } → v with x + t n v _n ∈ S}.

(2) Let f : R ⁿ → R := [−∞, +∞] be finite at x ∈ R ⁿ . For the adjacent cone T , we define the T directional derivative of f at x in the direction y ∈ R ⁿ by

f ^T (x; y) := inf{r ∈ R | (y, r) ∈ T (epif, (x, f (x)))}.

We can prove an expression of f ^T (x; y); for any y ∈ R ⁿ , f ^T (x; y) := lim sup

t→0

v→y inf

f (x + tv) − f (x) t

:= sup

ǫ>0

δ>0 inf sup

t∈(0,δ)

v∈B(y,ǫ) inf

f (x + tv) − f (x)

t ,

where B(y, ǫ) := {z ∈ R ⁿ | k z − y k< ǫ}.

Also, we can check that if f is differentiable at x ∈ R ⁿ , then f ^T (x; y) = ­∇f(x), y®

for any y ∈ R ⁿ , where ∇f (x) is the gradient of f at x and ­·, ·® denotes the inner product on R ⁿ . Also, if f is Lipschitz near x, f ^T (x; y) = f ⁺ (x; y) (see, [22]), where

f ⁺ (x; y) = lim sup

t→0

f (x + ty) − f (x)

t .

Now we give second order tangent sets, which are found in [20, 21];

Definition 1.4. Let S be a nonempty closed subset of R ⁿ , and let x ∈ S and v ∈ R ⁿ .

(a) The second order contingent set is defined by K ² (S, x, v)

:= {y ∈ R ⁿ | ∀δ > 0, ∃t ∈ (0, δ), w ∈ B(y, δ) with x + tv + 1

2 t ² w ∈ S}

:= {y ∈ R ⁿ | ∃{t n } → 0 ⁺ , {y n } → y with x + t n v + 1

2 t ² _n y n ∈ S}.

(b) The second order adjacent set is defined by T ² (S, x, v)

:= {y ∈ R ⁿ | ∀δ > 0, ∃λ > 0 s.t. ∀t ∈ (0, λ), ∃w ∈ B(y, δ) with x + tv + 1

2 t ² w ∈ S}

:= {y ∈ R ⁿ | ∀{t n } → 0 ⁺ , ∃{y _n } → y with x + t n v + 1

2 t ² _n y _n ∈ S}.

K ² (S, x, v) and T ² (S, x, v) are (possibly empty) closed sets, but not necessarily cones. T ² (S, x, v) ⊂ K ² (S, x, v), but the converse inclusion may not be true.

Remark 1.2. Let S ⊂ R ⁿ and x ∈ S. Then K ² (S, x, 0) = K(S, x) and T ² (S, x, 0) = T (S, x).

Now we will define second order directional derivative with the second order adjacent set.

Definition 1.5. Let f : R ⁿ → R be finite at x, and suppose that f ^T (x; v) is finite. The T ² directional derivative of f at x with respect to v ∈ R ⁿ , y ∈ R ⁿ is defined by

d ² f ^T (x; v, y) := inf {r ∈ R | (y, r) ∈ T ² (epif, (x, f (x)), (v, f ^T (x; v)))}.

The following proposition can be found in [21]:

Proposition 1.1. Let f : R ⁿ → R be finite at x ∈ R ⁿ . If f ^T (x; v) is finite, then for all y ∈ R ⁿ ,

d ² f ^T (x; v, y) := lim sup

t→0

inf

w→y 2(f (x + tv + t ² w/2) − f (x) − tf ^T (x; v))/t ² := sup

ǫ>0

inf

λ>0

sup

t∈(0,λ)

inf

w∈B(y,ǫ)

2(f (x + tv + t ² w/2) − f (x) − tf ^T (x; v))/t ² .

Remark 1.3. Let f : R ⁿ → R be twice differentiable at x ∈ R ⁿ . Then for all y ∈ R ⁿ ,

d ² f ^T (x; v, y) = ­∇f(x), y® + ­v, ∇ ² f (x)v®.

Remark 1.4 ([20]). Suppose f : R ⁿ → R is finite at x ∈ R ⁿ and f ^T (x; y) is finite. Then we have

(1) if v = 0, then d ² f ^T (x; v, y) = f ^T (x; y),

(2) epi d ² f ^T (x; v, ·) = T ² (epi f, (x, f (x)), (v, f ^T (x; v))).

Remark 1.5 ([23]). If f is Lipschitz near x, then d ² f ^T (x; v, y) = d ² f ⁺ (x; v, y), where

d ² f ⁺ (x; v, y) := lim sup

t→0

2(f (x + tv + t ² y/2) − f (x) − tf ⁺ (x; v))

t ² .

2. Second order necessary optimality conditions

Now we will give a second order necessary optimality conditions for properly efficient solutions of the vector optimization problem (VP) in- troduced in Section 1.

Theorem 2.1. Suppose that f _i , i = 1, . . . , p, are twice differentiable.

Let x ∈ S be a properly efficient solution of (VP). If ¯ ­∇f k (¯ x), v ®

= 0, k = 1, . . . , p and v ∈ K(S, ¯ x), then for each i ∈ {1, . . . , p},

{y|­∇f i (¯ x), y® + ­v, ∇ ² f _i (¯ x)v® < 0}

∩ {y | ­∇f j (¯ x), y® + ­v, ∇ ² f j (¯ x)v® ≦ 0, j 6= i}

∩ K ² (S, ¯ x, v) = ∅,

equivalently,

{y | ¡­∇f 1 (¯ x), y® + ­v, ∇ ² f 1 (¯ x)v®, . . . , ­∇f p (¯ x), y® + ­v, ∇ ² f p (¯ x)v ®¢

∈ − R ^p ₊ \ {0}} ∩ K ² (S, ¯ x, v) = ∅.

Proof. Following the approach used in the proof of Theorem 3.16 in [6], we will prove this theorem. Let ¯ x ∈ S be a properly efficient solution of (VP). Let v ∈ K(S, ¯ x) be such that ­∇f k (¯ x), v® = 0, k = 1, . . . , p. Suppose to the contrary that there exist i ∈ {1, . . . , p} and y ∈ K ² (S, ¯ x, v) such that ­∇f i (¯ x), y® + ­v, ∇ ² f i (¯ x)v® < 0 and ­∇f j (¯ x), y® +

­v, ∇ ² f j (¯ x)v® ≦ 0, j 6= i. Since y ∈ K ² (S, ¯ x, v), there exist sequences {t n } → 0 ⁺ , {y _n } → y such that ¯ x + t _n v + ¹ ₂ t _n ² y _n ∈ S. By the twice differentiability of f i at ¯ x, we have

f i (¯ x + t n v + 1

2 t n 2 y n ) − f i (¯ x)

= ­∇f i (¯ x), t _n v + 1

2 t _n ² y _n ® + 1

2 ­t n v + 1

2 t _n ² y _n , ∇ ² f _i (¯ x)(t _n v + 1

2 t _n ² y _n ) ® + kt n v + 1

2 t n 2 y n k ² · β i (¯ x; t n v + 1

2 t n 2 y n ),

where lim _n→∞ β _i (¯ x; t _n v + ¹ ₂ t _n ² y _n ) = 0. Since ­∇f i (¯ x), v® = 0, we have 1

t n 2

·

f _i (¯ x + t _n v + 1

2 t _n ² y _n ) − f _i (¯ x)

¸

= 1

2 ­∇f i (¯ x), y n ® + 1 2 ­v + 1

2 t n y n , ∇ ² f i (¯ x)(v + 1 2 t n y n ) ® + kv + 1

2 t _n y _n k ² · β i (¯ x; t _n v + 1

2 t _n ² y _n ).

Then, we have

n→∞ lim 1 t _n ²

·

f _i (¯ x + t _n v + 1

2 t _n ² y _n ) − f _i (¯ x)

¸

= 1

2 ­∇f _i (¯ x), y® + 1

2 ­v, ∇ ² f _i (¯ x)v® < 0.

So, there exists a natural number N such that for all n ≧ N, 1

t _n ²

·

f _i (¯ x + t _n v + 1

2 t _n ² y _n ) − f _i (¯ x)

¸

< 0.

Thus we have

f i (¯ x + t n v + 1

2 t n 2 y n ) < f i (¯ x) for all n ≧ N.

Since ¯ x is an efficient solution of (VP), by choosing a subsequence of {¯ x + t _n v + ¹ ₂ t ² _n y _n }, if necessary, we can assume that ˜ I = {j : f _j (¯ x + t _n v +

1

2 t n 2 y n ) > f j (¯ x)} is constant for all n ≧ N. By the twice differentiability f j , j ∈ ˜ I, at ¯ x, we have

f _j (¯ x + t _n v + 1

2 t _n ² y _n ) − f _j (¯ x)

= ­∇f j (¯ x), t n v + 1

2 t n 2 y n ® + 1

2 ­t n v + 1

2 t n 2 y n , ∇ ² f j (¯ x)(t n v + 1

2 t n 2 y n ) ® + kt _n v + 1

2 t _n ² y _n k ² · β j (¯ x; t _n v + 1

2 t _n ² y _n ),

where lim _n→∞ β _j (¯ x; t _n v + ¹ ₂ t _n ² y _n ) = 0. Since ­∇f j (¯ x), v® = 0, we have

­∇f _j (¯ x), y _n ® + ­v + 1

2 t _n y _n , ∇ ² f _j (¯ x)(v + 1 2 t _n y _n ) ® + 2kv + 1

2 t _n y _n k ² · β j (¯ x; t _n v + 1

2 t _n ² y _n ) > 0

for all n ≧ N and for all j ∈ ˜ I. Thus ­∇f j (¯ x), y® + ­v, ∇ ² f j (¯ x)v® ≧ 0 for all j ∈ ˜ I. Since ­∇f j (¯ x), y® + ­v, ∇ ² f _j (¯ x)v ®

≦ 0 for all j ∈ I, ˜ ­∇f j (¯ x), y® + ­v, ∇ ² f j (¯ x)v® = 0. For all j ∈ ˜ I, we have

f

(¯ x)−f

(¯ x+t

v+

t

y

) f

(¯ x+t

v+

t

y

)−f

(¯ x)

=

£

2

­

®

­

v+¹₂tnyn,∇²f_i(¯x)(v+¹₂tnyn)

®

+kv+¹₂tnynk²·βi(¯x;tnv+¹₂tn2yn)

¤

1 2

­

®

­

v+¹₂tnyn,∇²fj(¯x)(v+¹₂tnyn)

®

+kv+¹₂tnynk²·βj(¯x;tnv+¹₂tn2yn)

.

Thus for all j ∈ ˜ I,

n→∞ lim

f i (¯ x) − f i (¯ x + t n v + ¹ ₂ t n 2 y n ) f j (¯ x + t n v + ¹ ₂ t n 2 y n ) − f j (¯ x) = ∞,

which contradicts the proper efficiency of ¯ x. Hence for each i ∈ {1, . . . , p},

{y|­∇f i (¯ x), y® + ­v, ∇ ² f _i (¯ x)v® < 0}

∩ {y|­∇f j (¯ x), y® + ­v, ∇ ² f j (¯ x)v® ≦ 0, j 6= i}

∩ K ² (S, ¯ x, v) = ∅.

Hence we obtain the conclusion of Theorem 2.1. ¤ Remark 2.1. Since K ² (S, ¯ x, 0) = K(S, ¯ x) and 0 ∈ K(S, ¯ x), letting v = 0, we can obtain from Theorem 2.1 that if ¯ x ∈ S is a properly efficient solution of (VP), then for each i ∈ {1, . . . , p},

{y | ­∇f _i (¯ x), y® < 0} ∩ {y | ­∇f _j (¯ x), y® ≦ 0, j 6= i} ∩ K(S, ¯ x) = ∅, equivalently,

{y | ¡­∇f 1 (¯ x), y®, . . . , ­∇f p (¯ x), y®¢ ∈ −R ^p ₊ \ {0}} ∩ K(S, ¯ x) = ∅.

Remark 2.2. Suppose that the constraint set S of (VP) is closed and convex. If ¯ x ∈ S is a properly efficient solution of (VP), then ¯ x ∈ S is a solution of the following vector variational inequality:

¡­∇f 1 (¯ x), s − ¯ x®, . . . , ­∇f p (¯ x), s − ¯ x®¢ 6∈ −R ^p ₊ \ {0}

for any s ∈ S.

The vector variational inequality can be found in [8].

We give an example illustrating Theorem 2.1.

Example 2.1. Let f 1 (x 1 , x 2 , x 3 ) = x 1 , f 2 (x 1 , x 2 , x 3 ) = x 2 and f (x 1 , x 2 , x 3 ) = (x 1 , x 2 ). Let S = {(x 1 , x 2 , x 3 ) ∈ R ³ | x 2 ≧ −x 1 }.

Consider a vector optimization problem (VP):

Minimize f (x 1 , x 2 , x 3 ) subject to (x 1 , x 2 , x 3 ) ∈ S.

Let ¯ x = (0, 0, 0). Then ¯ x is a properly efficient solution of (VP) and K(S, (0, 0, 0)) = S. Then we have

A := {(v 1 , v 2 , v 3 )| ­∇f _i (0, 0, 0), (v 1 , v 2 , v 3 )® = 0, i = 1, 2}

= {(v 1 , v 2 , v 3 )| (1, 0, 0) ^t (v 1 , v 2 , v 3 ) = 0, (0, 1, 0) ^t (v 1 , v 2 , v 3 ) = 0}

= {(0, 0, v ₃ )| v ₃ ∈ R}.

Hence A ∩ K(S, (0, 0, 0)) = {(0, 0, v ₃ )| v ₃ ∈ R}.

Also, we have

(y 1 , y 2 , y 3 ) ∈ K ² (S, (0, 0, 0), (0, 0, v 3 ))

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y 1 , y 2 , y 3 ) s.t. (0, 0, 0) + t _n (0, 0, v 3 ) + 1

2 t ² _n (y ⁿ ₁ , y ⁿ ₂ , y ₃ ⁿ ) ∈ S

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y 1 , y 2 , y 3 ) s.t. ( 1

2 t ² _n y ₁ ⁿ , 1

2 t ² _n y ₂ ⁿ , t n v 3 + 1

2 t ² _n y ₃ ⁿ ) ∈ S

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y 1 , y 2 , y 3 ) s.t. 1

2 t ² _n y ⁿ ₂ ≧ − 1 2 t ² _n y ⁿ ₁

⇐⇒ y 2 ≧ −y 1 .

Hence K ² (S, (0, 0, 0), (0, 0, v 3 )) = {(y 1 , y 2 , y 3 ) ∈ R ³ | y 2 ≧ −y 1 }. Let v = (0, 0, v 3 ), where v 3 ∈ R. Then we have

{y | ­∇f 1 (¯ x), y® + ­v, ∇ ² f 1 (¯ x)v® < 0}

∩ {y | ­∇f 2 (¯ x), y® + ­v, ∇ ² f 2 (¯ x)v® ≦ 0}

= {y | (1, 0, 0) ^t (y 1 , y 2 , y 3 ) < 0} ∩ {y| (0, 1, 0) ^t (y 1 , y 2 , y 3 ) ≦ 0}

= {y | y 1 < 0, y 2 ≦ 0}.

Thus we have

{y | ­∇f 1 (¯ x), y® + ­v, ∇ ² f ₁ (¯ x)v® < 0}

∩ {y | ­∇f 2 (¯ x), y® + ­v, ∇ ² f 2 (¯ x)v® ≦ 0}

∩ K ² (S, (0, 0, 0), v) = ∅.

Similarly,

{y | ­∇f 2 (¯ x), y® + ­v, ∇ ² f 2 (¯ x)v® < 0}

∩ {y | ­∇f 1 (¯ x), y® + ­v, ∇ ² f 1 (¯ x)v® ≦ 0}

∩ K ² (S, (0, 0, 0), v) = ∅.

Thus the conclusion of Theorem 2.1 holds. ¤

The following example shows that Theorem 2.1 can not be extended

to the efficient solution of (VP).

Example 2.2. Let f 1 (x 1 , x 2 , x 3 ) = x 1 , f 2 (x 1 , x 2 , x 3 ) = x 2 and f (x 1 , x 2 , x 3 ) = (x 1 , x 2 ). Let S = {(x 1 , x 2 , x 3 )| x 2 = x ² ₁ , x 3 ∈ R}. Con- sider a vector optimization problem (VP):

Minimize f (x ₁ , x ₂ , x ₃ ) subject to (x 1 , x 2 , x 3 ) ∈ S.

Then ¯ x = (0, 0, 0) is an efficient solution of (VP), but not a properly ef- ficient solution of (VP). Also, K(S, ¯ x) = {(x 1 , 0, x 3 )|x 1 , x 3 ∈ R}. More- over we have

{v ∈ R ³ | ­∇f 1 (¯ x), (v 1 , v 2 , v 3 )® = 0, ­∇f 2 (¯ x), (v 1 , v 2 , v 3 )® = 0}

= {v ∈ R ³ | v 1 = 0, v 2 = 0, v 3 ∈ R}

= {(0, 0, v 3 ) ∈ R ³ | v 3 ∈ R}.

Thus

v := (0, 0, 1) ∈ {v ∈ R ³ | ­∇f i (¯ x), (v 1 , v 2 , v 3 )® = 0, i = 1, 2} ∩ K(S, ¯ x).

Also, we have

(y 1 , y 2 , y 3 ) ∈ K ² (S, (0, 0, 0), (0, 0, 1))

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y ₁ , y ₂ , y ₃ ) s.t.

(0, 0, 0) + t _n (0, 0, 1) + 1

2 t ² _n (y ⁿ ₁ , y ₂ ⁿ , y ₃ ⁿ ) ∈ S

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y 1 , y 2 , y 3 ) s.t.

( 1

2 t ² _n y ₁ ⁿ , 1

2 t ² _n y ₂ ⁿ , t n + 1

2 t ² _n y ⁿ ₃ ) ∈ S

⇐⇒ ∃t n → 0 ⁺ , (y ₁ ⁿ , y ⁿ ₂ , y ⁿ ₃ ) → (y 1 , y 2 , y 3 ) s.t. 1

2 t ² _n y ₂ ⁿ = 1

4 t ⁴ _n (y ₁ ⁿ ) ²

⇐⇒ y 2 = 0.

Hence we have

{y | ­∇f 1 (¯ x), y® + ­v, ∇ ² f ₁ (¯ x)v® < 0}

∩ {y| ­∇f 2 (¯ x), y® + ­v, ∇ ² f 2 (¯ x)v® ≦ 0} ∩ K ² (S, (0, 0, 0), (0, 0, 1))

= {(y 1 , y 2 , y 3 )| y 1 < 0, y 2 ≦ 0, y 3 ∈ R} ∩ {(y 1 , 0, y 3 )| y 1 ∈ R, y 3 ∈ R}

6= ∅.

So, the conclusion of Theorem 2.1 does not hold. ¤

We can easily obtain the following second order necessary optimality condition for weakly efficient solutions of (VP):

Theorem 2.2. Suppose that f _i , i = 1, . . . , p, are twice differentiable.

Let x ∈ S be a weakly efficient solution of (VP). If ¯ ­∇f k (¯ x), v® = 0, k = 1, . . . , p, and v ∈ K(S, ¯ x), then

{y | ­∇f i (¯ x), y® + ­v, ∇ ² f _i (¯ x)v® < 0, i = 1, . . . , p} ∩ K ² (S, ¯ x, v) = ∅.

3. Nonsmooth versions of Theorems 2.1 and 2.2

In this section, using the arguments in the proofs of Ward and Lee [11, 12], we obtain the nonsmooth versions of Theorems 2.1 and 2.2.

Theorem 3.1 ([19], (Intersection Theorem)). Let S _i , i = 0, 1, . . . , p be a nonempty closed subset of R ⁿ and x ∈ T p

i=0 S _i . Suppose that

p

X

i=0

y _i = 0, y _i ∈ N (S i , x), i = 0, 1, . . . , p, imply y _i = 0, i = 0, 1, . . . , p.

Then we have

K ² (S 0 , x, v) ∩

p

\

i=1

T ² (S i , x, v) ⊂ K ² (

p

\

i=0

S i , x, v).

Using the above Theorem 3.1, we can obtain the nonsmooth version of Theorem 2.1 as follows.

Theorem 3.2. Let the constraint set S of (VP) be a nonempty closed subset of R ⁿ and x ∈ S, and suppose that the functions f ¯ i , i = 1, . . . , p, of (VP) are lower semicontinuous. Assume that

(3.1)

p

X

i=0

z i = 0, z 0 ∈ N (S, ¯ x) and z i ∈ ∂ ^∞ f i (¯ x), i = 1, . . . , p imply z i = 0, i = 0, 1, . . . , p.

Let x ∈ S be a properly efficient solution of (VP). If f ¯ _i ^T (¯ x; v) = 0, i = 1, . . . , p, and v ∈ K(S, ¯ x), then for each i ∈ {1, . . . , p},

(3.2)

{y| d ² f _i ^T (¯ x; v, y) < 0, d ² f _j ^T (¯ x; v, y) ≦ 0, j 6= i} ∩ K ² (S, ¯ x, v) = ∅.

Proof. Let v be such that f _i ^T (¯ x; v) = 0, i = 1, . . . , p, and v ∈ K(S, ¯ x).

Suppose that (3.2) is false. Reordering the f i , if necessary, we say that there exists y ∈ K ² (S, ¯ x, v) such that

d ² f ₁ ^T (¯ x; v, y) < 0 and d ² f _i ^T (¯ x; v, y) ≦ 0, i = 2, . . . , p.

Then we can choose r < 0 such that d ² f ₁ ^T (¯ x; v, y) < r. Define S ₀ := S × R ^p

and

S i := {(x, r 1 , . . . , r p ) ∈ R ^n+p | f i (x) ≦ r i }, i = 1, . . . , p.

Since f i is lower semicontinuous, S i is closed. Since y ∈ K ² (S, ¯ x, v), then (y, r, 0, . . . , 0) ∈ K ² (S 0 , (¯ x, f (¯ x)), (v, 0, . . . , 0)).

Indeed,

y ∈ K ² (S, ¯ x, v)

⇐⇒ ∃t n → 0 ⁺ , y n → y s.t. ¯ x + t n v + 1

2 t ² _n y n ∈ S

⇒ (¯ x, f 1 (¯ x), . . . , f _p (¯ x)) + t _n (v, 0, . . . , 0) + 1

2 t ² _n (y _n , r, 0, . . . , 0)

= (¯ x + t _n v + 1

2 t ² _n y _n , f 1 (¯ x) + 1

2 t ² _n r, f 2 (¯ x), . . . , f _p (¯ x))

∈ S × R ^p = S 0

⇒ (y, r, 0, . . . , 0) ∈ K ² (S ₀ , (¯ x, f ₁ (¯ x), . . . , f _p (¯ x)), (v, 0, . . . , 0)).

Since d ² f ₁ ^T (¯ x; v, y) < r, (y, r) ∈ epid ² f ₁ ^T (¯ x; v, ·) = T ² (epif 1 , (¯ x, f 1 (¯ x)), (v, f ₁ ^T (¯ x, v))). Hence we have (y, r, 0, . . . , 0) ∈ T ² (S 1 , (¯ x, f (¯ x)), (v, 0, . . . , 0)). Since d ² f _i ^T (¯ x; v, y) ≤ 0, i = 2, . . . , p, then (y, 0) ∈ T ² (epif _i , (¯ x, f _i (¯ x)), (v, f _i ^T (¯ x, v)). So we have (y, r, 0, . . . , 0) ∈ T ² (S _i , (¯ x, f (¯ x)), (v, 0, . . . , 0)), i = 2, . . . , p. Therefore, we have

(y, r, 0, . . . , 0)

∈ K ² (S 0 , (¯ x, f (¯ x)), (v, 0, . . . , 0)) ∩

p

\

i=1

T ² (S i , (¯ x, f (¯ x)), (v, 0, . . . , 0)).

Let d i := (x ^∗ ₀ ⁱ , d ⁱ ₁ , . . . , d ⁱ _p ) ∈ N (S i , (¯ x, f (¯ x))), i = 0, 1, . . . , p with P p

i=0 d i = 0. We will prove that d i = 0, i = 0, 1, . . . , p. We notice that

N (S 0 , (¯ x, f (¯ x))) = N (S, ¯ x) × N (R ^p , f (¯ x))

= N (S, ¯ x) × {0}.

Since d 0 ∈ N (S 0 , (¯ x, f (¯ x))), x ^∗ ₀ ⁰ ∈ N (S, ¯ x) and d ⁰ _i = 0, i = 1, . . . , p. We can check that for i = 1, . . . , p,

N (S i , (¯ x, f (¯ x))) = {(x ^∗ , y ^∗ ₁ , . . . , y _p ^∗ ) ∈ R ^n+p | y ^∗ _j = 0, j 6= i, (x ^∗ , y _i ^∗ ) ∈ N (epif i , (¯ x, f i (¯ x)))}.

Since d i ∈ N (S i , (¯ x, f (¯ x))), i = 1, . . . , p, then d ⁱ _j = 0, j 6= i and (x ^∗ ₀ ⁱ , d ⁱ _i ) ∈ N (epif i , (¯ x, f i (¯ x))). Since P p

i=0 d i = 0, then P p

i=0 x ^∗ ₀ ⁱ = 0 and d ⁱ _i = 0, i = 1, . . . , p. Hence we have

p

X

i=0

x ^∗ ₀ ⁱ = 0, x ^∗ ₀ ⁰ ∈ N (S, ¯ x) and x ^∗ ₀ ⁱ ∈ ∂ ^∞ f i (¯ x), i = 1, . . . , p.

So, from assumption (3.1), x ^∗ ₀ ⁱ = 0, i = 0, 1, . . . , p. Consequently, d _i = 0, i = 0, 1, . . . , p. Thus from Theorem 3.1, we have

(y, r, 0, . . . , 0) ∈ K ² (

p

\

i=0

S _i , (¯ x, f (¯ x)), (v, 0, . . . , 0)).

So, there exist t _n → 0 ⁺ , (y _n , r ¹ _n . . . , r ^p _n ) → (y, r, 0, . . . , 0) such that

(¯ x, f 1 (¯ x), . . . , f p (¯ x)) + t n (v, 0, . . . , 0) + 1

2 t ² _n (y n , r _n ¹ , . . . , r _n ^p ) ∈

p

\

i=0

S i

that is, ¯ x + t n v + ¹ ₂ t ² _n y n ∈ S and f i (¯ x + t n v + 1

2 t ² _n y n ) ≦ f i (¯ x) + 1

2 t ² _n r ⁱ _n , i = 1, . . . , p.

So, we have

(f 1 (¯ x), . . . , f _p (¯ x)) + 1

2 t ² _n (r _n ¹ , . . . , r ^p _n ) ∈ f (S) + R ^p ₊ . Since (r ¹ _n , . . . , r _n ^p ) → (r, 0, . . . , 0), then we have

(r, 0, . . . , 0) ∈ K(f (S) + R ^p ₊ , f (¯ x)).

Since r < 0, we have K(f (S) + R ^p ₊ , f (¯ x)) T(−R ^p ₊ ) 6= {0}. Notice

that ¯ x ∈ S is properly efficient for (VP) if and only if K(f (S) +

R ^p ₊ , f (¯ x)) T(−R ^p ₊ ) = {0} (see, [6, 25]). So, ¯ x ∈ S is not a properly

efficient solution of (VP). ¤

By Remarks 1.1 and 1.5, and Theorem 3.2, we can easily obtain the following corollary.

Corollary 3.1. Let the constraint set S of (VP) be a nonempty closed subset of R ⁿ , and suppose that the functions f _i , i = 1, . . . , p, of (VP) are locally Lipschitzian. Let ¯ x ∈ S be a properly efficient solution of (VP). If f _i ⁺ (¯ x; v) = 0, i = 1, . . . , p and v ∈ K(S, ¯ x), then for each i ∈ {1, . . . , p},

{y | d ² f _i ⁺ (¯ x; v, y) < 0, d ² f _j ⁺ (¯ x; v, y) ≦ 0, j 6= i} ∩ K ² (S, ¯ x, v) = ∅.

By Remarks 1.2 and 1.4, and Theorem 3.2, we can obtain the following first order necessary optimality theorem for a properly efficient solution of (VP).

Corollary 3.2. Let the constraint set S of (VP) be a nonempty closed subset of R ⁿ and x ∈ S, and suppose that the functions f ¯ i , i = 1, . . . , p, of (VP) are lower semicontinuous. Assume that

p

X

i=0

z _i = 0, z 0 ∈ N (S, ¯ x) and z _i ∈ ∂ ^∞ f _i (¯ x), i = 1, . . . , p imply z _i = 0, i = 0, 1, . . . , p, and v = 0.

Let x ∈ S be a properly efficient solution of (VP). If f ¯ _i ^T (¯ x; 0) = 0, i = 1, . . . , p, then for each i ∈ {1, . . . , p},

{y| f _i ^T (¯ x; y) < 0, f _j ^T (¯ x; y) ≦ 0, j 6= i} ∩ K(S, ¯ x) = ∅.

Following the proofs of Ward and Lee [11, 12], we obtain the following second order necessary optimality theorem for weakly efficient solutions of the vector optimization problem (VP).

Theorem 3.3. Let the constraint set S of (VP) be a nonempty closed subset of R ⁿ and x ∈ S, and suppose that the functions f ¯ i , i = 1, . . . , p, of (VP) are lower semicontinuous. Assume that

(3.3)

p

X

i=0

z _i = 0, z 0 ∈ N (S, ¯ x) and z _i ∈ ∂ ^∞ f _i (¯ x), i = 1, . . . , p

imply z _i = 0, i = 0, 1, . . . , p.

Let x ∈ S be a weakly efficient solution of (VP). If f ¯ _i ^T (¯ x; v) = 0, i = 1, . . . , p and v ∈ K(S, ¯ x),

(3.4) {y| d ² f _i ^T (¯ x; v, y) < 0, i = 1, . . . , p} ∩ K ² (S, ¯ x, v) = ∅.

Proof. Let v be such that f _i ^T (¯ x; v) = 0, i = 1, . . . , p, and v ∈ K(S, ¯ x).

Suppose that (3.4) is false. Then there exists y ∈ K ² (S, ¯ x, v) such that d ² f _i ^T (¯ x; v, y) < 0, i = 1, . . . , p.

Then we can choose r _i < 0 such that d ² f _i ^T (¯ x; v, y) < r _i , i = 1, . . . , p.

Define

S 0 := S × R ^p and

S _i := {(x, r 1 , . . . , r _p ) ∈ R ^n+p | f i (x) ≦ r _i }, i = 1, . . . , p.

Since f i is lower semicontinuous, S i is closed. Since y ∈ K ² (S, ¯ x, v), then (y, r ₁ , . . . , r _p ) ∈ K ² (S ₀ , (¯ x, f (¯ x)), (v, 0, . . . , 0)). Since d ² f _i ^T (¯ x; v, y)

< r i , (y, r i ) ∈ epid ² f _i ^T (¯ x; v, ·) = T ² (epif i , (¯ x, f i (¯ x)), (v, f _i ^T (¯ x, v))).

Hence we have (y, r 1 , . . . , r _p ) ∈ T ² (S _i , (¯ x, f (¯ x)), (v, 0, . . . , 0)). Therefore, we have

(y, r 1 , . . . , r p )

∈ K ² (S 0 , (¯ x, f (¯ x)), (v, 0, . . . , 0)) ∩

p

\

i=1

T ² (S i , (¯ x, f (¯ x)), (v, 0, . . . , 0)).

Let d _i := (x ^∗ ₀ ⁱ , d ⁱ ₁ , . . . , d ⁱ _p ) ∈ N (S _i , (¯ x, f (¯ x))), i = 0, 1, . . . , p with P p

i=0 d _i = 0. By the same argument in the proof of Theorem 3.2, we can prove that d i = 0, i = 0, 1, . . . , p. Thus from Theorem 3.1, we have

(y, r 1 , . . . , r p ) ∈ K ² (

p

\

i=0

S i , (¯ x, f (¯ x)), (v, 0, . . . , 0)).

So, there exist t n → 0 ⁺ , (y n , r ¹ _n , . . . , r _n ^p ) → (y, r 1 , . . . , r p ), r _n ⁱ < 0 such that

(¯ x, f 1 (¯ x), . . . , f _p (¯ x)) + t _n (v, 0, . . . , 0) + 1

2 t ² _n (y _n , r _n ¹ , . . . , r ^p _n ) ∈

p

\

i=0

S _i ,

that is, ¯ x + t _n v + ¹ ₂ t ² _n y _n ∈ S and f _i (¯ x + t _n v + 1

2 t ² _n y _n ) ≦ f _i (¯ x) + 1

2 t ² _n r ⁱ _n , i = 1, . . . , p.

Since r _n ⁱ < 0, i = 1, . . . , p, then f i (¯ x + t n v + ¹ ₂ t ² _n y n ) < f i (¯ x). Thus ¯ x ∈ S

is not weakly efficient for (VP). ¤

By Remarks 1.1 and 1.5, and Theorem 3.3, we can easily obtain the following corollary.

Corollary 3.3. Let the constraint set S of (VP) be a nonempty closed subset of R ⁿ , and suppose that the functions f i , i = 1, . . . , p, of (VP) are locally Lipschitzian. Let ¯ x ∈ S be a weakly efficient solution of (VP). If f _i ⁺ (¯ x; v) = 0, i = 1, . . . , p and v ∈ K(S, ¯ x), then

{y | d ² f _i ⁺ (¯ x; v, y) < 0, i = 1, . . . , p} ∩ K ² (S, ¯ x, v) = ∅.

By Remarks 1.2 and 1.4, and Theorem 3.3, we can obtain the following first order necessary optimality theorem for a weakly efficient solution of (VP).

Corollary 3.4 ([12]). Let the constraint set S of (VP) be a nonemp- ty closed subset of R ⁿ and x ∈ S, and suppose that the functions f ¯ i , i = 1, . . . , p, of (VP) are lower semicontinuous. Assume that

p

X

i=0

z i = 0, z 0 ∈ N (S, ¯ x) and z i ∈ ∂ ^∞ f i (¯ x), i = 1, . . . , p

imply z i = 0, i = 0, 1, . . . , p.

Let x ∈ S be a weakly efficient solution of (VP). If f ¯ _i ^T (¯ x; 0) = 0, i = 1, . . . , p, then

{y | f _i ^T (¯ x; y) < 0, i = 1, . . . , p} ∩ K(S, ¯ x) = ∅.

References

[1] J. P. Aubin, Mathematical Methods of Game and Economic Theory, North-

Holland (1979).

[2] D. Blackwell and M. A. Girshick, Theory of Games and Statistical Decisions, John Wiley and Sons, New York, 1954.

[3] T. S. Ferguson, Mathematical Statistics, A Decision Theoretic Approach, Aca- demic Press New York, 1967.

[4] T. Takayama, Mathematical Economics, The Dryden Press, 1974.

[5] M. Zeleny, Multiple Criteria Decision Making, McGraw-Hill, New York, 1982.

[6] Y. Sawaragi, H. Nakayama and T. Tanino, Theory of Multiobjective Optimiza- tion, Academic Press, New York, 1985.

[7] F. Giannessi, Theorems of alternative, quadratic programs and complementarity problems in Variational Inequalities and Complementarity Problems, edited by R. W. Cottle, F. Giannessi, and J. L. Lions, John Wiley and Sons, Chichester, England (1980), 151–186.

[8] , On Minty variational principle, In New Trends in Mathematical Pro- gramming, Kluwer Academic Publishers, 1997.

[9] G. M. Lee, On Relations between vector variational inequality and vector opti- mization problem, in: X. Q. Yang et al. eds: Progress in Optimization, Kluwer Academic Publishers (2000), 167–179.

[10] X. Q. Yang, Vector variational inequality and multiobjective pseudolinear pro- gramming, J. Optim. Theory Appl. 95 (1997), 431–443.

[11] D. E. Ward and G. M. Lee, Generalized properly efficient solutions of vector optimization problems, Math. Methods of Oper. Res. 53 (2001), 215–232.

[12] , On relations between vector optimization problems and vector varia- tional inequalities, J. Optim. Theory Appl. 113 (2002), 583–596.

[13] J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, Springer-Verlag New York, Inc., 2000.

[14] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, 1983.

[15] F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer-Verlag New York, Inc., 1998.

[16] V. F. Demyanov and L. V. Vasilev, Nondifferentiable Optimization, Optimiza- tion Software, New York, 1985.

[17] B. S. Mordukhovich, Sensitivity analysis in nonsmooth optimization In The- oretical Aspects of Industrial Design, D. A. Field and V. Komkov eds, SIAM Publications, Philadelphia (1992), 32–46.

[18] J. P. Penot, Optimality conditions in mathematical programming and composite optimization, Math. Program. 67 (1994), 225–245.

[19] D. E. Ward, Epiderivatives of the marginal function in nonsmooth parametric optimization, Optimization 31 (1994), 47–61.

[20] , A chain rule for parabolic second-order epiderivatives, Optimization 28 (1994), 223–236.

[21] , Calculus for parabolic second-order derivatives, Set-Valued Anal. 1 (1993), 213–246.

[22] J. -P. Aubin and H. Frankowska, Set-Valued Analysis, Birkh¨ a user, Boston, 1990.

[23] M. Studniarski, Second-order necessary conditions for optimality in nonsmooth nonlinear programming, J. Math. Anal. Appl. 154 (1991), 303–317.

[24] A. M. Geoffrion, Proper efficiency and the theory of vector maximization, J.

Math. Anal. Appl. 22 (1968), 618–630.

[25] H. P. Benson, An improved definition of proper efficiency for vector minimiza- tion with respect to cones, J. Math. Anal. Appl. 71 (1978), 232–241.

Department of Applied Mathematics Pukyong National University

Pusan 608-737, Korea E-mail: [email protected]

[email protected]