A Class of Hybrid Projection Methods with Perturbations - Advanced Research on Computer Education, Simulation and Modeling - page 220

iteration then the next task is to find a step size α along the search direction. The

k

ideal line search rule is the exact one that satisfies

f ( x + α d ) = min f ( x + α d ) . (1.4)

k k k k k

α > 0

In fact, the exact step size is difficult or even impossible to seek in practical
computation, and thus many researchers constructed some inexact line search rules,
such as Armijo rule, Goldstein rule, Wolfe rule and nonmonotone line search
rules(see [1,4,7]).
Since Grippo, Lampariello and Lucidi proposed the nonmonotone line search rule
for Newton methods, the new line search approach has been studied by many authors
(e.g. [2-4]). Although it has many advantages, especially in the case of iterates
trapped in a narrow curved valley of objective functions, the nonmonotone line search
rule has some drawbacks(see [6]). Therefore, Shi and Shen proposed a new
nonmonotone line search for general line search method, which is described as
follows.
New nonmonotone line search (NNLS): Let M be a nonnegative integer. For each
k , let

m ( k ) satisfy

m ( 0 ) = 0 0 ≤ m ( k ) ≤ min[ k − 1 M ], ∀ k ≥ 1 . (1.5)

1

β ∈ ( 0 , ), σ ∈ ( 0 , )

B is a symmetric positive definite

Given and δ ∈ [ 0 5 , 2 ) ,

2

x and

matrix that approximates the Hessian of

f ( x ) at the iterate

δ

g

T
k

d

s

= − .

k

k

d

T
k

B d

k k

{ }

Choose α to be the largest in

s

,

s

β ,

s

β , such that

2

K

α

k k k k

1

f

(

x

+

d

) − max

f

≤ [

g d

+

d B d

]

α σα

T
k

α

T
k

. (1.6)

k k k − j k

2

k k

0 ≤ j ≤ m ( k )

The new line search is a novel scheme of the nonmonotone Armijo line search and
allows one to find a larger accepted step size and possibly reduces the function
evaluations at each iteration.
In this paper, we propose a kind of hybrid projection method with perturbations
(see Algorithm 2.1). In the algorithm, we employ the new nonmonotone line search
technique. We prove the iteration sequence

{}

k x generated by the algorithm satisfies

either

f

→ −∞ or

f converges to finite value and

g

→ 0 only in the case where

k k

( xg is uniformly continuous on an open convex set containing the iteration
sequence

)

{}

k x . In doing so, we remove various boundedness conditions such as
boundedness from below of f ( ⋅ ) , boundedness of

x , etc.