min qk s s.t s op , s k
由于最优曲线的确定需要计算矩阵 和特征向量， 相当费时。
k
Bk
的所有特征值
折线法：用低维空间内满足一定要求的折线，记为
k ,
代替最优曲线。通过求解：
min qk s s.t s , s k
T k
1
步骤4:
计算
f xk sk 和 rk , 令：
xk sk xk rk 1 others
xk 1
步骤5:
校正信赖域半径，令：
k 1 0, 1 k
步骤6:
k 1 k , min 2 k , rk 2 产生 Bk 1 , 校正 qk (s), 令 k k 1, 转 步骤2
折线法基本思想
1 T min qk s f k g k s sT Gk s 2
1
s.t
s k
如果令信赖域的半径 k 在区间
0, 内连பைடு நூலகம்变化，
则问题(1)的解 sk 在空间 R n 中形成一条光滑的连续曲线， k 记为 op . 此时， 问题(1)等价于在信赖域内并且在最优曲线 k op 上确定一点使二次函数 qk s 取极小，即
称为双折线.(信赖域迭代中产生的点偏向牛顿方向,会改善 算法的性态).
在双折线情形下：
k xk g g k k ˆ c N c xk 1 xk sk sk sk 1 xk Gk g k
s k
c k


c k
s k , s k
c k
ˆ N k
s k , s k
ˆ N k
其中 一般取
s s , ,1,
ˆ N k N k
g G g g G g
T k k k T k 1 k k
gk
4
.
0.8 0.2 .
f x x x x 1 k 试用双折线法求 xk 1 . , 2 14 解： x 1, 1T , g 6, 2 T , G k k k T 3 N 1 sk Gk g k ,1 7
让信赖域迭代中产生的点偏向牛顿方向，
ˆ 于是把Cauchy点和牛顿方向上的 N
ˆ xN xk C.P. N k 1
点连接起来，
并将这条连线与信赖域边界的交点取为
xk 1.
称为双折线．
ˆ 折线 xk C.P. xkN1 称为单折线, xk C.P. N xkN1
综上：
k xk gk skc k gk c N c c N xk 1 xk sk sk sk sk k , sk k xk Gk1 g k skc k , skN k
双折线法 (1979)
信赖域方法的模型子问题
1 T min qk s f k g s s Gk s 2
T k
1
s.t
其中
s k
是Hesse阵 2 f x 的近似 k
s x xk , g k f xk , Gk k 0 为信赖域半径．
注：
(1) 这种方法既具有牛顿法的快速局部收敛性，又具有 理想的全局收敛性。 (2) 不要求目标函数的Hesse阵是正定的。 (3) 利用了二次模型来求修正步长，使得目标函数的下降比 线性搜索方法更有效。
(P1) 点
x 到 xk
(P2) 函数值
qk s
性质(P1)确保对任意给定的 k , 折线上的近似解惟一。 性质(P2)确保在折线上所确定的近似解 定理的条件。
sk
能满足收敛性
折线法算法原理(1970)
Cauchy点：由最速下降法产生的极小点，记为C.P. Newton点： 由牛顿法产生的极小点，记为
k 1 1 k , k
rk 1 rk [1 , 2 )
注： 参数建议取：
1 0.01,2 0.75 , 1 0.5, 2 2, 0 1
1 T qk s f k g s s Bk s 2
T k
信赖域子问题
rk 越接近于１， 表明模型函数 qk ( s)与目标函数 f ( x)的 rk 0 不接近于１， 可以保持 k 不变。
与目标函数 f ( x ) 的 rk 接近于零或取负值，表明 qk ( s)
一致性程度越好， 可以增大 k 以扩大信赖域。 (2) (3)
一致性程度不好， 可以减小
k 以缩小信赖域．
k 1 k k
Newton点为
x
N k 1
xk s xk Gk g k .
N k
1
g gk s T gk , g k Gk g kT gk gk c Caushy点为： xk 1 xk gk . T g k Gk g k
c Cauchy步为：k
T k
N Newton步为： k
0.867s

0,1
c k

2

2 k
ˆ N k
0.340 s 0.669
c k

[s,val,posdef,count,lambda] = TRUST(g(x),B,d) ;
(4) 由于步长受到使Taylor展开式有效的信赖域的限制，
故方法又称为有限步长法。
1 T min qk s f k g s s Gk s 2 s.t s k
T k
信赖域半径的选择
根据模型函数 qk s 与目标函数 f x 的拟合程度来调整
信赖域半径
k . sk ,
x
N k 1
连接Cauchy点(由最速下降法产生的极小点C.P.)和牛顿点(即 由牛顿法产生的极小点
取为 显然, 折线
xkN1）,
其连线与信赖域的边界的交点
xk 1.
xk 1 xk k .
xk C.P. xkN1
称为单折线．
折线法算法原理(1970)
连接Cauchy点(由最速下降法产生的极小点C.P.)和牛顿点(即
g Gk g k
.
T k
T gk gk xkc1 xk skc xk T gk . g k Gk g k
1 T qk s f k g s s Bk s 2
T k
Newton点：
d k Gk1 g k , k 1,
Newton步为：s
N k
k d G g ,
=qk xk g k f xk g k
令 '
2
1 2 T g k Gk g k 2
=0,
k
得 k

k
gk
T k
2
Cauchy步为：s c Caushy点为：
g gk k d k g k T gk . g k Gk g k
k , 计算 s , 有：
ˆ N k
40 2 T 0.684 T 1 g k Gk g k g k Gk g k 32 512 7 0.8 0.2 0.747 0.320 ˆ N N sk sk 0.747 ˆ N 由于 s 0.813 k , 故取双折线步长为： k
信赖域算法
步骤1:
x0 R n , 信赖域半径的上界 , 0 0, , 0, 0 1 2 1, 0 1 1 2 , k 0.
给出
步骤2: 步骤3:
g k , 停止． 求解子问题(1)得到 sk .
如果
1 T min qk s f k g s s Gk s 2 s.t s k
在每次迭代中给出一个信赖域， 这个信赖域一般是当前迭代点
xk 的一个小邻域。然后在这个邻域内求解一个子问题，得到 sk ，接
着用某一评价函数来决定是否接受该 sk 以及确定下一次迭代的信 赖域。
如果试探步长被接受，则：
xk 1 xk sk ，
否则，
xk 1 xk .
新的信赖域的大小取决于试探步的好坏，粗略地说，如果试探步 较好，下一步信赖域扩大或保持不变，否则减小信赖域。
定义比值：
给定问题(1)的解
f xk f xk sk Ared k rk qk 0 qk sk Pred k
它衡量模型函数 qk
s 与目标函数 f x
的一致性程度。
注： (1)
f xk f xk sk Ared k rk qk 0 qk sk Pred k
信赖域方法
信赖域方法是求解最优化问题的另一类有效方法。 其最初的设计思想可追溯至Levenberg和Marquart对 GaussNewton法的修正。 线搜索方法是把一个复杂的最优化问题转化成一系列简单 的一维寻优问题。 信赖域方法是把最优化问题转化为一系列相对简单的局部 寻优问题。
基本思想
牛顿法的基本思想是在迭代点
xkN1 由牛顿法产生的极小点
取为 显然,
）, 其连线与信赖域的边界的交点
xk 1.
xk 1 xk k .
xk 1 =？
Caushy点和 Newton点的表达 式？
Caushy点：
k
1 T qk s f k g s s Bk s 2
T k
d =-g k , 精确一维搜索求最佳步长 =qk (xk + d k )