无约束优化问题的修正拟牛顿非单调信赖域算法研究

【作者】 杨洁；

【导师】 焦宝聪；

【作者基本信息】 首都师范大学 ， 应用数学， 2009， 硕士

【摘要】 信赖域方法是非线性优化的一类重要的数值计算方法.它在近二十年来受到非线性优化领域许多研究者的关注,是非线性优化的研究热点.与线搜索相比,信赖域有两个突出的优点:一是它有很强的稳定性和强适性,二是它具有很强的收敛性.由于信赖域的有界性,它可以处理非凸的近似模型.目前,信赖域方法已经和传统的线搜索方法并列为求解非线性规划问题的两类主要数值方法[1],与线性搜索方法相比,信赖域算法不仅具有很强的收敛性[2],而且对于病态问题也能有效地解决,需要的迭代次数少,但由于求解子问题花费代价高,往往不易求解新的迭代点;而线性搜索方法易于求得新的迭代点.为充分发挥两种方法的优势,1991年,Jorge Nocedal和袁亚湘[3]提出将信赖域算法和线性搜索方法相结合来构造新计算方法的思想,在文[25]中,采用回溯(backtracking)线搜索,优点是不需重解子问题,大大减少了计算量,但为了保证序列{B_k}的正定性,却使得一些B_k未能满足拟牛顿方程,这样做往往使B_k逼近(?)~2f(x_k)的效果不佳,从而信赖域子问题不能很好地逼近原问题.在文[5]中E.MichaelGertz提出了一种新的带线搜索的信赖域方法,它不仅继承了文[25]中方法不需重解子问题的优点,而且由于在每步都采用Wolfe线搜索,使得序列{B_k}满足拟牛顿方程且保证其正定性,充分开发了拟牛顿校正公式的性质,克服了文[25]中方法的缺点.本文主要研究应用修正拟牛顿方程的非单调信赖域方法.因为,在实际计算中,对于某些问题单调算法并不能保证算法的有效性. 1986年, Grippo等人[6,7]提出了一种非单调线搜索,并将此技术分别运用到Newton法和截Newton法中1993年,邓乃扬等人[8]首次将非单调技术应用到信赖域方法中,在一定条件下证明了其全局收敛性和超线性收敛性,数值试验表明对某些问题,非单调信赖域方法比相应的单调算法有更好的数值结果.以上提到的非单调技术都是以(?)为参考函数值来实现的,其中m(0)=0, 0≤m(k)≤min[m(k-1)+1,M], M是给定的正整数.鉴于以上工作的基础上,本文提出了两类新的非单调信赖域方法.第一章,我们首先介绍了最优化问题的研究背景和现状,以及信赖域子问题的求解方法.其次回顾求解无约束最优化问题的主要非精确线性搜索方法.第二章,我们提出了一类新拟牛顿非单调信赖域方法.采用加权的r_k用以调整信赖域半径,在适当的条件下,证明了此算法的全局收敛性.数值结果表明该算法的有效性.第三章,我们提出了一类带线搜索的修正拟牛顿非单调信赖域算法.不同于传统的非单调信赖域算法,此算法在每步都采用非单调Wolfe线搜索得到下一个迭代点.这样得到的新算法不仅不需要重复求解子问题,而且由于应用基于修正拟牛顿方程的校正,可以得到逼近Hessian阵精度更高的B_k.在适当的条件下,证明了该算法的全局收敛性.数值试验证实该算法是有效的.更多还原

【Abstract】 Trust region method is one of the important numerical computational methods in conlinear optimization. It has been paid so much attention by many researchers in the field of nonlinear optimization. Compared with line search method, TR method has two outstanding advantages: one is it has very strong stability and robustness; the other is its strong convergence. Because of the boundness of trust region. it can deal with nonconvex models. So far. TR method enlists in one of the two major numerical options for solving nonlinear optimization [1].Compared with line search method, TR method not only has strong convergence [2], but can solve bad-scaled problems efficiently with less iteration numbers. However, because it is difficult to solve the subproblem. the new iterative point is hard to obtain by using TR method, while line search method is easier to obtain the new point. As a result, in order to make good use of the advantages of both methods. Jorge Nocedal and Yuan Yaxiang [3] proposed an idea of combining TR method and line search method in 1991. In paper [25]. with backtracking line search and no need to resolve the subprobleni of TR method. the computational amount is greatly reduced. But in order to maitain the positive definiteness of B_k, causing some B_k do not perfectly match （?）²f（x_k）. and then the subproblem of TR method does not match the original problem accordingly. In paper [5], E.Micheal Gertz propesed a new TR method with line search method. It not only no need to resolve the subproblem, but since using Wolfe line search at every iteration, B_k satisfies the quasi-Newton equation and maitains the positive definiteness. It fully developped the propertises of quasi-Newton formular and avoided the disadvantages of paper [25].In this paper, we mainly study the nonmonotonic TR method based on modified quasi-Newton equations. Since in real computations, the monotonic algorithms can not guarantee the validity of some problems, In 1986. Grippo，etc [6,7] lay out a nonmonotone line search technique, and applied it to Newton method and cutted Newton method. In 1993, Deng Naiyang and others [8] firstly applied nonmonotonic technique to trust region method and proved its global and superlinear convergence under suitable conditions. Numerical experiments showed that the nonmonotonic trust region method was superior to the corresponding monotonic method for some problems. The nonmonotonic techniquementioned above is realized by f_? = （?） f(x_k-j), where m（0） = 0,0≤m（k）≤min[m（k-1）+1,M],M is the given positive integer. Based on the proceeding work, we propese two kinds of new nonmonotonic TR algorithms.In chapter 1, we firstly give a brief introduction of the background and current situation of Optimization, and methods to solve TR subproblem. THen, we review the major nonexact line search methods for unconstrained optimization.In chapter 2, we propose a new quasi-Newton nonmonotonictrust region algorithm. We adjust the trust radius using not only （?）. but also the previous ratios {r_k-m…,r_k}, where m is some positive integer. Under proper assumptions. we prove the global convergence of the algorithm and numerical experiments show the algorithm is competitive.In chapter 3, we present a modified quasi-Newton nonmonotonic trust region algorithm with Wolfe line search. Unlike traditonal nonmonotonic trust region algorithms, our algorithm gets the next point by the nonmonotonic Wolfe line search at each iteration. This new algorithm not only does not resolve the sub-problem but also satisfies the modified quasi-Newton condition at each iteration and simultaneously maintains a positive-definite approximation to the Hessian of the objective function. Under mild conditions, we prove the global convergence and numerical results show its efficiency.更多还原