《最优化方法》课程教学资源（PPT课件）信赖域方法（刘二永）

信赖域方法

信赖域方法

信赖域方法 信赖域方法是求解最优化问题的另-类有效 方法其最初的设计思想可追溯至 Levenberg Marq粗对 Gauss- Newton法的修 线搜索方法是把一个复杂的最优化问题转化 成一系列简单的一维寻优问题狺赖域方法是把 最优化问题转化为一系列相对简单的局部寻优 问题

信赖域方法 信赖域方法是求解最优化问题的另一类有效 方法．其最初的设计思想可追溯至Levenberg Marquart 和 对Gauss－Newton法的修 正．线搜索方法是把一个复杂的最优化问题转化 成一系列简单的一维寻优问题．信赖域方法是把 最优化问题转化为一系列相对简单的局部寻优 问题．

基本思想 牛顿法的基本思想是在迭代点x附近用二次 函数逼近/x(S)=+8S sGs并以g()的 的极小点修正x得到k1=x+s 以上方法只能保证算法的局部收敛性,为了建 立总体收敛性算法,我们采用了线搜索技术虽然 这种策略是成功的但它有一个缺点,即没有进一 步利用二次模型

基本思想 牛顿法的基本思想是在迭代点 k x 附近用二次 函数逼近 ( ) ( ) , 2 1 f x q s f g s s G sk T T  k = k + k + 并以 q (s) k 的 的极小点 k s 修正 , k x 得到： . k 1 k k x = x + s + 以上方法只能保证算法的局部收敛性，为了建 立总体收敛性算法，我们采用了线搜索技术．虽然 这种策略是成功的，但它有一个缺点，即没有进一 步利用二次模型．

基本思想 牛顿法的基本思想是在迭代点x附近用二次 函数逼近/x(S)=+8S sGs并以g()的 的极小点修正x得到k1=x+s 以上方法只能保证算法的局部收敛性,为了建 立总体收敛性算法,我们采用了线搜索技术虽然 这种策略是成功的但它有一个缺点,即没有进一 步利用二次模型.信赖域方法是另一种新的保证 算法总体收敛的方法

基本思想 牛顿法的基本思想是在迭代点 k x 附近用二次 函数逼近 ( ) ( ) , 2 1 f x q s f g s s G sk T T  k = k + k + 并以 q (s) k 的 的极小点 k s 修正 , k x 得到： . k 1 k k x = x + s + 以上方法只能保证算法的局部收敛性，为了建 立总体收敛性算法，我们采用了线搜索技术．虽然 这种策略是成功的，但它有一个缺点，即没有进一 步利用二次模型．信赖域方法是另一种新的保证 算法总体收敛的方法．

信赖域方法的模型子问题 min q s)=f+g S+SBS (1) s t s‖≤△ k 其中=x-x28k=V(x)B是 Hesse v2f(x)的近似 △>0为信赖域半径阵

信赖域方法的模型子问题 ( ) (1) 2 1 min q s f g s s B sk T T k = k + k + k s.t s   其中 , ( ), k k k s = x − x g = f x Bk 是Hesse 阵 ( ) k f x 2  的近似   0 k 为信赖域半径．

注:(1)这种方法既具有牛顿法的快速局部收 敛性,又具有理想的总体收敛性 (2)不要求目标函数的Hese阵是正定的 (3)利用了二次模型来求修正量使得目标函数 的下降比线性搜索方法更有效 (4)由于步长受到使 Taylor展开式有效的信赖 域的限制故方法又称为有限步长法

注：(1) 这种方法既具有牛顿法的快速局部收 敛性，又具有理想的总体收敛性． (2) 不要求目标函数的Hesse阵是正定的． (3) 利用了二次模型来求修正量，使得目标函数 的下降比线性搜索方法更有效． (4) 由于步长受到使Taylor展开式有效的信赖 域的限制，故方法又称为有限步长法．

信赖域半径的选择 根据模型函数q(s)对目标函数f(x)的拟合程度 来调整信赖城半径△ 对于问题(1)的解Sk2定义比值 Ared,f(*)-f+s) Predk qkd -qk 它衡量模型函数叭()与目标函数/(的致性 程度

信赖域半径的选择 根据模型函数 q (s) k 对目标函数 f (x) 的拟合程度 来调整信赖域半径 . k 对于问题(1)的解 , k s 定义比值： ( ) ( ) ( ) ( ) k k k k k k k k k q q s f x f x s Pred Ared r − − + = = 0 它衡量模型函数 q (s) k 与目标函数 f (x) 的一致性 程度．

注:(1)越接近于1表明模型函数与目标 函数的致性程度越好可以增大Δ以扩大 信赖域 (2)>0不接近于1可以保持△不变 (3)κk接近于零或取负值,表明模型函数与目标 函数的致性程度不好可以减小△以缩小 信赖域

注：(1) k r 越接近于１，表明模型函数与目标 函数的一致性程度越好，可以增大 k 以扩大 信赖域． (2) rk  0 不接近于１，可以保持 k 不变． (3) k r 接近于零或取负值，表明模型函数与目标 函数的一致性程度不好，可以减小 k 以缩小 信赖域．

信赖域算法 Step1:给出x∈R",信赖域半径的上界AA0=(0,△ E≥0,0<7≤72<10<%1<1<y2k=0 step2:如果gk≤e停止 Step3:求解子问题(1)得到sk step4:计算f(xk+sA)和;令 」xk+S 71 k+1 others

信赖域算法 Step1: 给出 , 0 n x  R 信赖域半径的上界 , (0, ),  0 =  0,0 1,0 1 , 0.   1 2    1    2 k = Step2: 如果  , gk 停止． Step3: 求解子问题(1)得到 . k s Step4: 计算 ( ) k k f x + s 和 , k r 令：    +  + = x others x s r x k k k k k 1 1 

Step5:校正信赖域半径,令 k+1 0.y1△ k n71 k+1 k2k A∈(△,min2△A2△) step6:产生B1,校正q,令k=k+1,转Step2 注:参数建议取 71=0.01,72=0.75,1=0.5,y2=2,△o=1

Step5: 校正信赖域半径，令： ( )   (  ) 1 2 2 1 1 1 2 1 1 1 ,min , , [ , ) 0,                       + + + k k k k k k k k k k k r r r Step6: 产生 , Bk+1 校正 , qk 令 k = k +1, 转Step2 注：参数建议取： 1 = 0.01,2 = 0.75, 1 = 0.5, 2 = 2,0 =1