第8讲信赖域方法

ɶ ɶ (3). 对于某个正的常数η , sk 2 ≤ η∆ k .
对于二次模型函数 ，定义其柯西点: 对于二次模型函数(2)，定义其柯西点 二次模型函数
s c = −τ k k ∆k gk , gk
其中, 其中
T 1, if g k Bk g k ≤ 0; gk 3 τk = min ∆ g T B g ,1 , or. k k k k
3
2．线性搜索与信赖域方法的联系 不同点: 2.1 不同点: 与线性搜索方法相比， 与线性搜索方法相比， 信赖域方法直接通过模型求解得到 试探步长，而不是先确定搜索方向，再寻找步长. 试探步长，而不是先确定搜索方向，再寻找步长. 2.2 相同点: 相同点: 线搜索方向可以看成是信赖域半径充分大时的信赖域步； 线搜索方向可以看成是信赖域半径充分大时的信赖域步； 而信赖域方法所得出的试探步可看成是将二次逼近模型加上 而信赖域方法所得出的试探步可看成是将二次逼近模型 加上 一个惩罚项之后所导致的线搜索方向. 一个惩罚项之后所导致的线搜索方向.
1 η1 = 0.01,η2 = 0.75, γ 1 = 0.5, γ 2 = 2, ∆ 0 = 1, 或者 ∆ 0 = g0 . 10
rk ≥ η 2 ,
∆ k +1 ≥ ∆ k , 信赖域扩大 信赖域扩大;
rk ∈ [η1 ,η2 ) ; rk < η ,
信赖域缩小. 信赖域缩小
9
6．信赖域方法的收敛性 ． 理论假设： 理论假设： (1). Hesse 近似 Bk 按范数一致有界 即 Bk ≤ M , M 是某个 按范数一致有界, 正的常数. 正的常数 (2). 函数 f : R n → R 在一个有界的水平集 L( x) 上连续可微 且有下界. 且有下界
sk
2
≤ (1 + η ) ∆ k
(7)
是子问题(2) (2)的 下降试探步. 则称 sk 是子问题(2)的 ( β1 ,η ) 下降试探步. 显然,子问题(2)的精确解是 下降试探步. 显然,子问题(2)的精确解是( 0.5,0 ) 下降试探步. (2)的精确 全局收敛性定理[袁亚湘， 定理 2 全局收敛性定理[袁亚湘，1994] 上连续可微, 成立， 设函数 f ( x) 在 R n 上连续可微,如果η1 > 0 ， Bk 2 ≤ M 对一切 k 成立，则 对于 ε = 0 信赖域算法必定经过有限次迭代后终止或者产生点列 xk 使 得:
2
1． 基本思想 在每次迭代中给出一个信赖域， 这个信赖域一般是当前迭代 在每次迭代中给出一个信赖域， 的一个小邻域 然后在这个邻域内求解一个子问题， 邻域内求解一个子问题 点 xk 的一个小邻域.然后在这个邻域内求解一个子问题，得到试 探步长(trial step) 探步长(trial step) sk ，接着用某一评价函数来决定是否接受该 试探步以及确定下一次迭代的信赖域. 试探步以及确定下一次迭代的信赖域. 如果试探步长被接受， 如果试探步长被接受，则：
lim f ( xk ) = −∞
k →∞
lim g k
k →∞
2
=0
中必有一个成立. 中必有一个成立.
12
7．解信赖域子问题 ． 信赖域方法在每步迭代中求解下列形式的子问题: 信赖域方法在每步迭代中求解下列形式的子问题
1 k T min q ( ) ( s ) = f ( xk ) + g k s + sT Bk s 2 , s.t. s ≤ ∆ k 2
xk + sk , if rk ≥ η1 . xk +1 = or. xk ,
Step5.校正信赖域半径 令 校正信赖域半径.令 校正信赖域半径
wk.baidu.com
∆ k +1 ∈ ∆ k , min {γ 2 ∆ k , ∆}
∆ k +1 ∈ ( 0, γ 1∆ k ] ∆ k +1 ∈ [γ 1∆ k , ∆ k ]
4
3．信赖域方法思想 ． 的邻域定义为: 设当前点 xk 的邻域定义为
Ω k = x ∈ R n x − xk ≤ ∆ k
{
}
（1） ）
其中, 称为信赖域半径. 其中 ∆ k 称为信赖域半径 目标函数在极值点附近近似一个二次函数， 目标函数在极值点附近近似一个二次函数，因此对于无约束 优化问题,利用二次逼近 构造如下信赖域子问题: 利用二次逼近， 优化问题 利用二次逼近，构造如下信赖域子问题 1 T (k ) T min q ( s ) = f ( xk ) + g k s + s Bk s 2 , （2） ） s.t. s ≤ ∆ k 2 其中， s 处的梯度， 其中， = x − xk , g k 是目标函数 f ( x) 在当前迭代点 xk 处的梯度，
Bk ∈ R n×n 对称，是 f ( x) 在 xk 处 Hesse 阵 ∇ 2 f ( xk ) 或者其近似 对称， 或者其近似.
5
3．信赖域方法思想 ． 是信赖域子问题(2)的解 的解.我们称目标函数 设 sk 是信赖域子问题 的解 我们称目标函数 f ( x) 在第 k 步的 实际下降量(真实下降量 实际下降量 真实下降量): 真实下降量 Ared k = f ( xk ) − f ( xk + sk ) 称二次模型函数 q ( k ) ( s ) 的下降量(预测下降量)： 的下降量 预测下降量 ： 预测下降量
连接初始点 s0 及 s1, s2 的单折线近似最优曲线,在该折线上取点 s∗ 使 的单折线近似最优曲线 在该折线上取点 作为(2) 的解 sk . 得 s∗ 2 = ∆ k 作为
13
其中 s1是 Cauchy点 (由最速下降法产生的极小点 C.P.); 点 由最速下降法产生的极小点
s2 是牛顿点 (由牛顿方法产生的极小点 xkN+1 ). 由牛顿方法产生的极小点
Dennis和Mei(1979)提出双折线法 在牛顿方向上取一点 s3 ,连 和 提出双折线法,在牛顿方向上取一点 连 提出双折线法 作为(2) 的解 sk . 接 s1 和 s3 ,在该折线上取一点 s∗ ,使得 s∗ = ∆ k 作为 在该折线上取一点 使得
xk +1 = xk + sk ，
否则， 否则，
xk +1 = xk .
新的信赖域的大小取决于试探步的好坏，粗略地说， 新的信赖域的大小取决于试探步的好坏，粗略地说，如果 域的大小取决于试探步的好坏 试探步较好， 试探步较好， 在下一步信赖域扩大或保持不变， 在下一步信赖域扩大或保持不变， 否则减小信赖域. 否则减小信赖域.
两者连线与信赖域边界的交点取为 xk +1 ,即 xk +1 − xk = ∆ k ,当牛 即 当牛 顿步 skN 的长度小于 skN ≤ ∆ k 时, xk +1 取为牛顿点 xkN+1 .
T gk gk c s1 = sk = −α k g k , s2 = skN = − Bk−1 g k , α k = T . g k Bk g k
3.6 信赖域方法 ( Trust-Region Methods)
1. 基本思想 2. 线性搜索与信赖域方法的联系 3. 信赖域方法思想 4. 信赖域半径的选择 5. 信赖域算法 6. 信赖域方法的收敛性 7. 解信赖域子问题 8. 优化工具箱
1
信赖域方法和线性搜索方法是求解非线性优化问题的两 信赖域方法和线性搜索方法是求解非线性优化问题的两 类主要的数值方法.与线性搜索方法相比， 类主要的数值方法.与线性搜索方法相比，信赖域方法思想 新颖，具有可靠性，有效性和很强的收敛性. 新颖，具有可靠性，有效性和很强的收敛性.鉴于信赖域方 法的优点， 法的优点 ， 由它来构造新的优化方法成为非线性优化界许 多学者关注的焦点. 多学者关注的焦点. 单折线法； 单折线法； 双折线法; 双折线法; 切线折线法; 切线折线法; 信赖域自适应调整算法……… 信赖域自适应调整算法………
2
域方法的收敛性主要是基于试探步满足当 β1 = 1 时的不等
2
(6),为了降低计算的复杂度 人们并不精确求解(2), 为了降低计算的复杂度, (2),而 式(6),为了降低计算的复杂度,人们并不精确求解(2),而 是计算满足(6) (6)式的试探步 是计算满足(6)式的试探步 sk .
11
定义 1 是两常数, 满足(6)式和不等式: (6)式和不等式 设 β1 ∈ ( 0,1] ,η ≥ 0 是两常数,如果 sk ∈ R n 满足(6)式和不等式:
（2） ）
其中， 处的梯度， 对称， 其中，g k 是目标函数 f ( x) 在当前迭代点 xk 处的梯度，Bk ∈ R n×n 对称， 是 f ( x) 在 xk 处Hessian阵的近似 ∆ k 为信赖域半径 s 为待求变量 阵的近似. 为信赖域半径, 为待求变量. 阵的近似 变化时, 的解形成一条空间曲线, 称为最优曲线. 当 ∆ k 变化时 s 的解形成一条空间曲线 称为最优曲线 Powell [1970 ]给出了求解 给出了求解(2) 的单折线法 的单折线法, 给出了求解 可逆时,用 当 Bk 可逆时 用
Pred k = q ( k ) ( 0 ) − q ( k ) ( sk )
(3)
(4)
定义比值: 定义比值
Ared k rk = . Pred k
明接近程度越好. 明接近程度越好 因此，我们也用这个量来确定下次迭代的信赖域半径. 因此，我们也用这个量来确定下次迭代的信赖域半径
(5)
它衡量了二次模型与目标函数的逼近程度， 它衡量了二次模型与目标函数的逼近程度，rk 越接近于 1，表 ，
10
定理 1 二次模型子问题(2)中的精确解, 近似解, 二次模型子问题(2)中的精确解, 近似解, Cauchy 点均 (2)中的精确解 满足: 满足:
gk q ( 0 ) − q ( sk ) ≥ β1 g k min ∆ k , , Bk
(k ) (k )
（6）
其中, 其中, β1 ∈ ( 0,1] . (1975)给出 当 β1 = 1 时, s 所满足的不等式由 Powell(1975)给出,信赖 (1975)给出,
if rk < η1; if rk ∈ [η1 ,η2 ) ;
if rk ≥ η 2 .
8
5．信赖域算法 ．信赖域算法 Step6. 产生 Bk +1 ，校正 q( k ) ，令 k := k + 1, 转 Step 2. 很成功迭代: 很成功迭代 成功迭代: 成功迭代 不成功迭代: 不成功迭代 算法参数选择建议: 算法参数选择建议
6
4．信赖域半径的选择 ．信赖域半径的选择 (1). rk 越接近于 1， 表明接近程度越好.这时可以增大 ， 表明接近程度越好 这时可以增大 ∆ k 以扩大信 赖域 ; (2). rk > 0 但是不接近于 1, 保持 ∆ k 不变 ; (3). 如果 rk 接近于 0, 减小 ∆ k ,缩小信赖域 . 缩小信赖域 或者其它 ∆ k 的选择方法： 的选择方法： Satenaer(1997)研究了初始信赖域半径 ∆ 0 的选取对算法有效性 研究了初始信赖域半径 的影响, 给出了一个自动确定初始信赖域半径的ITRR算法 其基本 算法, 的影响 给出了一个自动确定初始信赖域半径的 算法 思想是通过二次近似模型和目标函数沿负梯度方向的近似程度, 二次近似模型和目标函数沿负梯度方向的近似程度 思想是通过二次近似模型和目标函数沿负梯度方向的近似程度 调 节初始信赖域半径. 节初始信赖域半径 Zhang(2002)等同把这一思想应用到信赖域半径的自适应 等同把这一思想应用到信赖域半径的自适应. 等同把这一思想应用到信赖域半径的自适应
7
5．信赖域算法 ．信赖域算法 Step1. 给 出 初 始 点 x0 ， 信 赖 域 半 径 的 上 界 ∆ , ∆ 0 ∈ ( 0, ∆ ) , 0 ≤ ε ,
0 < η1 ≤ η 2 < 1, 0 < γ 1 ≤ 1 < γ 2 , k := 0 .
Step2. 如果 g k ≤ ε ,停止 停止. 停止 Step3. (近似 求解子问题 得到 sk . 近似)求解子问题 近似 求解子问题(2),得到 Step4. 计算 f ( xk + sk ) 和 rk .令 令