英语原文共 33 页，剩余内容已隐藏，支付完成后下载完整资料
信赖域方法的研究现状
袁亚湘1
收稿日期：2014年9月29日/接受：2015年2月17日/在线发表时间：2015年3月15日
copy;施普林格出版社柏林海德堡和数学优化协会2015年
摘要：信赖域方法是一类最优化数值方法。其中，每次迭代进行搜索的方法是根据不同的步长，信赖域方法的计算是通过求解信赖域子问题的一个试探步为信赖域半径的区域内的最小值。由于信赖域的约束，可以将非凸模型使用在信赖域子问题上，并且信赖域算法可以应用到非凸和病态问题中。通常信赖域算法比相应的线搜索方法更容易全局收敛。在论文中，我们回顾了信赖域方法的最新成果：无约束最优化，约束最优化，线性与非线性最小二乘问题，不连续的非光滑优化和优化。最后对信任域子问题和正规化方法进行了讨论。
关键词：信赖域算法；非线性优化；子问题；复杂度；拟合；
数学主题分类 65K05·90C30
- 引言
信赖域算法是一类研究了几十年的最优化数值方法。信赖域法的历史发展可以追溯到Levenberg 修改的高斯 - 牛顿方法求解非线性最小二乘 问题。Levenberg的方法是由Morrison和Marquita重新发现的。由于方法被推广到Marquardt的论文，因此，它被称为Levenberg-Marquardt方法。因为它被刊登在会刊，而不是杂志，所以Morrison的文章不是众所周知的，但由于许多权威专家的青睐，于是将其命名为“Levenberg–Morrison–Marquadt”法作为对Morrison[80]的重要贡献的肯定。 Levenberg-Marquardt方法是通过增加阻尼系数来修改高斯 - 牛顿法限制高斯 - 牛顿的步长，以避免当一个过长步长的非线性函数的雅可比矩阵是在当前点几乎奇异。因此，Fletcher便对于信赖域方法采取限制步长的方法。对于信赖域方法的研究先驱分别有Powell , Fletcher , Hebden , Madsen , Osborne , Moreacute; , Toint , Dennis and Mei , Sorensen , and Steihaug这些人。其中More很早就给出了优秀的调研信赖域方法，这种大众化的信赖域方法，规范了“信任域”这个术语。袁受邀了第四届国际定国会工业与应用数学在信赖域方法全体会议讲座，这是由Conn等著名的学者1999年7月在爱丁堡举行的举办的。 这本书第一次公布对信赖域的研究方法，直到出版时这都是对其很好的一个总结，被称为它的百科全书。
线搜索方法每次是沿搜索方向进行迭代，与线搜索方法相比较，信赖域算法通常是在当前迭代的信赖域附近搜索迭代点，然后获得新的迭代点。确切地说，在第k次迭代时，对于一般的信赖域算法优化问题
(1.1)
其中，f（x）是目标函数，是可行集，通过求解下面的信赖域子问题获得试探步
(1.2)
(1.3)
其中，是近似目标函数当前迭代点的函数模型，是一个近似可行集合的试探步。是范数，是信赖域半径。
优化问题（1.1）的一个信赖域方法的框架如下:
优化信赖域法的框架
步1 初始化，给出，构造，和，令k:=1。
步2 如果收敛，则停止;给出试探步，求解问题（1.2） - （1.3）。
步3 确定试验步骤是否应该接受（是否设或）。
步4 构造，选择和;设k:=k 1;转到步2。
因此，信赖域算法的主要思想是信赖域子问题的求解以及如何判断试探步。为了定义信赖域子问题，我们需要建立一个近似模型，并选择信赖域半径。一旦试探步通过求解信赖域子问题恰好合适或不精确，我们就可以利用试探点来衡量试探步的好坏。根据一些标准，如果试探点满足条件，并且比当前迭代点更好，我们就接受这一试探步。在每次迭代结束后，我们需要重新选择选择信赖域半径，并且为下一次迭代构建新近似模型函数。
由于信赖域的约束条件（1.3），一个信赖域子问题的可行域始终会是一个有界集，这使我们能够使用非凸模型近似函数。这是信赖域方法相比线搜索方法的优势之一。信赖域约束可以被看作是一个隐藏的合适范数。这些使得信赖域算法是可靠和稳定的，所以它们可以被应用到非凸和病态问题上。
信赖域方法的一个优点是，信赖域算法比线搜索算法更容易建立收敛结果。例如，为了证明线搜索型拟牛顿法的全局收敛，人们需要使用复杂的技术来估计拟牛顿法的成长矩阵，而信赖域型拟牛顿法可以很容易的建立全局收敛准则，只要拟牛顿法的成长矩阵不会超过线性增加速度。在文献中，它解释了为什么线搜索的假设条件都更强。信赖域方法相比线搜索方法的另一个优点是，信赖域方法采用二阶常常收敛到二阶稳定点，而线搜索式方法则可能收敛到固定点。
在本文中，我们回顾了信赖域方法的最新成果。在第二节我们考虑了无约束优化问题的信赖域方法，尤其是在关于子问题的求解上，更新了对信赖域半径的不规范使用，和由非标准欧式空间定义的信赖域。在第三节我们讨论了约束优化，其中重点是信赖域的子问题，并给出了增广拉格朗日函数的最新结果的方法。在第四节，我们主要介绍信赖域方法中非线性方程组和非线性的最小二乘法。 第五节。对非光滑优化的信赖域算法进行了讨论。并将信赖域方法进行了优化，对不连续的优化问题进行了综述。在第六节，讨论了现在的正规化方法。 第七节，在文章的中间给出了简短的讨论。
- 无约束优化
在本节中，我们考虑无约束优化，这样的情况下它的可行域X是整个空间。这是它的基本思想，比较简单，因为我们可以简单地赋值。因此，信赖域子问题在第k次迭代具有如下形式：
(2.1)
(2.2)
使作为一个试探步这是（2.1） - （2.2）的精确或不精确的解决方案。我们计算该预测减少的方式为，这是模型函数的下降量，和目标函数的实际减少 。在一般情况下，如果不是的固定点，则预测的。例如，用欧几里得范数二次模型函数信赖域限制标准的信赖域子问题（TRS）：
(2.3)
(2.4)
其中，是一个近似目标函数的海赛对称矩阵。子问题（2.3） - （2.4）被广泛应用于许多信赖域算法，因为它很容易解决，具有良好的理论特性包括拉格朗日函数的海赛矩阵（2.3） - （2.4）是半正定，并且它具有至多一个局部最小值。对于凸二次模型功能，它表明，截断共轭梯度法可以得到（2.3）- （2.4）一个很好的不精确的解决方案 ，即通过截断共轭梯度法得到目标函数的下降量将在信赖域的最大减少至少一半。是（2.3）- （2.4）的精确解 ，我们有
这是首次由Powell证明。然而，满足（2.5）使得成为（2.3）- （2.4）的精确解不是必要的。例如，一个极小的二次模型在（2.3）-（2.4）中沿信任区最速下降方向也满足（2.5）。类型（2.5）的不等式表示一定的充分降低后可以用近似模型来实现，只要不是一个固定的点目标函数。二次模型（2.3）不是唯一可能的模型。如下面锥模型所示：
这是由狄和孙给出的用于信赖域算法，其中。 不管选择哪种模型函数，我们通常要求用试探步得到满足一些“充分下降”的情况，类似（2.5），以建立算法的全局收敛。实际减少和预测减少之间的比
在信赖域算法中有非常重要的作用，因为它提供了一种衡量试探步的方法。主观上来说，一个较大的对应于更好的试验步骤，因为它实现了对于相同的预测的较低的目标函数值减少。因此，一般的策略是只要是接受试探步比预先设定的非负常数大。
对于无约束优化问题，模型信赖域方法给出如下:
无约束优化模型信赖域方法
步1 给出对称；
。
步2 如果则停止；求解（2.1） - （2.2），给出。
步3 计算；
（2-8）
选择，即满足
（2-9）
步4 选择一个新的模型函数和选择范数;
K：= K 1;转到步2。
不同的选择是袁、conn和Gloud等人讨论的主要内容。信赖域算法的全局收敛只要试探步满足类似（2.5）的充分下降条件就可以很快建立。为了证明一个信赖域方法的局部超线性收敛，一般的方法是要表明信赖域约束处于非活动状态的所有足够大ķ。为了确保，所述标准技术是要表明，从零界距离。
然而，边界去零只是超线性收敛的充分条件，但不是必要条件。因此，允许是值得研究的技术，之所以宁愿是病态条件的问题，这是因为更加可靠和稳定。在不连续的优化信赖域法，也变为零，因为它是所谓的临界步骤。
一种方法是让新的信赖域半径取代。Hei建议通过更新信赖域半径
其中，满足单调递增函数
。
假设算法收敛在该二阶充分条件被满足的f（x）局部极小。该算法是局部超线性收敛的，如果我们能证明是接近牛顿迭代的一步 ，即
而信赖域约束条件（）是无效的。假设是xi;，2.11）意味着对所有足够大ķ。因此，可以合理地让信赖。范和袁建议使用
其中
给到（2.12）可以被概括至
其中，参数alpha;isin;（0，1]。
最近，通过应用巴斯汀等的精度在优化过程中提供的资料自适应目的，利用其中的技术以改变目标函数的计算。
在他们回顾信赖域算法，他们使用的模型函数在当前迭代计算实际压缩比和在前面的试验步骤所预测的降低，并使用该比率来更新信赖域半径。也就是说，如果，建立新的函数模型。然后得到新的比率
经过计算，用下式更新信赖域半径：
其中
和常数满足用来确保。请注意，使用在中的梯度。
对于大规模的优化问题，即当n非常大的时候，信赖域子问题也是大规模的。因此，它是有价值的调查子空间性质信赖域子。考虑标准信赖域拟牛顿法在模型函数是与海森矩阵二次函数由拟牛顿法进行更新。王和袁给出了子空间试验步骤的属性：
引理1 假设矩阵更新公式是任何一个选择从PSB和Broyden族（这里的更新可能是单数），是第k个更新矩阵。是子问题（2.3）- （2.4）的解决方案 ，是任何给定的初始点）。那么对于所有的kge;1，。而且对于任何的任何，我们有
这一结果扩展了在线搜索类型拟牛顿方法相似的结果通过西格尔[112]给出。根据这一结果，可以证明，充分空间信赖区域准牛顿方法等效于子空间对应，只要近似的Hessian是由拟牛顿公式和初始黑森州更新近似适当地选择。在空间算法，试用步骤可通过解决所有覆盖的子空间的信赖域获得梯度向量至今计算。更确切地说，在试验步骤可以被定义通过最小化所有覆盖的子空间的准牛顿二次模型计算的梯度。信赖域子空间算法的优点是子问题在低维定义，因此它们更适合于大规模问题。
对无约束一般信赖域子空间算法子问题优化有如下形式：
其中，是一个低维子空间。可能的选择有
和
其中是一个非负整数，，是第i个坐标单位向量。关于子空间上的选择更详细的讨论，请参阅袁的文献。
关于范数在信赖域子问题上选择的标准，它通常使用的是欧几里得范数，因为欧几里得范信赖域子（2.3） - （2.4）被广泛的研究和容易解决。。然而，在某些特殊的情况下，我们可以对欧几里得范数使用不同的标准范数。 例如，对于二次函数模型（2.3）与浅滩通过有限的内存被更新拟牛顿更新，矩阵的形式为
其中，满足是对角线正定。通常情况下，r是远小于n的。 Burdakov等人建议使用范数
其中，是投影到子空间正交的Range（）。在这情况下，信赖域子问题（2.1） - （2.2）的解可以表示（正交分解）作为的。和都已经闭合形式解，由于这样的事实，s为盒子的的解决方案约束QP（在中）
而解决了2-范数受限的特殊QP
龚和Zikrin共同报告使用圆筒形信赖域算法令人鼓舞的数字结果信赖域（2.23）
一类为多尺度非线性优化递归的信赖域方法，由偏微分方程支配系统经常发生的，是由给定格拉顿等人。无约束优化标准的信赖域方法是这个类的一个特例，由格拉顿，Sartenaer获得显着成效和Toint是不受约束的信赖域算法至多需要迭代在下实现。
- 约束优化
通常情况下，约束优化问题（1.1）的信赖域方法比线搜索方法更复杂得多，由于困难，近似可行区域值可能没有点，在当前迭代的信任区域只要即。考虑的情况是可行集X是由等式和不等式约束定义
在第k次迭代点，线路搜索类型SQP方法通常通过计算搜索方向求解QP子问题：
其中，是一个二次近似拉格朗日函数
是可行集的线性约束。为了克服可能困难，即，我们可以使用下面的信赖域子问题，而不是使用（1.2） - （1.3）
对于一些很容易看出，对于足够小，条件是和非空，在这种特殊情况等式
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[145948]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
