第8讲信赖域方法

f
(xk1())
f
(xk )
gkT
xk
1(
)
xk
,
0,
1 2
则接受 xk1 为新点 xk1.并根据信赖域算法校正信赖域半径,
否则, 令 xk1 : xk ,并缩小信赖域半径.
18
例题
设
f
(x)
x4 1
x2 1
x
2
2
，当前点
xk
1,1T ，K
1 ，试用双
2
折线法求 xk1. 解:
由于 xk
7
5．信赖域算法
Step1. 给 出 初 始 点 x0 ， 信 赖 域 半 径 的 上 界 , 0 0, , 0 ,
0 1 2 1,0 1 1 2,k : 0. Step2. 如果 gk ,停止.
Step3. (近似)求解子问题(2),得到sk .
Step4. 计算 f (xk sk )和rk .令
很成功迭代: 成功迭代: 不成功迭代:
rk 2 , k1 k , 信赖域扩大;
rk 1,2 ;
rk , 信赖域缩小.
算法参数选择建议:
1
0.01,2
0.75, 1
0.5,
2
2, 0
1,或者0
1 10
g0
.
9
6．信赖域方法的收敛性 理论假设：
(1). Hesse 近似 Bk 按范数一致有界, 即 Bk M ,M 是某个
(1). how to choose and compute the approximation q .
(defined at the current point x),
(2). how to choose and modify the trust region k ,
(3). how accurately to solve the trust-region sub-problem.
gk
4 2
402 0.684.
g
T k
Gk
gk
g
T k
G 1 k
g
k
512
32 7
0.8 0.2 0.747,
skNˆ
skN
0.320 0.747
.
20
由于 skNˆ k ，故取双折线步长为 sk skc (skNˆ skc ), 0,1,
使得 sk k . 解二次方程:
算法的性态).
15
单折线法总结
(1)
skc 2 k 时,
sk
k gk gk 2
( K
1时的Cauchy点);
(2) skc 2 k 时, 再计算牛顿步skN :
2.1 如果 skN 2 k ,则 sk skN ;
2.2 如果 skN 2 k ,则 sk skc (skN skc ), 其中, 为方程：
3.6 信赖域方法 ( Trust-Region Methods)
1. 基本思想 2. 线性搜索与信赖域方法的联系 3. 信赖域方法思想 4. 信赖域半径的选择 5. 信赖域算法 6. 信赖域方法的收敛性 7. 解信赖域子问题 8. 优化工具箱
1
信赖域方法和线性搜索方法是求解非线性优化问题的两 类主要的数值方法.与线性搜索方法相比，信赖域方法思想 新颖，具有可靠性，有效性和很强的收敛性.鉴于信赖域方 法的优点，由它来构造新的优化方法成为非线性优化界许 多学者关注的焦点.
6
4．信赖域半径的选择
(1). rk 越接近于 1，表明接近程度越好.这时可以增大k 以扩大信 赖域 ;
(2). rk 0但是不接近于 1, 保持k 不变 ; (3). 如果rk 接近于 0, 减小k ,缩小信赖域 . 或者其它k 的选择方法： Satenaer(1997)研究了初始信赖域半径 0 的选取对算法有效性 的影响, 给出了一个自动确定初始信赖域半径的ITRR算法, 其基本 思想是通过二次近似模型和目标函数沿负梯度方向的近似程度, 调 节初始信赖域半径. Zhang(2002)等同把这一思想应用到信赖域半径的自适应.
xN k 1
).
两者连线与信赖域边界的交点取为 xk1,即 xk1 xk k ,当牛
顿步 skN 的长度小于 skN
k时,
xk
1
取为牛顿点
xN k 1
.
s1 skc k gk ,
s2 skN Bk1gk ,
k
gkT gk gkT Bk gk
.
Dennis和Mei(1979)提出双折线法,在牛顿方向上取一点 s3 ,连
Powell [1970 ]给出了求解(2) 的单折线法, 当 Bk 可逆时,用
连接初始点s0 及s1, s2 的单折线近似最优曲线,在该折线上取点s使 得 s 2 k 作为(2) 的解 sk .
13
其中s1是 Cauchy点 (由最速下降法产生的极小点 C.P.);
s2 是牛顿点
(由牛顿方法产生的极小点
单折线法； 双折线法; 切线折线法; 信赖域自适应调整算法………
2
1． 基本思想
在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代
点 xk 的一个小邻域.然后在这个邻域内求解一个子问题，得到试
探步长(trial step) sk ，接着用某一评价函数来决定是否接受该
试探步以及确定下一次迭代的信赖域. 如果试探步长被接受，则：
综上所述:
skc (skN skc ) k 的解.
xk
k gk gk 2
,
当 skc k
xk 1
xk
skc
(skN
skc ),当
skc
k且 skN
k
xk Bk1gk ,
当 skc k skN k
（8）
16
双折线法总结
xk
k gk gk 2
,
当 skc k
xk 1
xk
xk 1
xk
xk
,
sk ,
if rk 1 .
or.
Step5.校正信赖域半径.令
k1 0,1k k1 1k , k
if rk 1;
if rk 1,2 ;
k1 k , min 2k , if rk 2.
8
5．信赖域算法 Step6. 产生 Bk1，校正qk，令k : k 1, 转 Step 2.
min s.t.
qk s
f
(xk )
gkT s
1 2
sT
Bk
s
,
s 2 k
（2）
其中，s x xk , gk 是目标函数 f (x)在当前迭代点 xk 处的梯度，
Bk Rnn对称，是 f (x)在 xk 处 Hesse 阵2 f (xk )或者其近似.
5
3．信赖域方法思想
设 sk 是信赖域子问题(2)的解.我们称目标函数 f (x)在第k 步的
正的常数. (2). 函数 f : Rn R 在一个有界的水平集 L(x) 上连续可微
且有下界.
(3). 对于某个正的常数 , sk 2 k .
对于二次模型函数(2)，定义其柯西点:
sc k
k
k gk gk
,
其中,
1,
if gkT Bk gk 0;
k
min
k
gk 3
g
T
k
Bk
g
k
,1,
式(6),为了降低计算的复杂度,人们并不精确求解(2),而
是计算满足(6)式的试探步 sk .
11
定义 1
设1 0,1, 0是两常数,如果sk Rn满足(6)式和不等式:
sk 2 (1)k
(7)
则称sk 是子问题(2)的1, 下降试探步.
显然,子问题(2)的精确解是 0.5, 0 下降试探步.
定理 2 全局收敛性定理[袁亚湘，1994]
设函数 f (x)在 Rn上连续可微,如果1 0， Bk 2 M 对一切k 成立，则
对于 0信赖域算法必定经过有限次迭代后终止或者产生点列 xk 使 得:
lim
k
f
( xk
)
中必有一个成立.
lim
k
gk
0
2
12
7．解信赖域子问题 信赖域方法在每步迭代中求解下列形式的子问题:
得 0.867.
skc
(skNˆ
skc )
2 2
2 k
.
因此, sk
skc
( skNˆ
skc )
0.340 0.669
,
xk 1
xk
sk
0.660 0.331
.
21
8. Optimization Toolbox Many of the methods used in the Optimization Toolbox
1,1T ,则 gk
f
(xk )
4x3 1
2x1
,
2x2
从而, 可以得到 gk 6 , 2T .
同理可得:
Gk
2
f
(xk )
12x2 1
2
0
0 14
2
0
0 2
19
skN
Gk1gk
3 7
,
1T
.
skc
gk
2 2
g
T
k
Gk
g
k
gk
0.469, 0.156T .
由于 skc 0.496 k ，从而需要计算牛顿步 skNˆ ，有
min
qk s
f
(xk )
g
T k
s
1 2
sT
Bk
s
,
s.t. s 2 k
（2）
其中，gk 是目标函数 f (x)在当前迭代点 xk 处的梯度，Bk Rnn对称，
是 f (x)在 xk 处Hessian阵的近似. k 为信赖域半径, s 为待求变量.
当k 变化时, s 的解形成一条空间曲线, 称为最优曲线.
否则，
xk1 xk sk ，
xk1 xk .
新的信赖域的大小取决于试探步的好坏，粗略地说，如果 试探步较好，在下一步信赖域扩大或保持不变，否则减小信赖域.
3
2．线性搜索与信赖域方法的联系 2.1 不同点: 与线性搜索方法相比，信赖域方法直接通过模型求解得到
试探步长，而不是先确定搜索方向，再寻找步长. 2.2 相同点: 线搜索方向可以看成是信赖域半径充分大时的信赖域步；
接s1 和s3 ,在该折线上取一点 s,使得 s k 作为(2) 的解sk . 即是把Cauchy点与牛顿方向的 N 连接起来,将这条连线与信
赖域边界的交点取为 xk1,称为双折线.
14
折线
xk
C.P.
xN k 1
称
为
单
折
线
,
xk
C.P.
Nˆ
xN k 1
称为双折线.(信赖域迭代中产生的点偏向牛顿方向,会改善
skc
(skNˆ
skc ),当
skc
k且 skNˆ
k ，
xk
Bk1gk ,
当 skc k skNˆ k
（9）
其中，skNˆ skN , ,1,
gk
4 2
g
T
k
Bk
g
k
g
T
k
B1 k
g
k
.如果 1，双折线法
就变成了单折线法.一般的,取 0.8 0.2.
上述方法满足：
(1).
而信赖域方法所得出的试探步可看成是将二次逼近模型加上 一个惩罚项之后所导致的线搜索方向.
4
3．信赖域方法思想
设当前点 xk 的邻域定义为:
k x Rn x xk k
（1）
其中, k 称为信赖域半径. 目标函数在极值点附近近似一个二次函数，因此对于无约束
优化问题,利用二次逼近，构造如下信赖域子问题:
22
[s,val,posdef,count,lambda] = TRUST(g(x),B,d) ; %TRUST是matlab自带的求解信赖域子问题的函数 利用它信赖域方法的程序就简单多了.
23
作业
P111. 习题7.
24
实际下降量(真实下降量):
Aredk f (xk ) f (xk sk )
(3)
称二次模型函数qk s的下降量(预测下降量)：
Predk qk 0 qk sk
(4)
定义比值:
rk
Aredk Predk
.
(5)
它衡量了二次模型与目标函数的逼近程度，rk 越接近于 1，表
明接近程度越好. 因此，我们也用这个量来确定下次迭代的信赖域半径.
从点 xk 到Cauchy点C.P. ,
到
x Nˆ k 1
的距离单调增加;
(2).
从Cauchy点C.P. ,
到 xNˆ k 1
模型函数值单调减少.
17
在产生Cauchy点C.P.和 Nˆ 点后,所求的新点 xk1由(9)式得出,选 择 ,使得:
skc skN skc
2 2.
2
k
如果所得到的 xk1 满足下降性要求:
or.
10
定理 1 二次模型子问题(2)中的精确解, 近似解, Cauchy 点均
满足:
qkห้องสมุดไป่ตู้0 qk sk 1
gk
min k ,
gk Bk
,
（6）
其中,1 0,1.
当
1
1 2
时,
s
所满足的不等式由
Powell(1975)给出,信赖
域方法的收敛性主要是基于试探步满足当
1
1 2
时的不等
are based on trust-regions, a simple yet powerful concept in optimization.
The key questions in defining a specific trust-region approach to minimizing are :