PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of springeropenLink to Publisher's site
Journal of Inequalities and Applications
 
J Inequal Appl. 2017; 2017(1): 212.
Published online 2017 September 8. doi:  10.1186/s13660-017-1487-8
PMCID: PMC5591379

Second-order optimality conditions for nonlinear programs and mathematical programs

Abstract

It is well known that second-order information is a basic tool notably in optimality conditions and numerical algorithms. In this work, we present a generalization of optimality conditions to strongly convex functions of order γ with the help of first- and second-order approximations derived from (Optimization 40(3):229-246, 2011) and we study their characterization. Further, we give an example of such a function that arises quite naturally in nonlinear analysis and optimization. An extension of Newton’s method is also given and proved to solve Euler equation with second-order approximation data.

Keywords: strong convexity of order γ, second-order approximation, C1,1 functions, Newton’s method

Introduction

The concept of approximations of mappings was introduced by Thibault [2]. Sweetser [3] considered approximations by subsets of the space of continuous linear maps L(XY), where X and Y are Banach spaces, and Ioffe [4] by the so-called fans. This approach was revised by Jourani and Thibault [5]. Another approach belongs to Allali and Amahroq [1]. Following the same ideas, Amahroq and Gadhi [6, 7] have established optimality conditions to some optimization problems under set-valued mapping constraints.

In this work, we explore the notion of strongly convex functions of order γ; see, for instance, [815] and references therein. Let f be a mapping from a Banach space X into , and let C ⊂ X be a closed convex set. It is well known that the notion of strong convexity plays a central role. On the one hand, it ensures the existence and uniqueness of the optimal solution for the problem

(P)minxCf(x).

On the other hand, if f is twice differentiable, then the strong convexity of f implies that its Hessian matrix is nonsingular, which is an important tool in numerical algorithms. Here we adopt the definition of a second-order approximation [1] to detect some equivalent properties of strongly convex functions of order γ and to characterize the latter. Furthermore, for a C1,1 function f on a finite-dimensional setting, we show some simple facts. We also provide an extension of Newton’s method to solve an Euler equation with second-order approximation data.

The rest of the paper is written as follows. Section 2 contains basic definitions and preliminary results. Section 3 is devoted to mains results. In Section 4, we point out an extension of Newton’s method and prove its local convergence.

Preliminaries

Let X and Y be two Banach spaces. We denote by ℒ(XY) the set of all continuous linear mappings from X into Y, by ℬ(X × XY) the set of all continuous bilinear mappings from X × X into Y, and by 𝔹Y the closed unit ball of Y centered at the origin.

Throughout this paper, X and Y denote the continuous duals of X and Y, respectively, and we write 〈 ⋅ ,  ⋅ 〉 for the canonical bilinear forms with respect to the dualities XX and YY.

Definition 1

[1]

Let f be a mapping from X into Y, x¯X. A set of mappings Af(x¯)L(X,Y) is said to be a first-order approximation of f at [x with macron] if there exist δ > 0 and a function r:X → ℝ satisfying limxx¯r(x)=0 such that

f(x)f(x¯)Af(x¯)(xx¯)+xx¯r(x)BY
1

for all xx¯+δBX.

It is easy to check that Definition 1 is equivalent to the following: for all ε > 0, there exists δ > 0 such that

f(x)f(x¯)Af(x¯)(xx¯)+εxx¯BY
2

for all xx¯+δBX.

Remark 1

If Af(x¯) is a first-order approximation of f at [x with macron], then (2) means that for any xx¯+δBX, there exist A(x)Af(x¯) and b ∈ 𝔹Y such that

f(x)f(x¯)=A(x)(xx¯)+εxx¯b.

Hence, for any xB(x¯,δ) and A(x)Af(x¯),

f(x)f(x¯)A(x)(xx¯)εxx¯.
3

If Af(x¯) is norm-bounded (resp. compact), then it is called a bounded (resp. compact) first-order approximation. Recall that Af(x¯) is a singleton if and only if f is Fréchet differentiable at [x with macron].

The following proposition proved by Allali and Amahroq [1] plays an important role in the sequel in a finite-dimensional setting.

Proposition 1

[1]

Let f:ℝp → ℝ be a locally Lipschitz function at [x with macron]. Then the Clarke subdifferential of f at [x with macron],

cf(x¯):=co{limf(xn):xndomf and xnx¯},
4

is a first-order approximation of f at [x with macron].

In [6], it is also shown that when f is a continuous function, it admits as an approximation the symmetric subdifferential defined and studied in [16].

The next proposition shows that Proposition 1 holds also when f is a vector-valued function. Let us first recall the definition of the generalized Jacobian for a vector-valued function (see [17, 18] for more details) and the definition of upper semicontinuity.

Definition 2

The generalized Jacobian of a function g:ℝp → ℝq at [x with macron], denoted cg(x¯), is the convex hull of all matrices M of the form

M=limn+Jg(xn),

where xnx¯, g is differentiable at xn for all n, and Jg denotes the q × p usual Jacobian matrix of partial derivatives.

Definition 3

A set-valued mapping F:ℝp ⇉ ℝq is said to be upper semicontinuous at a point x¯Rp if, for every ε > 0, there exists δ > 0 such that

F(x)F(x¯)+εB

for every x ∈ ℝp such that xx¯<δ.

Proposition 2

Let g:ℝp → ℝq be a locally Lipschitz function at [x with macron]. Then the generalized Jacobian cg(x¯) of g at [x with macron] is a first-order approximation of g at [x with macron].

Proof

Since the set-valued mapping cg( ⋅ ) is upper semicontinuous, for all ε > 0, there exists r0 > 0 such that

cg(x)cg(x¯)+εBL(Rp,Rq)for all xx¯+r0BRp.

We may assume that g is Lipschitzian in x¯+r0BRp. Let xx¯+r0BRp. We apply [17], Prop. 2.6.5, to derive that there exits c]x,x¯[ such that

g(x)g(x¯)cg(c)(xx¯)cg(x¯)(xx¯)+εBL(Rp,Rq)(xx¯).

Since

BL(Rp,Rq)(xx¯)xx¯BRq,

we have

g(x)g(x¯)cg(x¯)(xx¯)+εxx¯BRq,

which means that cg(x¯) is a first-order approximation of g at [x with macron].

Recall that a mapping f:X → Y is said to be C1,1 at [x with macron] if it is Fréchet differentiable in neighborhood of [x with macron] and if its Fréchet derivative f( ⋅ ) is Lipschitz at [x with macron].

Let x¯Rp, and let f:ℝp → ℝ be a C1,1 function at [x with macron]. The generalized Hessian matrix of f at [x with macron] was introduced and studied by Hiriart-Urruty et al. [19] is the compact nonempty convex set

H2f(x¯):=co{lim2f(xn):(xn)dom2f and xnx¯},
5

where dom∇2f is the effective domain of 2f( ⋅ ).

Corollary 1

Let x¯Rp, and f:ℝp → ℝ be a C1,1 function at [x with macron]. Then, [nabla]f admits H2f(x¯) as a first-order approximation at [x with macron].

Definition 4

[1]

We say that f:X → Y admits a second-order approximation at [x with macron] if there exit two sets Af(x¯)L(X,Y) and Bf(x¯)B(X×X,Y) such that

  • (i)
    Af(x¯) is a first-order approximation of f at [x with macron];
  • (ii)
    For all ε > 0, there exists δ > 0 such that
    f(x)f(x¯)Af(x¯)(xx¯)+Bf(x¯)(xx¯)(xx¯)+εxx¯2BY
    for all xx¯+δBX.

In this case the pair (Af(x¯),Bf(x¯)) is called a second-order approximation of f at [x with macron]. It is called a compact second-order approximation if Af(x¯) and Bf(x¯) are compacts.

Every C2 mapping f:X → Y at [x with macron] admits (f(x¯),2f(x¯)) as a second-order approximation, where f(x¯) and 2f(x¯) are, respectively, the first- and second-order Fréchet derivatives of f at [x with macron].

Proposition 3

[1]

Let f:ℝp → ℝ be a C1,1 function at [x with macron]. Then f admits (f(x¯),12H2f(x¯)) as a second-order approximation at [x with macron].

Proposition 4

Let f:X → Y be a Fréchet-differentiable mapping. If (f(x¯),Bf(x¯)) is a bounded second-order approximation of f at [x with macron]. Then f( ⋅ ) is stable at [x with macron], that is, there exist cr > 0 such that

f(x)f(x¯)cxx¯
6

for all xx¯+rBX.

To derive some results for γ-strong convex functions, the following notions are needed.

Definition 5

[8]

Let γ > 0. We say that a map f:X → ℝ ∪ { + ∞} is γ-strongly convex if there exist c ≥ 0 and g:[0, 1] → ℝ+ satisfying

g(0)=g(1)=0andlimθ0g(θ)θ=1
7

and such that

f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y)−cg(θ)∥xyγ
8

for all θ ∈ [0, 1] and xy ∈ X.

Of course, when c = 0, f is called a convex function. Otherwise, f is said γ-strongly convex. This class has been introduced by Polyak [11] when γ = 2 and g(θ) = θ(1 − θ) and studied by many authors. Recently, a characterization of γ-strongly convex functions has been shown in [8]. For example, if f is C1 and γ ≥ 1, then (8) is equivalent to

f(x),yxf(y)f(x)cγyxγ,x,yX.
9

Let f:X → ℝ ∪ { + ∞} and x¯domf:={xX,f(x)<+} (the effective domain of f). The Fenchel-subdifferential of f at [x with macron] is the set

Fenf(x¯)={xX:x,yx¯f(y)f(x¯),yX}.
10

Let γ > 0 and c > 0. The (γc)-subdifferential of f at [x with macron] is the set

(γ,c)f(x¯)={xX:x,yx¯f(y)f(x¯)cx¯yγ,yX}.
11

For more details on (γc)-subdifferential, see [8]. Note that if x ∉ domf, then (γ,c)f(x¯)=Fenf(x¯)=. Clearly, we have (γ,c)f(x¯)Fenf(x¯). Note that the Fenchel-subdifferential defined by (10) coincides with the Clarke subdifferential of f at [x with macron] if the function f is convex. We also need to recall the following definitions.

Definition 6

[20]

We say that a map f:X → ℝ ∪ { + ∞} is 2-paraconvex if there exists c > 0 such that

f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y) + cmin (θ, 1 − θ)∥xy2
12

for all θ ∈ [0, 1] and xy ∈ X.

It has been proved in [20] that if f is a C1 mapping, then (12) is equivalent to

〈∇f(x), y − x〉 ≤ f(y)−f(x) + cyx2,  ∀xy ∈ X.
13

Main results

In this section, we obtain the main results of the paper related to strongly convex functions of order γ defined by (7)-(8). We begin by showing some interesting facts of functions that admit a first-order approximation.

For any subset A of X, we define the support function of A as

s(Ax) = sup{〈xx〉, x ∈ A}.
14

It is well known that, for any convex function f: X → ℝ ∪ { + ∞}, the ‘right-hand’ directional derivative at x in domf (the domain of f ) exists and, for each h ∈ X, is

d+f(x)(h)=limt0+f(x+th)f(x)t.

Theorem 1

Let x¯X. If f:X → ℝ ∪ { + ∞} is convex and continuous at [x with macron] and if Af(x¯)X is a convex w(XX)-closed approximation of f at [x with macron], then

(γ,c)f(x¯)Af(x¯).

Proof

By the definition of Af(x¯), there exist δ > 0 and r:X → ℝ with limxx¯r(x)=0 such that, for all xx¯+δBX, t ∈ ]0, δ[, and h ∈ X, there exist AAf(x¯) and b ∈ [−1, 1] satisfying

f(x¯+th)f(x¯)thr(x¯+th)b=A,hs(Af(x¯);h).

By letting t → 0+ the directional derivative of f at [x with macron] satisfies

d+f(x¯)(h)s(Af(x¯);h),hX.
15

Using [21], Prop. 2.24, we get

s(Fenf(x¯);h)s(Af(x¯);h).

Since (γ,c)f(x¯)Fenf(x¯), we deduce that

s((γ,c)f(x¯);h)s(Af(x¯);h).

Hence we conclude that (γ,c)f(x¯)Af(x¯).

Proposition 5

Let f:X → ℝ ∪ { + ∞} be a γ-strongly convex function. Assume that Af(x¯) is a compact approximation at [x with macron]. Then Af(x¯)(γ,c)f(x¯).

Proof

Let d ∈ X be fixed and define xn:=x¯+1nd. Using Definition 1, we get, for n large enough, AnAf(x¯) and bn ∈ [−1, 1] such that

1nAn,d=f(x¯+1nd)f(x¯)1ndr(xn)bn.

By γ-strong convexity we obtain

1nAn,d1n(f(x¯+d)f(x¯))cg(1n)dγ1ndr(xn)bn.

By the compactness of Af(x¯), extracting a subsequence if necessary, we may assume that there exists AAf(x¯) such that And〉 → 〈Ad; and hence we obtain

A,df(x¯+d)f(x¯)cdγ.
16

Assume that AAf(x¯)(γ,c)f(x¯). By the separation theorem there exists h ∈ X with  ∥ h ∥  = 1 such that

minAAf(x¯)A,h>supx(γ,c)f(x¯)x,h.

Let t > 0 sufficiently small, so that

minAAf(x¯)A,h>f(x¯+th)f(x¯)t,

in contradiction with relation (16) by taking dth.

Following a result by Rademacher, which states that a locally Lipschitzian function between finite-dimensional spaces is differentiable (Lebesgue) almost everywhere, we can prove the following result.

Proposition 6

Let γ ≥ 1, x¯Rp, and let f:ℝp → ℝ be continuous at [x with macron]. Assume that f is a γ-strongly convex function. Then cf(x¯)=(γ,c)f(x¯).

Proof

Obviously, we have (γ,c)f(x¯)cf(x¯). Now let Acf(x¯). For all n, there exists xn ∈ dom∇f such that xnx¯ and f(xn) → A. Since f is γ-strongly convex and Fréchet differentiable at xn for all n ∈ ℕ, it follows by (9) that

〈∇f(xn), y − xn〉 ≤ f(y)−f(xn)−cyxnγ,  ∀y ∈ ℝp, ∀n ∈ ℕ.

Letting n →  + ∞, we get

A,yx¯f(y)f(x¯)cyx¯γ,yRp,

which means that cf(x¯)(γ,c)f(x¯).

Corollary 2

Let γ ≥ 1, x¯Rp, and let f:ℝp → ℝ be continuous at [x with macron]. Assume that f is a γ-strongly convex function. Then, for all ε > 0, there exists r > 0 such that

f(x)f(x¯)(γ,c)f(x¯)(xx¯)+εxx¯BR
17

for all xx¯+rBRp, which means that (γ,c)f(x¯) is a first-order approximation of f at [x with macron].

Proof

It is clear that cf(x¯) is a first-order approximation of at [x with macron]. We end the proof by Propositions 1 and 6.

The converse of Proposition 5 holds if (16) is valid for any A ∈ 𝒜f(x) and x ∈ X.

Proposition 7

Let γ ≥ 1 and f:X → ℝ ∪ { + ∞}. Assume that, for each x ∈ X, f admits a first-order approximation 𝒜f(x) such that 𝒜f(x) ⊂ ∂(γ,c)f(x). Then f is γ-strongly convex.

Proof

Define xθ: = θu + (1 − θ)v for θ ∈ [0, 1] and uv ∈ X. Let us take A ∈ 𝒜f(xθ). Then

Au − xθ〉 ≤ f(u)−f(xθ)−cuxθγ.

Multiplying this inequality by θ, we obtain

(a) θ(1 − θ)〈Au − v〉 ≤ θf(u)−θf(xθ)−c(1−θ)γθuvγ.

In a similar way, since

Av − xθ〉 ≤ f(v)−f(xθ)−cvxθγ

we get

(a)  − θ(1 − θ)〈Au − v〉 ≤ (1 − θ)f(v)−(1 − θ)f(xθ)−c(1 − θ)θγuvγ.

We deduce by addition of (a) and (a) that

f(xθ) ≤ θf(u) + (1 − θ)f(v)−cg(θ)∥uvγ for all uv ∈ X

where g(θ) = (1 − θ)θγ + (1−θ)γθ, so that f is γ-strongly convex.

The next results are devoted to presenting some useful properties of the generalized Hessian matrix for a C1,1 function in the finite-dimensional setting and a characterization of γ-strongly convex functions with the help of a second-order approximation.

Proposition 8

Let x¯X, and let f:X → ℝ ∪ { + ∞} be convex and Fréchet differentiable at [x with macron]. Suppose that f admits (f(x¯),Bf(x¯)) as a second-order approximation at [x with macron] and that Bf(x¯) is compact. Then there exists BBf(x¯) such that

supBBf(x¯)Bd,d0,dX.
18

If f is 2-strongly convex, then we obtain

supBBf(x¯)Bd,dcd2,dX,
19

for some c > 0.

Proof

We prove only the case where f is convex. In a similar way, we can prove the other case. Let d ∈ X and ε > 0 be fixed. We get for n large enough BnBf(x¯) and bn ∈ [−1, 1] such that

f(x¯+1nd)f(x¯)=1nf(x¯),d+1n2Bnd,d+ε1n2d2bn.

Since f is convex, we obtain

Bndd〉 + εd2bn ≥ 0.

By the compactness of Bf(x¯), extracting a subsequence if necessary, we may assume that there exits BBf(x¯) such that Bn converges to B; therefore

Bdd〉 ≥ 0, 

and hence

supBBf(x¯)Bd,d0,dX.

When X is a finite-dimensional space, we get the following essential result.

Proposition 9

Let f:ℝp → ℝ be a C1,1 function at [x with macron]. Assume that f is γ-strongly convex. Then, for any BH2f(x¯), we have the following inequality:

Bdd〉 ≥ cdγ,  ∀d ∈ ℝp
20

for some c > 0.

Proof

It is clear that (f(x¯),12H2f(x¯)) is a second-order approximation of f at [x with macron]. Now let BH2f(x¯), so that there exists a sequence (xn) ∈ dom∇2f such that xnx¯ and 2f(xn) → B. Since f is γ-strongly convex, there exists c > 0 such that

〈∇2f(xn)dd〉 ≥ cdγ,  ∀d ∈ ℝp, ∀n ∈ ℕ.

Letting n →  + ∞, we have

Bdd〉 ≥ cdγ,  ∀d ∈ ℝp.

The preceding result shows that γ-strongly convex functions enjoy a very desirable property for generalized Hessian matrices. In fact, in this case, any matrix BH2f(x¯) is invertible. The next result proves the converse of Proposition 9. Let us first recall the following characterization of l.s.c. γ-strongly convex functions.

Theorem 2

Amahroq et al. [8]

Let f: X → ℝ ∪ { + ∞} be a proper and l.s.c. function. Then f is γ-strongly convex iff cf is γ-strongly monotone, that is, there exists a positive real number c such that, for all xy ∈ X, x ∈ ∂cf(x), and y ∈ ∂cf(y), we have

x − yx − y〉 ≥ cxyγ.

We are now in position to state our main second result.

Theorem 3

Let f:ℝp → ℝ be a C1,1 function. Assume that H2f() satisfies relation (20) at any x ∈ ℝp. Then f is γ-strongly convex.

Proof

Let t ∈ [0, 1] and uv ∈ ℝp. Define φ:ℝ → ℝ as

φ(t): = f(ut(v − u)), 

so that φ(t): = 〈∇f(ut(v − u)), v − u. By the Lebourg mean value theorem [22] there exists t0 ∈ ]0, 1[ such that

φ(1)−φ(0) ∈ ∂cφ(t0).

By using calculus rules it follows that

φ(1)φ(0)cφ(t0)H2f(u+t0(vu))(vu)(vu).

Hence, there exists Bt0H2f(u+t0(vu)) such that 〈∇f(v)−∇f(u), v − u〉 = 〈Bt0(v − u), v − u. The result follows from Theorem 2.

Hiriart-Urruty et al. [19] have presented many examples of C1,1 functions. The next proposition shows another example of a C1,1 function.

Theorem 4

Let f:H → ℝ be continuous on a Hilbert space H. Suppose that f is convex (or 2-strongly convex) and thatf is 2-paraconvex. Then f is Fréchet differentiable on H, and for some c > 0, we have that

 ∥ ∇f(x)−∇f(y) ∥  ≤ c ∥ x − y ∥  for all xy ∈ H.
21

Proof

Let x0 ∈ X. Clearly, f is locally Lipschitzian at x0. Now let x1 and x2 be arbitrary elements of cf(x0) and c(−f)(x0), respectively. By [20], Thm. 3.4, there exists c > 0 such that c(−f)(x0) = ∂(2,c)(−f)(x0), and for any y ∈ H and positive real θ, we have

(a)θx2,yf(x0+θy)+f(x0)+cθ2y2

and

(a)θx1,yf(x0+θy)f(x0).

Adding (a) and (a′), we get

θx1+x2,ycθ2y2,

and hence

x1+x2,ycθy2.

Letting θ → 0, we have x1+x2,y0, so that x1=x2. Since x1 and x2 are arbitrary in cf(x0) and c(−f)(x0), it follows that cf(x0) is single-valued. Put cf(x0) = {p(x0)}. Since (a) and (a′) hold for any θ > 0 and y ∈ H, we deduce that, for θ = 1,

p(x0), y〉 ≤ f(x0y)−f(x0)

and

f(x0y)−f(x0)−〈p(x0), y〉 ≤ cy2.

Hence, for all y ≠ 0, we obtain

|f(x0+y)f(x0)p(x0),y|ycy.
22

Letting  ∥ y ∥  → 0 in (22), we conclude that f is Fréchet differentiable at x0. Now since −f is 2-paraconvex and f is Fréchet differentiable, we may prove that there exists c > 0 such that

−〈∇f(x), y − x〉 ≤ −f(y) + f(x) + cxy2 for all xy ∈ H.
23

For every z ∈ H, we have that

f(z) ≥ −f(x) + 〈∇f(x), x〉 − 〈∇f(x), z〉 − cxz2.

Thus

f(z) ≥ f(∇f(x)) − 〈∇f(x), z〉 − cxz2

so that

f(f(y))f(y),zf(z),f(f(y))f(y),z+f(f(x))f(x),zcxz2,

and hence

f(f(y))f(f(x))f(y)f(x),xf(y)f(x),zxcxz2supzH{f(y)f(x),zxcxz2}.

This means that, for all xy ∈ H,

f(f(y))f(f(x))f(y)f(x),x12cf(y)f(x)2.

Changing the roles of x and y, we obtain

f(f(x))f(f(y))f(x)f(y),y12cf(x)f(y)2.

So by addition we get

f(x)f(y),xy1cf(x)f(y)2.
24

Consequently, by the Cauchy-Schwarz inequality we obtain

 ∥ ∇f(x)−∇f(y) ∥  ≤ c ∥ x − y ∥  for all xy ∈ H.

Newton’s method

The aim of this section is to solve the Euler equation

f(x) = 0
25

by Newton’s method. The classic assumption is that f:ℝp → ℝ a C2 mapping and the Hessian matrix 2f(x) of f at x is nonsingular. Here we prove the convergence of a natural extension of Newton’s method to solve (25) assuming that f( ⋅ ) admits βf( ⋅ ) as a first-order approximation. Clearly, if f:ℝp → ℝ is a C1,1 mapping, then using Corollary 1, we obtain that f( ⋅ ) admits H2f() as a first-order approximation.

This algorithm has been proposed by Cominetti et al. [23] with C1,1 data. Only some ideas were given, but it remains as an open question to state results on rate of convergence and local convergence of that algorithm. In the sequel, f:ℝp → ℝ is a Fréchet-differentiable mapping such that its Fréchet derivative admits a first-order approximation, and [x with macron] is a solution of (25).

An external file that holds a picture, illustration, etc.
Object name is 13660_2017_1487_Figa_HTML.jpg

Theorem 5

Let f:ℝp → ℝ be a Fréchet-differentiable function, and [x with macron] be a solution of (25). Let εrK > 0 be such that f( ⋅ ) admits βf(x¯) as a first-order approximation at [x with macron] such that, for each xBRp(x¯,r), there exists an invertible element B(x) ∈ ℬf(x) satisfying  ∥ B(x)−1 ∥  ≤ K and ξ: = εK < 1. Then the sequence (xk) generated by Algorithm (ℳ) is well defined for every x0BRp(x¯,r) and converges linearly to [x with macron] with rate ξ.

Proof

Since f(x¯)=0, we have

xk+1x¯=B(xk)1(f(x¯)f(xk)+B(xk)(xkx¯)).

We inductively obtain that

xk+1x¯Kf(x¯)f(xk)+B(xk)(xkx¯).

Thus

xk+1x¯ξxkx¯,

which means that xk+1BRp(x¯,r), and we have xk+1x¯ξkx0x¯. Therefore the whole sequence (xk) is well defined and converges to [x with macron].

Now let us consider the following algorithm under less assumptions.

An external file that holds a picture, illustration, etc.
Object name is 13660_2017_1487_Figb_HTML.jpg

Theorem 6

Let U be an open set of p, x0 ∈ U, and f:ℝp → ℝ be a Fréchet-differentiable function on U. Let εrK > 0 be such that f( ⋅ ) admits βf(x0) as a strict first-order approximation at x0 such that, for each x ∈ 𝔹p(x0r), there exists a right inverse of B(x) ∈ βf(x0), denoted by B˜(x), satisfying B˜(x)()K and ξ: = εK < 1.

If  ∥ ∇f(x0) ∥  ≤ K−1(1 − ξ)r and [nabla]f is continuous, then the sequence (xk) generated by Algorithm (ℳ) is well defined and converges to a solution [x with macron] of (25). Moreover, we have xkx¯rξk for all k ∈ ℕ and x¯x0f(x0)K(1ξ)1<r.

Proof

We prove by induction that xk ∈ x0r𝔹p,  ∥ xk+1 − xk ∥  ≤ Kξk ∥ ∇f(x0) ∥ , and  ∥ ∇f(xk) ∥  ≤ ξk ∥ ∇f(x0) ∥  for all k ∈ ℕ. For k = 0, these relations are obvious. Assuming that they are valid for k < n, we get

xnx0n1k=0xk+1xkKf(x0)k=0ξkKf(x0)(1ξ)1<r.

Thus xn ∈ x0r𝔹p and since f(xn−1) + B(xn−1)(xn − xn−1) = 0, from Algorithm (ℳ) we have

f(xn)f(xn)f(xn1)B(xn1)(xnxn1)εxnxn1ξnf(x0)

and

 ∥ xn+1 − xn ∥  ≤ Kξn ∥ ∇f(x0) ∥ .

Since ξ < 1, the sequence (xn) is a Cauchy sequence and hence converges to some x¯Rp with x0x¯<r. Since [nabla]f is a continuous function, we get f(x¯)=0.

Conclusions

In this paper, we investigate the concept of first- and second-order approximations to generalize some results such as optimality conditions for a subclass of convex functions called strongly convex functions of order γ. We also present an extension of Newton’s method to solve the Euler equation under weak assumptions.

Acknowledgements

The author wishes to express his heartfelt thanks to the referees for their detailed and helpful suggestions for revising the manuscript.

Footnotes

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

The author read and approved the final manuscript.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Allali K, Amahroq T. Second order approximations and primal and dual necessary optimality conditions. Optimization. 1997;40(3):229–246. doi: 10.1080/02331939708844311. [Cross Ref]
2. Thibault L. Subdifferentials of compactly Lipschitzian vector-valued functions. Ann. Mat. Pura Appl. (4) 1980;125:157–192. doi: 10.1007/BF01789411. [Cross Ref]
3. Sweetser TH. A minimal set-valued strong derivative for set-valued Lipschitz functions. J. Optim. Theory Appl. 1977;23:539–562. doi: 10.1007/BF00933296. [Cross Ref]
4. Ioffe AD. Nonsmooth analysis: differential calculus of nondifferentiable mappings. Trans. Am. Math. Soc. 1981;266:1–56. doi: 10.1090/S0002-9947-1981-0613784-7. [Cross Ref]
5. Jourani A, Thibault L. Approximations and metric regularity in mathematical programming in Banach space. Math. Oper. Res. 1993;18(2):390–401. doi: 10.1287/moor.18.2.390. [Cross Ref]
6. Amahroq T, Gadhi N. On the regularity condition for vector programming problems. J. Glob. Optim. 2001;21(4):435–443. doi: 10.1023/A:1012748412618. [Cross Ref]
7. Amahroq T, Gadhi N. Second order optimality conditions for the extremal problem under inclusion constraints. J. Math. Anal. Appl. 2003;285(1):74–85. doi: 10.1016/S0022-247X(03)00399-8. [Cross Ref]
8. Amahroq, T, Daidai, I, Syam, A: γ-strongly convex functions, γ-strong monotonicity of their presubdifferential and γ-subdifferentiability, application to nonlinear PDE. J. Nonlinear Convex Anal. (2017, to appear)
9. Crouzeix JP, Ferland JA, Zalinescu C. α-convex sets and strong quasiconvexity. SIAM J. Control Optim. 1997;22:998–1022.
10. Lin GH, Fukushima M. Some exact penalty results for nonlinear programs and mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 2003;118:67–80. doi: 10.1023/A:1024787424532. [Cross Ref]
11. Polyak BT. Introduction to Optimization. New York: Optimization Software; 1987.
12. Rockafellar RT. Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 1976;14:877–898. doi: 10.1137/0314056. [Cross Ref]
13. Vial J-P. Strong convexity of sets and functions. J. Math. Econ. 1982;9(1-2):187–205. doi: 10.1016/0304-4068(82)90026-X. [Cross Ref]
14. Vial J-P. Strong and weak convexity of sets and functions. Math. Oper. Res. 1983;8(2):231–259. doi: 10.1287/moor.8.2.231. [Cross Ref]
15. Zălinescu C. On uniformly convex functions. J. Math. Anal. Appl. 1983;95(2):344–374. doi: 10.1016/0022-247X(83)90112-9. [Cross Ref]
16. Mordukhovich BS, Shao YH. On nonconvex subdifferential calculus in Banach spaces. J. Convex Anal. 1995;2(1-2):211–227.
17. Clarke FH. Optimization and Nonsmooth Analysis. New York: Wiley; 1983.
18. Clarke FH. On the inverse function theorem. Pac. J. Math. 1976;64(1):97–102. doi: 10.2140/pjm.1976.64.97. [Cross Ref]
19. Hiriart-Urruty J-B, Strodiot J-J, Nguyen VH. Generalized Hessian matrix and second-order optimality conditions for problems with C1,1C1,1 data. Appl. Math. Optim. 1984;11(1):43–56. doi: 10.1007/BF01442169. [Cross Ref]
20. Jourani A. Subdifferentiability and subdifferential monotonicity of γ-paraconvex functions. Control Cybern. 1996;25(4):721–737.
21. Phelps RR. Convex Functions, Monotone Operators and Differentiability. Berlin: Springer; 1989.
22. Lebourg G. Valeur moyenne pour gradient généralisé C. R. Acad. Sci. Paris. 1975;281:795–797.
23. Cominetti R, Correa R. A generalized second-order derivative in nonsmooth optimization. SIAM J. Control Optim. 1990;28(4):789–809. doi: 10.1137/0328045. [Cross Ref]

Articles from Springer Open Choice are provided here courtesy of Springer