# Necessary Conditions for Weak Sharp Minima in Cone-Constrained Optimization Problems

Authors: W. Y. Zhang; S. Xu; S. J. Li
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

We study weak sharp minima for optimization problems with
cone constraints. Some necessary conditions for weak sharp minima of higher order are
established by means of upper Studniarski or Dini directional derivatives. In particular,
when the objective and constrained functions are strict derivative, a necessary condition
is obtained by a normal cone.


---

## Body

## 1. Introduction

The notion of a weak sharp minimum in general mathematical program problems was first introduced by Ferris in [1]. It is an extension of a sharp (or strongly unique) minimum in [2]. Weak sharp minima play an important role in the sensitivity analysis [3, 4] and convergence analysis of a wide range of optimization algorithms [5–7]. Recently, the study of weak sharp solution set covers real-valued optimization problems [5, 8–10] and multiobjective optimization problems [11–13]. Moreover, it has been extended to convex-composite optimization with inequality constraints [14] and semi-infinite programs [15].The weak sharp minima defined in [5] specified first-order growth of the objective function away from the set of optimal solutions. Recently, Studniarski [16] considered a special class of nonsmooth functions which are pointwise maxima of finite collections of strictly differentiable functions and presented a characterization of weak sharp local minima of order one. In addition, Studniarski [17] established the Kuhn-Tucker conditions for a nonlinear programming problem with constraints of both inequality and equality types, where the objective and inequality constrained functions are locally Lipschitzian and the equality constraints are differentiable.Weak sharp minima of higher order are also of interest in sensitivity analysis in parametric optimization. In particular, the presence of weak sharp minima in parametric optimization leads to Hëlder continuity properties of the associated solution mappings in [18]. Bonnans and Ioffe [19] studied sufficient conditions and characterizations for weak sharp minima of order two in the case that the objective function is a pointwise maximum of twice continuously differentiable convex functions. In [20], Ward presented some necessary conditions for weak sharp minima of higher order for optimization problems with a set constraint. In [21], Studniarski and Ward obtained some sufficient conditions and characterizations for weak sharp local minimizer of higher order in terms of the limiting proximal normal cone and a generalization of the contingent cone.However, to the best of our knowledge, there has no research concerning weak sharp minima for optimization with cone constraints although conic programming is a very hot research topic in optimization. In this paper, we first discuss necessary conditions for weak sharp minima of higher order in terms of the upper Studniarski and Dini directional derivatives and various tangent cones. In particular, by means of a normal cone, we provide a necessary condition for weak sharp minima of order one when the objective and constrained functions are strict derivative.This paper is organized as follows. In Section2, we recall the basic definitions. In Section 3, we establish several necessary conditions for a weak sharp minimizer of higher order.


## 2. Notions and Preliminaries

Consider the following optimization problem with cone constraints(2.1)min⁡⁡f(x)s.t.x∈Q,g(x)∈-K,
where X is finite space and Y is a normed space. f is an extended real-valued function defined on X. S and K are nontrivial closed convex cones in Y, in which S defines an order. g:X→Y is a vector-valued mapping. Q is a closed convex subset of X. Let G={x∈X:g(x)∈-K}. Denote by M the feasible set, that is, M=Q∩G.Definition 2.1 (see [21]).
Let∥·∥ be the Euclidean norm on X. Suppose that f is a constant on the set S̅⊂X, and let x̅∈S̅∩M and m≥1. For x∈X, let
(2.2)dist⁡(x,S̅)m∶=inf⁡⁡{‖y-x‖m:y∈S̅}.(a)
We say thatx̅ is a weak sharp minimizer of order m with module α>0 for (2.1), if there exists α>0 such that
(2.3)f(x)-f(x̅)≥αdist⁡(x,S̅)m,∀x∈M.Letg:X→Y be a vector-valued mapping. The Hadamard and Dini derivatives of g at x̅ in a direction v∈X are, respectively, defined by
(2.4)dHg(x̅,v)=lim⁡t→0+,u→v⁡g(x̅+tu)-g(x̅)t,dDg(x̅,v)=lim⁡t→0+g(x̅+tv)-g(x̅)t.Letf:X→R∪{+∞} be finite at x̅ and m≥1 an integer number. The upper Studniarski and Dini derivatives of order m at x̅ in a direction v∈X are, respectively, defined by
(2.5)d¯Smf(x̅,v)=limsup⁡t→0+,u→v⁡f(x̅+tu)-f(x̅)tm,d¯Dmf(x̅,v)=limsup⁡t→0+⁡f(x̅+tv)-f(x̅)tm.IfA⊂X, then, the indicator function of A is iA(x)=0 if x∈A and iA(x)=+∞ if x∉A. The support function for A is defined by ψA*(x)∶=sup{〈x*,x〉:x*∈A}.LetA be a closed and convex subset of X, we define the projection of a point x∈X onto the set A, denoted by P(A,x) as follows:
(2.6)P(A,x)={y∈A:‖x-y‖X=min⁡u∈A⁡‖x-u‖X}.LetK be a cone in a norm space Z. Denote by K* the dual cone of K(2.7)K*={z*:〈z*,z〉≥0,∀z∈K},
where Z* is the topological dual of Z. Note that K* is a w*-closed convex cone. Let us introduce the following set:
(2.8)K0={z∈K:〈z*,z〉>0,∀z*∈K*∖{0}}.Definition 2.2.
LetA be a subset of normed vector space Z and x∈clA, then(a)
(see [22]) the contingent cone to the set A is T(A,x)={v∈Rn:∃tn→0+,vn→v,withx+tnvn∈A},(b)
(see [23]) the Clarke tangent cone to the set A is K(A,x)={v∈Rn:∀A∋xn→x̅,∀tn→0+,∃vn→v,withxn+tnvn∈A},(c)
(see [24]) T̃(A,x)={v∈X:∃tn→0+suchthatx+tnv∈A,∀nlargeenough},(d)
(see [20]) IK(A,x)={v∈X:∃tn→0+suchthat∀vn→v,x+tnvn∈A,∀nlargeenough}.It is easy to see thatIK(A,x)⊂T̃(A,x)⊂T(A,x).A setA is said to be regular at x∈A if T(A,x)=K(A,x). Obviously, every convex set is regular. Moreover, if A is a convex set, we call both the contingent cone and Clarke tangent cone to the set A as tangent cone to the set A.For a nonempty setA⊂X, we define the polar of A to be the set A∘={x*∈X*:〈x*,x〉≤1∀x∈A}. The classic normal cone to A at x is defined dually by the relation N(A,x)=T(A,x)∘.Definition 2.3 (see [17]).
LetE and S be subset of Rn, and let x̅∈clE. The normal cone to E at x̅ relative to S is defined by
(2.9)NS(E,x̅)∶={(xn-wn)tny∈Rn:∃yn⟶y,xn⟶x̅,tn∈(0,+∞),wn∈Rnwithxn∈S,wn∈P(E,xn)andyn=(xn-wn)tn,(∀n)}.Definition 2.4.
Letf map X to another Banach space Y. We say that f admits a strict derivative at x, an element L(X,Y) denoted ∇f(x), provided that for each the following holds
(2.10)lim⁡x′→x,y→v,t→0+⁡f(x′+ty)-f(x′)t=〈∇f(x),v〉.


## 3. Necessary Conditions

In the section, we provide necessary optimality conditions for the problem (2.1), which are formulated in terms of the upper Studniarski and Dini derivatives of the objective function, respectively. Simultaneously, we also apply the indicator function of a set to state the necessary conditions.Theorem 3.1.
Suppose thatS̅ is a closed set. Let  x̅∈S̅ be a weak sharp minimizer of order  m with module  α>0 for the problem (2.1). Suppose that  g is Hadamard derivative at  x̅ in all directions  v∈X. Then,
(3.1)d̅Smf(x̅,v)≥αdist⁡(v,T(S̅,x̅))m,∀v∈T(Q,x̅)∩{u:dHg(x̅,u)∈-int⁡K}.
In particular, if S̅ is regular at x̅, then
(3.2)d̅Smf(x̅,v)≥αdist⁡(v,K(S̅,x̅)),∀v∈T(Q,x̅)∩{u:dHg(x̅,u)∈-int⁡K}.Proof.
Letv∈T(Q,x̅)∩{u:dHg(x̅,u)∈-intK}. By the definition of contingent cone, there exist tn→0+ and vn→v such that x̅+tnvn∈Q. In addition, v≠0, by assumption dHg(x̅,v)∈-intK.
Sinceg is Hadamard derivative at x̅ in the direction v∈X, we have that, for tn→0+,
(3.3)lim⁡n→∞⁡g(x̅+tnvn)-g(x̅)tn=dHg(x̅,v).
Moreover, dHg(x̅,v)∈-intK, then there exists a natural number N1 such that for n≥N1,
(3.4)g(x̅+tnvn)-g(x̅)tn∈-K,
which implies that
(3.5)g(x̅+tnvn)∈g(x̅)-K⊂-K.
Hence,
(3.6)x̅+tnvn∈M=Q∩G.
According to the definition of weak sharp minimizer of order m, we get
(3.7)f(x̅+tnvn)-f(x̅)≥αdist⁡(x̅+tnvn,S̅)m.
Consequently, it follows from (3.7) that
(3.8)f(x̅+tnvn)-f(x̅)tnm≥αdist⁡(x̅+tnvn,S̅)mtnm.
Taking lim sups of both sides in (3.8) as n→∞, we have
(3.9)d̅Smf(x̅,v)≥limsup⁡n→∞⁡f(x̅+tnvn)-f(x̅)tnm≥αlimsup⁡n→∞⁡dist⁡(x̅+tnvn,S̅)mtnm≥αlim⁡inf⁡n→∞⁡dist⁡(x̅+tnvn,S̅)mtnm.
To establish (3.1), we suffice to show that
(3.10)lim⁡inf⁡n→∞⁡dist⁡(x̅+tnvn,S̅)mtnm≥dist⁡(v,T(S̅,x̅))m.
Set
(3.11)L∶=lim⁡inf⁡n→∞⁡dist⁡(x̅+tnvn,S̅)mtnm.
If L=+∞, then (3.10) holds true. Hence, we may assume that L<+∞. Then, for any ϵ>0, there exists a number N, such that, for all k>N,
(3.12)tnk∈B(0,ϵ),vnk∈B(v,ϵ),wnk∈S̅,‖x̅+tnkvnk-wnk‖mtnkm≤L+ϵ.
Set
(3.13)znk∶=(x̅+tnkvnk-wnk)tnk.
Since the sequence {znk} is bounded, we may assume, taking a subsequence if necessary, that it converges to some z∈X with ∥z∥m≤L. For each k>N, we have
(3.14)x̅+tnk(vnk-znk)=wnk∈S̅,v-z∈T(S̅,x̅).
Hence
(3.15)dist⁡(v,T(S̅,x̅))m≤‖v-(v-z)‖m≤L,
and (3.10) holds.
Observe that the regularity atx̅∈S̅ implies that T(S̅,x̅)=K(S̅,x̅). Hence, the inequality (3.2) holds.Theorem 3.2.
Suppose thatS̅ is a closed set. Let  x̅∈S̅ be a weak sharp minimizer of order  m with module  α>0 for the problem (2.1). Suppose that  g is Hadamard derivative at  x̅ in all directions  v∈X. Then,
(3.16)d̅Sm(f+iQ)(x̅,v)≥αdist⁡(v,T(S̅,x̅))m,∀v∈{u:dHg(x̅,u)∈-int⁡K}.
In particular, if S̅ is regular at x̅, then
(3.17)d̅Sm(f+iQ)(x̅,v)≥αdist⁡(v,K(S̅,x̅)),∀v∈{u:dHg(x̅,u)∈-int⁡K}.Proof.
Suppose thatx̅ is a weak sharp minimizer of order m with module α>0 for the problem (2.1), then
(3.18)f(x)-f(x̅)≥αdist⁡(x,S̅)m,∀x∈M.
Since g is the Hadamard derivative at x̅ in the direction v∈X, there exist tn→0+ and vn→v such that
(3.19)lim⁡n→∞⁡g(x̅+tnvn)-g(x̅)tn=dHg(x̅,v).
Moreover, dg(x̅,v)∈-intK, then there exists a natural number N2 such that, for n≥N2,
(3.20)g(x̅+tnvn)-g(x̅)tn∈-K,
which implies that
(3.21)g(x̅+tnvn)∈g(x̅)-K⊂-K.
Therefore,
(3.22)x̅+tnvn∈G.
If x̅+tnvn∈Q, then, by (3.18),
(3.23)f(x̅+tnvn)+iQ(x̅+tnvn)-f(x̅)-iQ(x̅)≥αdist⁡(x̅+tnvn,S̅)m.
On the other hand, if x̅+tnvn∉Q, then iQ(x̅+tnvn)=+∞ and (3.23) still holds true.
Hence, from (3.23), it follows that
(3.24)f(x̅+tnvn)-f(x̅)+iQ(x̅+tnvn)-iQ(x̅)tnm≥αdist⁡(x̅+tnvn,S̅)mtnm.
Taking the lim sups on both sides in (3.24) as n→+∞, we get
(3.25)d̅m(f+iQ)(x̅,v)≥αlim⁡inf⁡n→∞⁡dist⁡(x̅+tnvn,S̅)mtnm.
The rest of the proof is similar to Theorem 3.1 and hence omitted.In what follows, we state other necessary conditions for the weak sharp minimizer of orderm for the problem (2.1) in terms of the cone K0 and T̃(Q,x̅). Note that the necessary conditions do not require the cone K to have nonempty interior.Theorem 3.3.
Suppose thatS̅ is a closed set. Let  x̅∈S̅ be a weak sharp minimizer of order  m with module  α>0 for the problem (2.1). Suppose that  g is Dini derivative at  x̅ in all directions  v∈X. Then,
(3.26)d̅Dmf(x̅,v)≥αdist⁡(v,T(S̅,x̅))m,∀v∈T̃(Q,x̅)∩{u:dDg(x̅,u)∈-K0}.
In particular, if S̅ is regular at x̅, then
(3.27)d̅Dmf(x̅,v)≥αdist⁡(v,K(S̅,x̅))m,∀v∈T̃(Q,x̅)∩{u:dDg(x̅,u)∈-K0}.Proof.
Letv∈T̃(Q,x̅)∩{u:dDg(x̅,u)∈-K0}, then there exists a sequence tn→0+ such that x̅+tnv∈Q for sufficiently large n. In addition,
(3.28)lim⁡n→∞⁡g(x̅+tnv)-g(x̅)tn=dDg(x̅,v),
which leads to the following relation
(3.29)g(x̅+tnv)=g(x̅)+tn⋅dDg(x̅,v)+o(tn),
where o(tn)/tn→0 as n→∞. Since dDg(x̅,v)∈-K0, for any z*∈K*∖{0}, 〈z*,dDg(x̅,v)〉<0, which yields that
(3.30)〈z*,g(x̅+tnv)〉=〈z*,g(x̅)〉+tn[〈z*,dDg(x̅,v)〉+o(tn)tn]≤0
for large enough n. Observing that K is a closed convex cone, it follows that K is weakly closed and
(3.31)g(x̅+tnv)∈-K**=-K.
Consequently, x̅+tnv∈M for sufficiently large n. The rest of the proof is analogue to Theorem 3.1 and thus omitted.By using the method of Theorems3.2 and 3.3, we easily establish the following results.Theorem 3.4.
Suppose thatS̅ is a closed set. Let  x̅∈S̅ be a weak sharp minimizer of order  m with module  α>0 for the problem (2.1). Suppose that  g is Dini derivative at  x̅ in all directions  v∈X. Then,
(3.32)d̅Dm(f+iQ)(x̅,v)≥αdist⁡(v,T(S̅,x̅))m,∀v∈{u:dDg(x̅,u)∈-K0}.
In particular, if S̅ is regular at x̅, then
(3.33)d̅Dm(f+iQ)(x̅,v)≥αdist⁡(v,K(S̅,x̅))m,∀v∈{u:dDg(x̅,u)∈-K0}.SinceIK(A,x)⊂T̃(A,x), the following result is direct consequence of Theorem 3.3.Corollary 3.5.
Suppose thatS̅ is a closed set. Let  x̅∈bdS̅ be a weak sharp minimizer of order  m with module  α>0 for the problem (2.1). Suppose that  g is Dini derivative at  x̅ in all directions  v∈X. Then,
(3.34)d̅Dmf(x̅,v)≥αdist⁡(v,T(S̅,x̅)),∀v∈IK(Q,x̅)∩{u:dDg(x̅,u)∈-K0}.Suppose thatX and Y are finite spaces. In what follow, we apply the normal cone to present a necessary optimality condition for problem (2.1), where the objective and constrained functions are strict derivative.Theorem 3.6.
Suppose thatS̅ is a closed set. Let  x̅∈bdS̅ be a weak sharp minimizer of order one with module  α>0 for the problem (2.1). Suppose that  f and  g are strict derivatives at  x̅. Then, for any  v∈NQ(S̅,x̅)∩{u:〈∇g(x̅),u〉∈-intK} with  ∥v∥=1,
(3.35)〈∇f(x̅),v〉>0.Proof.
Assume that〈∇f(x̅),v〉≤0 for some v∈NQ(S̅,x̅)∩{u:〈∇g(x̅),u〉∈-intK}. Then, by the definition of normal cone, there exist vn→v, xn→x̅, tn∈(0,+∞), wn∈X with xn∈Q, wn∈P(S̅,xn) and
(3.36)vn=xn-wntn.
Since ∥v∥=1 and vn→v, we have vn≠0 for n sufficiently large, and consequently, ∥xn-wn∥=d(xn,S̅).
Observe that the condition (3.36) implies that for n→∞,
(3.37)tn=‖xn-wn‖‖vn‖≤‖xn-x̅‖‖vn‖⟶0.
Moreover, for n→∞, ∥wn-x̅∥≤∥wn-xn∥+∥xn-x̅∥≤2∥xn-x̅∥→0. We can assume that limn→∞(f(wn+tnvn)-f(wn))/tn≤0 since 〈∇f(x̅),v〉≤0. Hence, for any ϵ>0, there exist N1 such that, for all n>N1,
(3.38)f(wn+tnvn)-f(wn)tn<ϵ.
Since g is strict derivative at x̅,
(3.39)lim⁡n→∞⁡g(wn+tnvn)-g(wn)tn=〈∇g(x̅),v〉.
It follows that from 〈∇g(x̅),v〉∈-intK, there exists a natural number N2 such that, for n≥N2,
(3.40)g(wn+tnvn)-g(wn)tn∈-K,
which implies that
(3.41)g(wn+tnvn)∈g(wn)-K⊂-K.
Hence,
(3.42)wn+tnvn∈M=Q∩G.
On the other hand, by assumption, for n≥max{N1,N2}, xn=wn+tnvn,
(3.43)f(wn+tnvn)-f(x̅)=f(wn+tnvn)-f(wn)≥αd(xn,S̅)=α‖xn-wn‖.
Together with relation (3.38), for n≥max{N1,N2}, we have
(3.44)ϵ>f(wn+tnvn)-f(wn)tn≥α‖vn‖.
Taking the limit when n→∞ and for the arbitrary ϵ>0, we deduce that limn→∞∥vn∥=0, which is a contradiction to the fact that v≠0.



---

*Source: 909520-2012-04-09.xml*