（ 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
（1）
1 T 2 （1） （1） T （1） min： （ d ） def f （ x ） f （ x ） d d f （ x ）d 1 2 s.t. || d || 1 即求解
2 2 min： （ d ） 5 4d d d 1 2 1 2 2 s.t.d1 d2 2 1
信赖域方法
15721546 马广庆
前言
上一节，学习了牛顿法 ，传统的牛顿法属于局 部收敛算法 （收敛性与初始点的选 取有关），为了得到全 局收敛算法，
（k） （k） 对它做了改进，即当 f（x ） 0， 2 f（x ）正定时， （k） - f（x ） 沿着搜索方向 d 2 作一维搜索， （k） f（x ） 从而得到一个缩短的步 长，这个就是阻尼牛顿 法， （k）
（2） （2） 2 s.t.d1 d2 2 4 （2） 0 （2） （2） 得到子问题的解 d ，算的f（x d ） 0 1 （2） （ d ） 1，实际下降量与预测下 降量之比， 2 2
5.例题讲解
2-0 2 2 -1
令x
（3）
x
（2）
d
（2）
0 ，r3 2r2 4 2
（3） .求解子问题 1 T 2 （k) min：（ f ( x ) f ( x ) d d f(x )d k d） 2 s.t. || d || rk
(k ) (k ) T
4.算法步骤
（k） 得到子问题的最优解 d ，令 （k） （k） f（x ( k )） - f (x d ) k （k） （k） f（x ） - （ d ） k （k 1） （k） （4） .如果 k ，令x x ；如果 k ， （k 1） （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 ），得到二次模型
（ 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 （可以看出信赖域算法 是将复杂的最优问题转 化为 一些列相对简单的局部 寻优问题）
（3） （3）
0 经过第三次迭代。计算 得到f（x ） 1，f（x ） 0 （3） 0 x 是最优解 2
6.收敛性分析
（1） 定理：设f（x）是 n 上的实函数，x 是给定的初始点， （1） S {x | f（x） f（x ） }是有界闭集，
1 （5） .如果 k ，令rk 1 rk；如果 k 2 令rk 1 rk；如果 k ，令rk 1 2rk （6） .置k k 1，转步骤（ 2）
5.例题讲解

例题：无约束问题
4 2 min：f（x） x1 x1 x2 2 - 4x 2 5
6.收敛性分析
证明：
（k） （k） 为简便，记f k f（x ）， 2f k 2 f（x ） .
由于S是有界闭集， 2 f（x）在S上连续，因此存在正数 M，使得 对每个k有 || 2 f k || M.
（k） 先证明|| f（x ） || 存在收敛到0的子列。反证法，假定
（k） （k） （k） x 后，先确定一个搜索方 向d ，然后沿着这个搜索方 向d
选择选择适当的步长 k，产生新的迭代点
（k 1） （k） （k） x x k d

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

信赖域方法
（k） k {x R n | || x - x || rk }
该方法具有整体收敛性 。 但它没有进一步的使用 二次模型函数。 这一节，将介绍另一种 全局收敛算法- 信赖域算法
信赖域方法
1.信赖域方法与常规方法区别 2.信赖域基本思想 3.信赖域方法
4.算法步骤
5.例题分析 敛性分析
1.信赖域方法与常规方法的区别

常规方法
前面介绍的无约束最优 化方法，一般策略是在 给定点

4.算法步骤

步骤如下：
（1） （1 ） .给定可行点x ，信赖域半径 1，参数0 1
1 3 （一般 ， ）及精度要求 ，置k 1 4 4 （k） （k） （k） （2） .计算f（x ），f（x ） .若 || f（x ） || ，
（k） （k） 则停止计算，得到解 x ；否则，计算 2 f（x ）
3.信赖域方法

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

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


由于位移长度受到Taylor展开式有效的信赖域的限制，此 方法又称为有限步长法
5.例题讲解
（1） 0 d （1） 1 得到子问题的 K T点，也是最优解 d （1） d 2 1 （1） （1） （1） 函数值f（x d ） 2， （ d ） 2 1
实际下降量与预测下降 量之比
（1） （1） （1） f（x ） - f（x d ） 5-2 1 1 （1） （1） f（x ） - （ 5-2 1 d ）
' T
（ 10.5.8）
（ 10.5.9）
由于d是最速下降方向，因此 0 || f k ||4 || f k ||2 当 （0，rk）时，下降量 Q T 2M 2f k 2 f k f k 当 rk时，根据（ 10.5.9 ）式，即f k 2 f k f k rk || f k ||3
记：
ˆ
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 ||
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 ，
逼近成功，令 x
（2）
x
（1）
d
（1）
0 ，r2 2r1 2 1
进行第二次迭代，经计 算得到 0 2 2 0 （2） f（x ） 2，f（x ） , f（x ） ，解子问题 2 0 2 2 min：（ 2 - 2d2 d1 d2 2 d） 2
取初点x
（1）
0 1 , 信赖域半径r1 1，取 ， 4 0
3 ，试用信赖域方法求最 优解 4
5.例题讲解
（1） 解：经计算得到函数值 f（x ） 5，目标函数的梯度
0 2 0 2 （1） f（x ） ，Hesse矩阵 f（x ） 4 0 2 解子问题
定义当前点的邻域 这里rk 是第k步的信赖半径 在这个信赖域内，优化 目标函数的二次逼近式
（k） （二次模型函数）得到 模型函数近似解 d （k 1） （k） （k） （k 1） （k） 产生新的迭代点 x x d ，或x x

相当于直接确定了位移
2.信赖域算法的基本思想
对于问题：min：f（x） 首先给出初始点，在初 始点附近构造一个近似 于原目标函数的 近似模型，信赖域子问 题就是在当前迭代点的 某个邻域内