文档介绍：最优化方法结课论文——信赖域的相关知识姓名: 历红影学号: 2010052210 学院:理学院班级:信息 102 班教师:葛仁东信赖域方法是非线性优化的一类重要的数值计算方法。它在近二十年来受到了非线性优化研究界非常的重视,特别是最近几年,一直是非线性优化的研究热点。目前,信赖域方法已经和传统的线收索方法并列为非线性规划的两类主要数值方法。信赖域方法的研究起始于 Powell 1970 。但是,人们发现信赖域方法的基本技巧在一定意义下等价于十分著名的求解非线性最小二乘的 Levenberg-Marquadt 方法。一. 信赖域理论信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点。所不同的是:线搜索技术是先产生位移方向(亦称为搜索方向),然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移,产生新的迭代点。信赖域方法的基本思想是: 首先给定一个所谓的“信赖域半径”作为位移长度的上界,并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移, 并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想, 需要缩小信赖域半径, 再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去,直到满足迭代终止条件。信赖域方法解决无约束线性规划的基本 min x R f(x) ?算法结构。设 kx 是第 k 次迭代点,记 k k f f(x ) ?, k k g f(x ) ??, kB 是Hesse 阵 2k f(x ) ?的第 k 次近似,则第 k 次迭代步的信赖域子问题具有如下形式: Tk1 min (d) g 2 T k k q d d B d ? ?, . . k s t d ??其中 k?是信赖域半径, ?是任一种向量范数,通常取 2 -范数或?-范数。定义 kf?为f 在第 k 步的实际下降量: - k k k k Δ f f f(x d ) ? ?, 定义 kq?对应的预测下降量: ???? 0 - k k k k q q q d ? ?。定义他们的比值为: kkkfrq ???一般的,我们有 0 kq ? ?。因此,若0 kr?,则0 kf ? ?, k k x d ?不能作为下一个迭代点,需要缩小信赖半径重新求解问题。若 kr 比较接近于 1 ,说明二次模型与目标函数在信赖与范围内有很好的相似,此时 1 k k k x x d ?? ?可以作为新的迭代点,同时下一次迭代时可以增大信赖半径,对于其他情况,信赖半径可以保持不变。二. 信赖域算法步骤 Step1. 给出初始点 0x ,信赖域半径的上界?,),0( 0???, Step2. 计算 kg ,如果??|| || kg ,停止;否则,计算 1?kB