（ 10.5.3）
求解信赖域子问题显然 是关键的
（k） ˆ ，使得 若d 是（ 10.5.3 ）的最优解，则存在乘 子 ˆ 2 （k） （k） （k） （k） f（x ）d f（x ） d 0 1 （k） （k） 2 （d d ） （k） （ || d || -rk） 0 T
（k） （k） （k） x 后，先确定一个搜索方 向d ，然后沿着这个搜索方 向d
选择选择适当的步长 k，产生新的迭代点
（k 1） （k） （k） x x k d

先确定方向，再确定步长
1.信赖域方法与常规方法的区别

信赖域方法
（k） k {x R n | || x - x || rk }
信赖域方法
15721546 马广庆
前言
上一节，学习了牛顿法 ，传统的牛顿法属于局 部收敛算法 （收敛性与初始点的选 取有关），为了得到全 局收敛算法，
（k） （k） 对它做了改进，即当 f（x ） 0， 2 f（x ）正定时， （k） - f（x ） 沿着搜索方向 d 2 作一维搜索， （k） f（x ） 从而得到一个缩短的步 长，这个就是阻尼牛顿 法， （k）
3.信赖域算法
（k） （k） （k） 求出信赖子问题 d 后，点x d 能否作为原问题的近似 解，
还要根据用（ k d）逼近f（x）是否成功来确定。 如果函数值实际下降量 与预测下降量之比，即
（k） （k） f（x ( k )） - f (x d ) k （k） （k） f（x ） - （ d ） k （k） 太小，就认为逼近不成 功，后继点仍取 x ，且信赖域半径 rk 1 （k 1） （k） （k） 若 k比较大，则逼近成功， 后继点x x d ，
3.信赖域算法
考虑无约束问题： min：f（x），x n
（k ） 将f（x）在给定点x 处展开，取二次近似
1 T （k ） （ k） T （k) f（x） f ( x ( k ) ) f ( x ( k ) ) （ x-x ） （x - x ） 2 f(x )(x - x (k) ) 2 （k） 取d （x - x ），得到二次模型
定义当前点的邻域 这里rk 是第k步的信赖半径 在这个信赖域内，优化 目标函数的二次逼近式
（k） （二次模型函数）得到 模型函数近似解 d （k 1） （k） （k） （k 1） （k） 产生新的迭代点 x x d ，或x x

相当于直接确定了位移
2.信赖域算法的基本思想
对于问题：min：f（x） 首先给出初始点，在初 始点附近构造一个近似 于原目标函数的 近似模型，信赖域子问 题就是在当前迭代点的 某个邻域内
该方法具有整体收敛性 。 但它没有进一步的使用 二次模型函数。 这一节，将介绍另一种 全局收敛算法- 信赖域算法
信赖域方法
1.信赖域方法与常规方法区别 2.信赖域基本思想 3.信赖域方法
4.算法步骤
5.例题分析 6.收敛性分析
1.信赖域方法与常规方法的区别

常规方法
前面介绍的无约束最优 化方法，一般策略是在 给定点
（1） 求逼近模型的最优点。 对于给定的初始点 x ，在其附近建立 （1） 目标函数的模型，并且 假定在x 的某个邻域内这个模型 大致
代表目标函数，接下来 为了得到要求的点，我 们选择一个
（2） （2） 适当的位移，移动到下 一个点x ，然后在x 附近建立目标
函数的新模型。继续以 上过程，用这种方法我 们可以找到 f（x）的最小值点。信赖域 半径的大小通过迭代逐 步调节， 如果在一次迭代中近似 模型比较好的逼近于原 问题， 则信赖域半径可适当扩 大，反之，信赖域半径 就减小。
3.信赖域方法

要从上海火车站去人民广场，有两种方法： ①可以先定一个方向，比如先向西走，走着走着发现方向 有点不对（人民广场应该是时尚地标啊，怎么越走感觉越 郊区了呢），就调整一下方向，变成向东南方向走，诸如 此类。 ②用信赖域算法，就比如，我先划一个圈，然后在这个圈 里面找离人民广场可能最接近的点，之后在这个点为中心 再画一个圈，在这个圈内找离人民 广场可能最近的点， 以此类推。
1 rk； 2
且rk 1 rk 或rk 1 2rk
3.信赖域算法

特点： 不要求目标函数的Hesse矩阵正定，在非正定的情况下也 能处理。 既有牛顿法的快速局部收敛性，也有理想的全局收敛性。 算法利用二次模型来修正步长，使得目标函数的下降比线 搜索方法更有效。


由于位移长度受到Taylor展开式有效的信赖域的限制，此 方法又称为有限步长法
（ f ( x ) f ( x k d）
(k )
(k ) T
1 T 2 （k) ) d d f(x )d 2
3.信赖域算法
（k） （k） 为了在x 附近用（ d ）近似 f （ x d）， k
限定d的取值，令|| d || rk , 即 || x - x (k) || rk rk 就是前面提到的第 k步的信赖域半径 （由此可以看出，限定 d的取值实质是在当前迭 代点的某个邻域 内建立一个简单模型， 这个简单模型近似于原 问题并求极值） 这样，求函数 f（x）的极小点问题就归结 为解 一系列子问题 1 T 2 （k) (k ) (k ) T min：（ d ） f ( x ) f ( x ) d d f(x )d k 2 s.t . || d || rk （可以看出信赖域算法 是将复杂的最优问题转 化为 一些列相对简单的局部 寻优问题）
记：
ˆ
1 T （k） （k） 2
（d d ） （k） 得到d 为最优解的必要条件
（k） （k） （k） （k） 2 f（x ）d d -f（x ） （k） （ || d || -rk） 0 0 （k） || d || r k （k） （k） （k） -1 （k） 设 2 f（x ） I可逆，有（ 10.5.5 ）得到 || d |||| （ 2 f（x ） I） f（x ||