A Non-Monotone Trust Region Method with Non-Monotone Wolfe-Type Line Search Strategy for Unconstrained Optimization

Changyuan Li^*, Qinghua Zhou^*, Xiao Wu

College of Mathematics and Information Science, Hebei University, Baoding, China.

DOI: 10.4236/jamp.2015.36084                

Abstract

In this paper, we propose and analyze a non-monotone trust region method with non-monotone line search strategy for unconstrained optimization problems. Unlike the traditional non-monotone trust region method, our algorithm utilizes non-monotone Wolfe line search to get the next point if a trial step is not adopted. Thus, it can reduce the number of solving sub-problems. Theoretical analysis shows that the new proposed method has a global convergence under some mild conditions.

Keywords

Unconstrained Optimization, Non-Monotone Trust Region Method, Non-Monotone Line Search, Global Convergence

1. Introduction

Consider the following unconstrained optimization problem:

(1)

where is a twice continuously differentiable function. Throughout this paper, we use the following notation:

・ is the Euclidean norm.

・ and are the gradient and Hessian matrix of f evaluated at x, respectively.

・ , , and is a symmetric matrix which is either or an approximation of.

For solving (1), trust region methods usually compute by solving the quadratic sub-problem:

(2)

where is a trust region radius. Some criteria are used to determine whether a trial step is accepted. If not, the sub-problem (2) may be computed several times at one iterate until an acceptable step is found. There is no doubt that the repetitive process will increase the cost of solving the problem.

To improve the performance of the algorithm, Nocedal and Yuan [1] put forward an algorithm which combine trust region algorithm and line search method for the first time in 1998, then Gertz [2] proposed a new trust region algorithm that use Wolfe line search at each iteration to obtain a new iteration point regardless of whether is accepted. Both of them improved the computational efficiency by fully using the advantages of two kinds of algorithm.

Algorithms mentioned above are monotonic algorithm. In 1982, Chamberlain et al. in [3] proposed the watchdog technique for constrained optimization to overcome the Maratos effect. Motivated by this idea, Grippo et al. first introduced a non-monotone line search technique for Newton’s method in [4] . In 1993, Deng et al. [5] proposed a non-monotone trust region algorithm in which they combined non-monotone term and trust region method for the first time. Due to the high efficiency of non-monotone techniques, many authors are interested in working on the non-monotone techniques for unconstrained optimization problem [6] - [15] . Especially, some researchers have combined non-monotone trust region method with non-monotone Armijo-type line search method and good numerical results have been achieved [16] [17] . Besides, Zhang and Hager [18] proposed a non-monotone Wolfe-type condition. Inspired by [16] - [18] , we present a non-monotone trust region algorithm with non-monotone Wolfe-type line search strategy. To be specific, the algorithm first solve sub-problem (2) to compute the trial step, if the trial step is accepted, set. Otherwise, the algorithm performs the non-monotone Wolfe-type line search strategy to find an iterative point instead of resolving the sub-prob- lem.

2. Non-Monotone Term and Wolfe-Type Line Search Condition

The general non-monotone form is as follows:

(3)

where, and is an integer constant. Actually, the most common non-monotone ratio is defined as follows:

.

Some researchers showed that utilizing non-monotone techniques may improve both the possibility of finding the global optimum and the rate of convergence [4] [18] . However, although the non-monotone technique has many advantages, it contains some drawbacks [11] [17] [18] . To overcome those disadvantages, Ahookhosh et al. in [11] proposed a new non-monotone technique to replace (3). They define

(4)

where, and. At the same time, they have the new non-monotone ratio:

(5)

In 2004, Zhang and Hager [18] presented a modified non-monotone Wolfe-type condition. In order to keep the consistency of non-monotone term and simplify the form of Wolfe-type condition, we define the new modified non-monotone Wolfe-type condition as follows:

(6)

(7)

The rest of this paper is organized as follows. In Section 3, we introduce the algorithm of non-monotone trust region method with line search strategy. In Section 4, we analyze the new method and prove the global convergence. Some conclusions are given in Section 5.

3. New Algorithm

In this paper, we consider the following assumptions that will be used to analyze the convergence properties of the below algorithm:

(H1) The level set, where is a closed, bounded set.

(H2) The matrix is a uniformly bounded matrix, i.e. there exists a constant such that for all k.

(H3) is a Lipschitz continuous function, i.e. there exists a constant such that .

(H4) has the upper bound.

The new algorithm can be described as follows:

Algorithm 0

Step 1 An initial point and a symmetric positive definite matrix are given. The constants, , , , , , and are also given. Compute and set.

Step 2 Compute. If then stop, else go to Step 3.

Step 3 Similar to [1] , solve (2) inaccurately to determine, satisfying

(8)

(9)

Step 4 Compute, , and. If, go to Step 5. Otherwise, find the step-length satisfying (6) and (7), then set and update, go to step 6.

Step 5 Set, and

.

Step 6 Update the symmetric matrix by a quasi-Newton formula, set, go to step 2.

4. Convergence Analysis

For the convenience of expression, we Let and. Obviously, is an infinite subset of the set.

We need the following lemmas in order to prove the convergence of the new algorithm.

Lemma 1 Assume that Algorithm 0 generates an infinite sequence, (H2), (H3) and (H4) hold, and there is a such that. Then for all, there exists a constant such that.

Proof. From (7) and (H3), we have

. (10)

Thus, we can conclude that

. (11)

This inequality, together with (H2), (H4) and (9), lead us to have

. (12)

Let, we complete the proof.

Lemma 2 (See Lemma 2.1 and Corollary 3.1 in [17] ) Suppose that the sequence is generated by Algorithm 0. Then, we have, is a decreasing sequence and

(13)

Lemma 3 Suppose that (H1) holds, if sequence does not converge to a stationary point, i.e. there exists a constant such that. Then

(14)

where

Proof. We consider two cases:

Case 1.. The proof is similar to Lemma 3.3 in [17] , we can obtain that

.

Case 2.. From (6), (9) and (12), we have

where.

Let, we can conclude

. (15)

Considering Lemma 2 and (15), we get (14).

Lemma 4 Suppose that all conditions of Lemmma 1 and Lemma 3 hold. Then for all sufficiently large k, we have

. (16)

Proof. The proof is similar to Lemma 3.6 and 3.7 in [16] , we omit it for convenience.

Lemma 5 Suppose that (H2) and (H3) hold, if there exists a constant such that, then for a sufficiently large integer, we have.

Proof. Assume that for, (16) holds. Using the fact and (15), we obtain

.

Then, the monotonicity of imply that

Thus, for we have

Using Lemma 2, we get

.

This inequality and the fact that is convergent (see [4] ) show

.

Therefore,. Then we have.

Theorem 6 Suppose that (H1)-(H4) hold, then sequence generated by Algorithm 0 satisfies

. (17)

Proof. Assume that (17) does not hold, then there exists a constant such that. From (H2) and the definition of, we have

.

Obviously, this contradicts Lemma 5. The proof is completed.

5. Conclusion

In this paper, we introduce the algorithm of non-monotone trust region method with non-monotone Wolfe-type line search strategy for unconstrained optimization problems based on (5), (6) and (7). When compared with (3), it is obviously that we fully employ the current objective function value and we can derive the better convergence results by choosing an adaptive. Besides, with the help of line search strategy, new algorithm can reduce the number of solving sub-problems. We analyzed the properties of the algorithm and proved the global convergence theory under some mild conditions.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (61473111) and the Natural Science Foundation of Hebei Province (Grant No. A2014201003, A2014201100).

NOTES

^*Corresponding authors.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Nocedal, J. and Yuan, Y.X. (1998) Combining Trust Region and Line Search Techniques. In: Yuan, Y., Ed., Advanced in Nonlinear Programming, Kluwer Academic Publishers, Dordrecht, 153-175. http://dx.doi.org/10.1007/978-1-4613-3335-7_7
[2]	Michael Gertz, E. (2004) A Quasi-Newton Trust Region Method. Mathematical Programming, 100, 447-470. http://dx.doi.org/10.1007/s10107-004-0511-1
[3]	Chamberlain, R.M. and Powell, M.J.D. (1982) The Watchdog Technique for Forcing Convergence in Algorithm for Constrained Optimization. Mathematical Programming Study, 16, 1-17. http://dx.doi.org/10.1007/BFb0120945
[4]	Grippo, L., Lampariello, F. and Lucidi, S. (1986) A Nonmonotone Line Search Technique for Newton’s Method. Society for Industrial and Applied Mathematics, 23, 707-716.
[5]	Deng, N.Y., Xiao, Y. and Zhou, F.J. (1993) Nonmonotone Trust Region Algorithm. Journal of Optimization Theory and Application, 76, 259-285. http://dx.doi.org/10.1007/BF00939608
[6]	Toint, Ph.L. (1996) An Assessment of Nonmonotone Linesearch Technique for Unconstrained Optimization. Society for Industrial and Applied Mathematics, 17, 725-739.
[7]	Toint, Ph.L. (1997) Non-Monotone Trust-Region Algorithm for Nonlinear Optimization Subject to Convex Constraints. Mathmatical Programming, 77, 69-94. http://dx.doi.org/10.1007/BF02614518
[8]	Sun, W.Y. (2004) Nonmonotone Trust Region Method for Solving Optimization Problems. Applied Mathematics and Computation, 156, 159-174. http://dx.doi.org/10.1016/j.amc.2003.07.008
[9]	Mo, J.T., Zhang, K.C. and Wei, Z.X. (2005) A Nonmonotone Trust Region Method for Unconstrained Optimization. Applied Mathematics and Computation, 171, 371-384. http://dx.doi.org/10.1016/j.amc.2005.01.048
[10]	Mo, J.T., Liu, C.Y. and Yan, S.C. (2007) A Nonmonotone Trust Region Method Based on Nonincreasing Technique of Weighted Average of the Successive Function Values. Journal of Computational and Applied Mathematics, 209, 97-108. http://dx.doi.org/10.1016/j.cam.2006.10.070
[11]	Ahookhosh, M. and Amini, K. (2012) An Efficient Nonmonotone Trust-Region Method for Unconstrained Optimization. Numerical Algorithms, 59, 523-540. http://dx.doi.org/10.1007/s11075-011-9502-5
[12]	Ahookhosh, M., Amini, K. and Bahrami, S. (2012) A Class of Nonmonotone Armijo-Type Line Search Method for Unconstrained Optimization. Optimization, 61, 387-404. http://dx.doi.org/10.1080/02331934.2011.641126
[13]	Zhou, Q.Y., Chen, J. and Xie, Z.W. (2014) A Nonmonotone Trust Region Method Based on Simple Quadratic Models. Journal of Computational and Applied Mathematics, 272, 107-115. http://dx.doi.org/10.1016/j.cam.2014.04.026
[14]	Huang, S., Wan, Z. and Chen, X.H. (2015) A New Nonmonotone Line Search Technique for Unconstrained Optimization. Numerical Algorithms, 68, 671-689. http://dx.doi.org/10.1007/s11075-014-9866-4
[15]	Zhou, Q.Y. and Hang, D. (2015) Nonmonotone Adaptive Trust Region Method with Line Search Based on New Diagonal Updating. Applied Numerical Mathematics, 91, 75-88. http://dx.doi.org/10.1016/j.apnum.2014.12.009
[16]	Gu, N.Z. and Mo, J.T. (2008) Incorporating Nonmonotone Strategies into the Trust Region for Unconstrained Optimization. Computers and Mathematics with Applications, 55, 2158-2172. http://dx.doi.org/10.1016/j.camwa.2007.08.038
[17]	Ahookhosh, M., Amini, K. and Peyghami, M.R. (2012) A Nonmonotone Trust-Region Line Search Method for Large-Scale Unconstrained Optimization. Applied Mathematical Modelling, 36, 478-487. http://dx.doi.org/10.1016/j.apm.2011.07.021
[18]	Zhang, H.C. and Hager, W.W. (2004) A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization. SIAM Journal on Optimization, 14, 1043-1056. http://dx.doi.org/10.1137/S1052623403428208