摘 要

最优化理论与算法是数学学科中一个重要的分支，所研究的问题是在众多问题的解决方案中，讨论出一个最好的解决方案以及如何去寻找这类方案，从而最终得到一个解决问题的最优方案，并且最优化理论在工业、商业和军工等领域都得到了比较广泛的应用。而在最优化问题的求解方案中，信赖域算法因为具有很强的收敛性和自适应性,所以受到了非线性优化研究者们的极大重视。尤其是与单调的信赖域算法相比较，非单调的信赖域算法不仅减少了计算子问题的次数，而且避免了Maratos效应，在实际应用中具有非常重要的作用。

本论文着重研究解决非线性优化问题的非单调信赖域算法，针对基本信赖域算法中的实际下降量进行调整，增加一个趋近于1的参数，放宽对信赖域半径的校正条件，得到一种新的非单调信赖域算法。所提出的新算法可以达到放大信赖域半径的目的，即尽可能挣脱局部最优解的“牢笼”，使算法搜索到的局部最优解成为全局最优解。最终，理论证明该算法在适当条件下的全局收敛性，并且采用Matlab进行数值验证该算法的可行性与有效性。

关键词：最优化理论；非单调算法；新的信赖域算法；全局收敛性

Abstract

Optimization theory and algorithm is a mathematical discipline an important branch. The problem is studied in solution of many problems, discuss the best solution and how to find such solutions. Finally, get a solution to the problem of the optimal solution. Optimization theory in the field of engineering, physics, economics and management has been used widely. Because of strong convergence and adaptability, the trust region algorithm attracts the attention of nonlinear optimization researchers. Especially non-monotonic trust region algorithm, compared with the trust region algorithm for reducing the number of sub-problem calculation to avoid Maratos effect, plays an important role in practical applications.

The contents of this working paper focuses on the non-monotonic trust region algorithm for nonlinear optimization problems. Correcting the basic trust region algorithm actually decrease the amount of,relax the trust region radius correction condition, to achieve the purpose of the trust region radiusenlarge. That might jump out of ‘the cage’ local optima, optimal solution to make the search as much as possible to become a global optimal solution, thus proposes a new trust region algorithm. Finally, proving the global convergence of the algorithm with appropriate conditions, and using matlab numerical shows that the algorithm is feasible and effective.

Keywords：Optimization theory; non-monotonic algorithm; a new trust region algorithm; global convergence.

摘 要 3

第1章 绪论 1

1.1 线搜索方法 1

1.2 信赖域方法 2

1.2.1　信赖域方法的基本思想 2

1.2.2　信赖域方法的基本结构 2

1.3 信赖域方法国内外研究现状 4

1.4 非单调信赖域算法 5

1.5 本文主要研究内容 5

第2章 新的非单调信赖域方法 7

2.1 新的非单调信赖域算法 7

2.2 新算法的MATLAB数值实现 8

2.3 新算法的全局收敛性证明 9

结论 13

参考文献 14

致 谢 15

第1章 绪论

一般来说，最优化问题是求解如下极小值问题：

(1-1)

其中，目标函数是定义在集合D上的实值函数，D是问题中变量x的取值集合，也称为最优化问题的可行域。

最优化问题可分为连续最优化问题和离散最优化问题，其中连续最优化问题又分为目标函数、约束函数都是线性时的线性最优化问题和目标函数或约束函数至少有一个是非线性的非线性最优化问题。我们这里主要研究的是D=Rⁿ的无约束优化问题：

(1-2)

其中 是上的二次连续可微且有下界的实值函数。

关于这类问题的解法，人们经常使用的求解方法是线搜索方法和信赖域算法这两种。两类求解方法各有其优点和缺点，线搜索方法易于求得新的迭代点，收敛性一般，与线搜索方法相比较，信赖域算法具有更强的收敛性，同样，对于病态问题也能得到更加有效的解决，并且经过Matlab的数值实验，发现所需的迭代次数相较之也更少，但是算法也有比较大的缺陷，因为子问题的求解过程较长，如果每次都要求解新的迭代点，对于算法的效率消耗极大。通过阅读前人所提出的各种方法，为充分发挥这两种方法的优势，我们可以试着将这两种算法结合起来构造一个新的求解方法，本文所做的工作就是基于这种方法提出的一种新的非单调信赖域算法。

1.1 线搜索方法

线搜索方法是解决最优化非线性优化问题的一种比较传统的方法，简单可靠，它的基本思想是在第次进行迭代的时候，产生一个新的搜索方向，之后顺着这个搜索方向产生精确的或者非精确的搜索，得到步长，并且求出下一个迭代点为，直到得到最优解，通常所选取的搜索方向也一般就是使目标函数下降的方向。人们常用的产生搜索方向的方法有：拟牛顿法，共轭梯度法，最快速下降法，牛顿法等^[1]，精确线搜索采用的是最优步长规则，但是这是一种理想化的搜索策略，于是人们常用不精确线搜索步长规则：步长规则、步长规则和步长规则等。

1.2 信赖域方法

信赖域方法与线搜索方法相似，都是优化问题求解方法中可以保持全局收敛性的重要方法。它们都是需要在算法中求出每次迭代所产生的搜索方向和步长，从而得到一个新的迭代点直至求出最优解。有一点不同的是得到新的迭代点的方法不同：线搜索方法是先产生搜索方向，再确定搜索步长，然后得到新的迭代点；而信赖域方法是在迭代点附近产生信赖区域，并且建立一个与目标函数近似的二次模型，最终基于近似二次模型在该信赖域内的最优解产生新的迭代点。

1.2.1　信赖域方法的基本思想

首先给出一个初始信赖域半径作为算法中位移长度的初始上界，并以初始迭代点为中心，此上界为半径得到一个信赖域，即一个圆的封闭光滑区域。然后，我们求解这个信赖区域内的子问题（即目标函数的二次近似模型）的最优点来得到一个满意的位移。

假设得到的这个位移可以让目标函数值能够有很强的下降量，并且比较令人满意，则可以考虑接受该位移作为我们新的位移，然后保持或增大信赖域半径，继续下一次的迭代，不然，表明该二次模型和目标函数的近似度不是很理想，这样我们就要考虑减小信赖域半径，然后在求出新的信赖域内的子问题的解之后得到一个新的位移。如果未满足迭代的终止条件，则这些步骤一直循环下去，直至满足。

1.2.2　信赖域方法的基本结构

这里我们可以先给出使用信赖域方法求解问题（1-2）的基本算法结构。设是第k次迭代点。记，是海赛矩阵的第k次近似，则第k次迭代步的信赖域子问题具有如下形式：