当前位置:
文档之家› 北航最优化方法作业答案uco_trustregion
北航最优化方法作业答案uco_trustregion
-保证方法具有大范围收敛性
理想特性: 在 x(k) 靠近局部解之前线搜索法用步长来限制 探搜索方向 p(k) 使 f(x) 获取充分下降; 而在 x(k)接近局部 解时, 该限制无效, 即步长为 1,迭代恢复为快速收敛的 基本牛顿法. 理想特性: 在 x(k) 靠近局部解之前信赖域法用信赖域约束 来限制探测步 s(k) 使 f(x) 获取充分下降; 而在 x(k)接近 局部解时, 该限制无效, 从而迭代恢复为快速收敛的基 本(即步长为 1)牛顿法.
基本信赖域法的收敛性
第 6 章 无约束优化:信赖域法 数学规划基础 LHY-SMSS-BUAA
Steihaug-Conjugate Gradient Method
min = q (s) :
s ≤∆ 1 2
s Bs + g s
T T
q(s)
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题:dog-leg法
min q ( k ) ( s ) = :
s ≤∆ k 1 2
s T G ( k ) s + g ( k )T s + f ( k )
⊙ 近似方法 :找 s(k) 使得 q(k) q(k) ⊙ dog-leg法(折线法),适合 G(k) 正定的问题 当 ∆ k 较小时, 柯西点较恰当 − g ( k ) 当 ∆ k 较大时, 牛顿步较恰当
第 6 章 无约束优化:信赖域法 数学规划基础 LHY-SMSS-BUAA
原型算法的收敛性
信赖域型牛顿法! 定理6.1.1 若算法6.1.1产生的序列 {x(k)}有界,且 f(x) 二次连 续可微. 则序列 {x(k)} 必有聚点 x*满足一阶和二阶最优性条 件,即 g*= 0 且 G* 半正定. 定理6.1.2 若定理6.1.1中的聚点 x*还满足二阶充分条件,即 g*= 0 且G*正定,则 (b) 对充分大的k,信赖域约束 收敛速度是二次的.
无约束优化:信赖域法
Trust Region Methods for Unconstrained Optimization
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
信赖域法的动机
Taylor展式: 信赖域(trust region):使得Taylor展式(模型)有效的区域 其中 是信赖域半径. 信赖域子问题: 设信赖域子问题的解为 s(k),根据 f(k)- f (x(k) + s(k)) 和 的吻合程度调整半径 真实下降量: 预计下降量: 定义
使得
正定,则
注2:当 B(k) = G(k)时,可以将牛顿型信赖域法理解成一种特殊的 修正牛顿法!
第 6 章 无约束优化:信赖域法 数学规划基础 LHY-SMSS-BUAA
精确求解信赖域子问题
2 范数信赖域子问题
除G(k)正定且牛顿步满足信赖域约束条件(此时牛顿 步为解)外,解均在信赖域边界取得,此种情况需要利用 牛顿法解关于标量 的方程,从而一次迭代需要做3-4个 Cholysky分解. --6.2.2小节--算法6.2.1
x ( k ) + sΝ
LM trajectory
s N = −(G ( k ) ) −1 g ( k )
ˆC x (k ) + s
x ( k ) ( s = 0)
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题: 共轭梯度法
= min q (s) :
s ≤∆ 1 2
第 6 章 无约束优化:信赖域法 数学规划基础
是非积极的,且
LHY-SMSS-BUAA
2范数信赖域子问题解的刻画
考虑 其中
注1:这里为了表述简洁和具有一般性,将二阶Taylor展式中的 Hessian阵替换成了B(k),并去掉了子问题中的迭代指标.
(1)
定理6.2.1 s*是问题(1)的全局解当且仅当存在 和 成立,且 半正定;另外,如果 s*是问题(1)的唯一解.
第 6 章 无约束优化:信赖域法
来度量
逼近
数学规划基础
的程度
LHY-SMSS-BUAA
一个原型算法
解的刻画/精确算法 Cauchy点/近似算法 收敛性(了解即可)
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
一个信赖域原型算法
模型函数是二阶Taylor展式 精确求解子问题 特定的信赖域半径更新方式
(a) p ( i )T Bp ( i ) ≤ 0
其中 τ 是二次方程
(b)
x ( i ) + α i p( i )
(i ) 2 2
s' 终止算法,返回信赖域边界上的点=
x
(i )
x ( i ) + τ p( i )
= ∆ 2 的某个根
2
≥∆
+α p
(k ) (k ) (k ) q ( s ) ≤ q ( s s' ≤ ∆ k ' 重要事实: C ), T (k ) ( k )T (k ) q ( k ) ( s) = : 1 s G s + g s + f 2
s ≤∆ k
1 2
s T B ( k ) s + g ( k )T s + f ( k )
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法-细节
参数的典型值
实用算法的参数选取更精细:如给信赖域的半径设定上界!
定理 (基本信赖域法的收敛性)
第 6 章 无约束优化:信赖域法
s ≤∆ 1 2
s B s+ g s
定理 假设应用初始点 x(0) = 0 的共轭梯度法来极小化二次函数 q(s),且对所有0 ≤ i ≤ k, 有 p(i)TB p(i) > 0,则下列不等式成立 x ( j ) < x ( j +1) , j =0, 1, , k − 1
2 2
引入两种新的终止情况:
⊙ 实践中,我们希望(并且能够)比这做得更好
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
近似标准-Cauchy点的图示
⊙ Cauchy点: 柯西点! q(k)(
trust region contours of q ( k )
(k ) sC
- g (k )
第 6 章 无约束优化:信赖域法 数学规划基础 LHY-SMSS-BUAA
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
Cauchy点与近似方法
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
近似标准-Cauchy点
要求近似解满足:模型在近似解处所获取的预测减少量不 比按最速下降迭代所获取的少! ⊙ Cauchy点: 在线段上极小化二次函数--非常容易! 柯西点! q(k)( ⊙ 要求所选的步s(k)满足 q(k)( q(k)( 算法即是全局收敛的!
sT Bs + gT s
问题: (i) B 不定时,可能有
( i )T (i )
p Bp = 0 p ( i )T Bp ( i ) < 0
(ii) 违反信赖域约束
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题:共轭梯度法 ( 续 ) T T
min = q( s) :
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
例
选取
子
,则
信赖域子问题为 求得牛顿步 有
第 6 章 无约束优化:信赖域法
所以解必在边界上!
数学规划基础 LHY-SMSS-BUAA
例
子(续)
Lagrange乘子法:
因为 因为
,所以 且 所以
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
线搜索法与信赖域法
trust region
line search directiቤተ መጻሕፍቲ ባይዱn
contours of q ( k )
trust region step
contours of f
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
线搜索法与信赖域法的作用
模型预测减少量的下界及全局收敛性
定理 (模型在柯西点处所获取的减少量). q(k)(s) q(k) 推论 q(k)(s) q(k)
第 6 章 无约束优化:信赖域法 数学规划基础 LHY-SMSS-BUAA
近似求解信赖域子问题
⊙ 近似方法 :找 s(k) 使得 q(k) q(k)
◇ dog-leg法(折线法)-解方程 ◇ 二维子空间极小化法 估计最小特征值+求解三次代数方程 ◇ Steihaug-共轭梯度法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法
需要解决的问题 一般性的参数设置 需要构造模型函数(二阶泰勒展式、一般的二次函数等、插值法) 子问题:近似算法 可由各种拟牛顿更新公式构造! 近似标准是什么?-Cauchy 点
第 6 章 无约束优化:信赖域法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法-描述
min q ( k ) ( s ) = :