【信赖域法】
拼译：trust region methods
一类很新的求解非线性规划问题的计算方法。它和经典的线性搜索方法并列为目前求解非线性规划问题的两类主要数值方法。信赖域法思想新颖，算法可靠，具有很强的收敛性质。它不仅能很快地求解良态问题，而且也能有效地求解病态(ill-coditoned)的优化问题。信赖域法的研究是近年来非线性规划的领域的一个重要研究方向，是当今寻求如何构造新的优化计算方法的主要途径。
信赖域法起源于鲍尔(M．J．D．Powell)1970年的工作。他提出一个求解无约束优化的算法，该算法在每次迭代时强制性地要求新的迭代点与当前迭代点之间的距离不超过某一控制量。鲍尔引入控制步长这一技巧，是因为他发现传统的线搜索方法常常由于线搜索步太大而导致算法失败，特别是当问题病态(ill conditioned)时尤为如此。控制步长实质上等价于在当前迭代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。这种技巧可以理解为我们只在一邻域内对近似模型信赖(trust)，所以这一邻域被称为信赖域(trust regiion)。利用这一技巧的方法也就称为信赖域法。后来，人们发现控制步长在模型问题是二次函数时等价于对模型函数的海色阵增加一个纯量阵(scalar matrix)，后者在利温伯格(K．Levenberg)1944年以及马夸尔特(D．W．Marquardt)1963年的求解非线性最小二乘方法中就已被用到。1975年鲍尔给出了信赖域法的第一个收敛性结果。他在仅假定函数连续可微近似海色阵满足
的条件下证明了无约束优化的信赖域法的全局收敛性。鲍尔还给出了一个超线性收敛性定理。1984年鲍尔将要求收敛的条件放松到‖Bk‖≤ck。鲍尔证明的收敛性结果都是弱收敛意义下的，即
。这种弱收敛结果在实际计算中对于保证算法有限终止是足够的。在稍强的假定下，舒尔茨(G．A．Shultz)、许纳博(R．B．Schnabel)和伯德(R．H．Byrd)证明了无约束优化的信赖域法在强收敛意义下的全局收敛性。1982年弗莱彻(R．Fletcher)提出了用信赖域法来求解复合非光滑优化(composite nondifferentiable optimization)问题。他给出了一个模型算法，并在模型二次函数的海色阵一致有界的假定下证明了该算法的全局收敛性。1985年袁亚湘(Y．Yuan)在仅要求近似海色阵满足‖Bk‖≤ck的假定下证明了一类非光滑优化的信赖域法的全局收敛。1984年袁亚湘构造出一个极大极小问题，指出了一类非光滑优化的信赖域法仅有线性收敛速度。造成这种线性收敛的原因是在每次迭代时函数的真实下降与预估下降之比都小于
。这个比值不靠近1，使得算法错误地认为点到还未收敛，故缩小信赖域半径，导致信赖域约束在每次迭代都是积极的，因而破坏了算法的超线性收敛性。1982年弗莱彻提出了一个二阶校正步(second order correction step)信赖域法。二阶校正步法基本上和弗莱彻的模型信赖域法一样，只是在一些迭代中求解一个二阶校正子问题。1985年袁亚湘证明了对于包括极大极小在内的一类复合非光滑优化问题，如果拉格朗日(Lagrange)乘子的估计较好，则弗莱彻的二阶校正步法是二次收敛的。后来，柏克(J．V．Burke)将袁亚湘的结果推广到一般的复合非光滑优化。信赖域方法应用到约束优化的一个明显困难，是线性化的约束条件在信赖域内可能无解，于是不可能像线搜索方法那样在线性化约束条件的可行域内找新的迭代点。对这一困难目前主要有两种处理办法。第1种是将线性化约束条件中的约束函数值项都乘上一个属于［0，1］的乘子，它实际上是将每个线性化约束的可行域向当前迭代点平移。这种技巧在线搜索方法逐步二次规划方法(SQP)中已被用来处理线性化约束无解的情形。利用这一技巧的信赖域法有1985年瓦蒂(A．Vardi)提出的方法以及1987年伯德等人提出的方法。第2种办法是将所有线性化约束之误差的平方和当作一个约束，使得该平方和不超过某一容许量。这种技巧于1985年由西莉斯(M．R．Celis)、丹尼斯(J．E．Dennis)和塔皮亚(R．A．Tapia)提出。1991年鲍尔和袁亚湘所提出的信赖域法也采用了该技巧。约束优化信赖域法的另一个重要因素是价值函数(Merit function)的选取。价值函数是用来判别一个试探点是否可以接受的，它通常是某种形式的罚函数。在瓦蒂方法、伯德－许纳博－舒尔茨方法、和西莉斯－丹尼斯－塔皮亚方法等中，价值函数是L1精确罚函数。利用L1精确罚函数的优点在于比较容易证明算法的全局收敛性。但是由于L1精确罚函数是非光滑的，马洛托斯(N．Maratos)效应可能发生，故算法不可能保证超线性收敛。为此，伯德等人在1987年提出的算法中当试探步不能被接受对就计算一个二阶较正步，这样就保证了算法的总体收敛性。1991年，鲍尔和袁亚湘在他们的算法中用弗莱彻的光滑精确罚函数作为价值函数。利用光滑罚函数的优点是马洛托斯效应不可能出现，从而比较容易得到超线性收敛结果。美中不足的是，计算该罚函数的导数时需要目标函数和约束函数的二阶导数。所以，鲍尔和袁亚湘提出了一种特殊的价值函数预估下降量的近似计算法，避免了计算任何二阶导数且保证了算法的收敛性和超线性收敛性。在西莉斯－丹尼斯－塔皮亚方法和鲍尔－袁亚湘方法中，每次迭代需要求解的子问题是在二个凸的二次约束下求一个二次函数的极小。袁亚湘1990年对该子问题进行了深入的研究，证明了在一定条件下该子问题的拉格朗日函数的海色阵最多只有一个负特征值。1991年袁亚湘给了一个求解凸的子问题的算法，该算法是基于对偶问题，利用了投影牛顿步。这个算法具有超线性收敛性，但缺点是不适合求解非凸问题。1992年张寅提出另一个求解凸子问题的算法，该算法采用变量代换，把子问题化成一个等价的一维优化问题，然后求解。目前，对于一般非凸的子问题还没有好的求解方法，是有待解决的重要问题。1991年，诺塞达尔(J．Nocedal)和袁亚湘提出了将信赖域法和线搜索方法相结合的思想，并依此给出了一个利用信赖域以及回溯(back-tracking)技巧的求解无约束优化的算法。这是综合两大类算法之优点的一个有益的探讨，但该方面的工作有待进一步深入。信赖域法是非线性规划的一个较新的方向，它将吸引更多的优化工作者，信赖域法的研究热点将主要是寻求有效的求解约束优化问题的信赖域法，特别是能较好地处理不等式约束问题的算法；对已有的信赖域子问题提供好的计算方法；构造新的信赖域子问题；探讨信赖域法在其它优化分支如线性规划等中的应用；以及进一步深入将信赖域与线搜索相结合的研究等。【参考文献】：1 Powell M J D. Numerical Methods for Nonlinear Algebraic Equations. London:Gordon and Breach Science,1970, 87～ 1442 Powell M J D. Nonlinear Programming 2. New York; Aca-demicPress, 1975,1～273 Fletcher R. Math. Prog Study, 1982,17:67～764. Fletcher R. Numerical Analysis Berlin: Springer - Verlag, 1982,85～1155 Powell M J D. Math Prog,1984,29,297 ～ 3036 Yuan Y.Math Prog,1985,31,269～2857 Vardi A. SiAM J Numer Anal,1985,22:575 ～5918 Celis M R, et al. Numerical Optimization SiAM. Philadel-phia,1985,71～829 ByrdR, et al. SIAM J. Numer Anal,1987,24:1152～117010 Yuan Y.Math. Prog,1990,47:53～63(中国科学院计算数学所袁亚湘研究员撰)