当前位置：文档之家 › 第8讲信赖域方法

第8讲信赖域方法

  • 格式：ppt
  • 大小：765.50 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

信赖域算法非线性优化问题课件

信赖域算法非线性优化问题课件

非ห้องสมุดไป่ตู้性优化问题的求解方法
总结词
非线性优化问题的求解方法主要包括梯度法、牛顿法、 拟牛顿法、共轭梯度法等。此外，还有一些启发式算 法如模拟退火、遗传算法等也被广泛应用于求解非线 性优化问题。
详细描述
梯度法是最早用于求解非线性优化问题的方法之一， 其基本思想是沿着目标函数的负梯度方向搜索。牛顿 法基于泰勒级数展开，构造一个二次模型逼近目标函 数，并在此基础上求解极小值。拟牛顿法是牛顿法的 改进，通过构造一个正定的拟牛顿矩阵来逼近海森矩 阵。共轭梯度法结合了梯度法和牛顿法的思想，在每 一步迭代中沿着当前搜索方向的前一方向共轭的方向 进行搜索。
可解释性与透明度
研究如何提高信赖域算法的可解释性和透明度，使其在关键领域（如 医疗、金融等）得到更广泛的应用。
信赖域算法的挑战和机遇
挑战
非线性、非凸、大规模、多模态等复杂优化问题对信赖域算法提出了更高的要求。同时，算法的稳定性和收敛速 度也是需要克服的难题。
机遇
随着计算能力的提升和算法理论的不断发展，信赖域算法有望在更多领域发挥重要作用。例如，在数据科学、机 器学习、人工智能、控制系统等领域，信赖域算法具有广阔的应用前景。同时，与其他先进技术的结合也为信赖 域算法的发展提供了新的机遇。
信赖域算法的未来发展
深度学习与机器学习集成
探索将信赖域算法与深度学习、机器学习等先进技术相结合，以解决 复杂、高维的非线性优化问题。
智能优化
结合人工智能和优化算法，开发能够自适应学习和进化的智能优化系 统。
强化学习与优化算法结合
利用强化学习中的智能体与环境交互学习的特点，与信赖域算法结合， 实现更高效的优化。
• 可以处理约束优化问题。
信赖域算法的优缺点

【课件】运筹学与最优化方法(华南理工)第3章(07-4)

【课件】运筹学与最优化方法(华南理工)第3章(07-4)

的最优解S(k)和最优值
(k +1) (k ) (k )
q(S(k) )
(k + 1) (k )
) f (X = X + S 若 f (X (3)令 X 取 X * = X (k+1) ,停止,否则转(4) (4)计算 f = f (X (k) ) f (X (k+1) ), q = f (X (k) ) q(S(k) ) 1/ 2k ..若 f < 0.1q 令
第三章
无约束非线性规划
3.4 信赖域法, Matlab解无约束非线性规划
一.信赖域法: 1.思想: 1) 前两节方法的结构原理为用二次模型产生下降方 向,在下降方向上确定可接受的步长,得到新迭代点. 若二次模型不近似原目标函数,则在搜索方向上无 法找到满意的下降迭代点. 能否先指定步长的界,再用二次模型确定方向和步 长? *注:保证在下近似,可使f(x)与 二次模
y(1) = x +α(x xmax )
2 扩展:给定扩展系数 >1,计算.(加速) 扩展:给定扩展系数γ 计算.(加速) 计算.(加速
y(2) = x +γ ( y(1) x)
3.5 直接算法
一, 2,改进单纯形法: (续) ,改进单纯形法: (1)若f(y(1))<f(x min), 则 若 那么y 取代x 否则, 取代x 若f(y(1))> f(y(2)), 那么 (2)取代 max; 否则, y(1)取代 max (2)若max{f(x(i))| x(i) ≠x max } ≥ f(y(1)) ≥ f(x min), y(1)取代 max . 取代x 若 3° 收缩:若f(x max )> f(y(1)) > f(x(i)), x(i) ≠x max ,计算 ° 收缩: 计算

6.2无约束优化(信赖域)

6.2无约束优化(信赖域)
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
无约束优化：信赖域法
Trust Region Methods for Unconstrained Optimization
第 6 章 无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
信赖域法的动机
Taylor展式： 信赖域(trust region)：使得Taylor展式(模型)有效的区域 其中 是信赖域半径. 信赖域子问题： 设信赖域子问题的解为 s(k)，根据 f(k)- f (x(k) + s(k)) 和 的吻合程度调整半径 真实下降量： 预计下降量： 定义
第 6 章 无约束优化：信赖域法
来度量
逼近
数学规划基础
的程度
LHY-SMSS-BUAA
一个原型算法
解的刻画/精确算法 Cauchy点/近似算法 收敛性(了解即可)
第 6 章 无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
一个信赖域原型算法
模型函数是二阶Taylor展式 精确求解子问题 特定的信赖域半径更新方式
s ≤∆ k
1 2
s T B ( k ) s + g ( k )T s + f ( k )
第 6 章 无约束优化：信赖域法
数学规划基础

第五章Chapter5-信赖域方法

第五章Chapter5-信赖域方法

Lingfeng NIU, FEDS
Chapter V
11/63
Outline of the Trust-Region Approach
Define the ratio ρk =
Lingfeng NIU, FEDS
Chapter V
7/63
Outline of the Trust-Region Approach
To obtain each step, we seek a solution of the subproblem 1 T minn mk (p) = fk + gk p + p T Bk p, p∈ 2 where ∆k > 0 is the trust-region radius. s.t. p ≤ ∆k , (3)
Lingfeng NIU, FEDS
Chapter V
9/63
Outline of the Trust-Region Approach
The size of the trust region is critical to the effectiveness of each step. If the region is too small, the algorithm misses an opportunity to take a substantial step that will move it much closer to the minimizer of the objective function. If too large, the minimizer of the model may be far from the minimizer of the objective function in the region, so we may have to reduce the size of the region and try again.

第8讲信赖域方法

第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
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 .令 令
xk + sk , if rk ≥ η1 . xk +1 = or. xk ,
Step5.校正信赖域半径 令 校正信赖域半径.令 校正信赖域半径
∆ k +1 ∈ ∆ k , min {γ 2 ∆ k , ∆}
∆ k +1 ∈ ( 0, γ 1∆ k ] ∆ k +1 ∈ [γ 1∆ k , ∆ k ]
if rk < η1; if rk ∈ [η1 ,η2 ) ;
if rk ≥ η 2 .
8
5．信赖域算法 ．信赖域算法 Step6. 产生 Bk +1 ，校正 q( k ) ，令 k := k + 1, 转 Step 2. 很成功迭代: 很成功迭代 成功迭代: 成功迭代 不成功迭代: 不成功迭代 算法参数选择建议: 算法参数选择建议

一种求解信赖域子问题的精确解法

一种求解信赖域子问题的精确解法

一种求解信赖域子问题的精确解法王希云;李亮;于海波【摘要】在Hessian矩阵正定的前提下,首先利用线性插值构造了一条折线,并利用该折线提出了一种求解信赖域子问题的精确求解方法,称为分段折线法.并且证明了分段折线路径的合理性,最后分别通过与牛顿法、单折线法、双折线法和切线单折线法的数值实验作比较,数值结果表明新算法是有效且可行的.【期刊名称】《宁夏师范学院学报》【年(卷),期】2013(034)006【总页数】5页(P16-20)【关键词】信赖域子问题;最优曲线;精确解法;分段折线法【作者】王希云;李亮;于海波【作者单位】太原科技大学应用科学学院,山西太原030024;太原科技大学应用科学学院,山西太原030024;太原科技大学应用科学学院,山西太原030024【正文语种】中文【中图分类】O221信赖域方法的关键就是每步迭代时都需求解下面形式的信赖域子问题:其中g∈Rn为目标函数在当前迭代点的梯度，B∈Rn×n为目标函数在当前迭代点的Hessian矩阵或其近似，Δ∈R为信赖域半径，δ∈Rn为待求变量.当Δ变化时，上述信赖域子问题(1)的解δ*形成一条空间曲线，称为最优曲线［1］.目前关于求解信赖域子问题(1)的方法有很多，比如常见的有精确求解方法、折线法与截断共轭梯度法［2］.其中折线法较为普遍，如单折线法、双折线法、切线单折线法、不定折线法、混合折线法、双割线折线法等［3-7］.而精确求解方法目前提出的主要是牛顿法，本文根据文献［2］中精确求解方法的思想，利用分段线性插值的方法，提出了一种新的求解信赖域子问题的精确求解方法，称为分段折线法.1 基础知识定理1［3］δ*是子问题(1)的解，当且仅当存在μ*≥0，使得而且(B+μ*Ⅰ)是半正定矩阵.由定理1可知，信赖域子问题的精确求解方法的思想是解如下方程组当μ=0时，信赖域子问题(1)的解δ*=-B-1g;当μ＞0时，则是通过求解一元非线性方程‖ (B+ μⅠ)-1g‖2- Δ =0，得到解μ*，然后把μ*代入(2)的第一个方程，则可以求出信赖域子问题(1)的解δ*=-(B+ μ*Ⅰ)-1g.牛顿法的思想:在求解信赖域子问题(1)的解δ*，即(2)的解时，当μ =0时，则δ*=-B-1g;当μ ＞0时，定义函数φ(μ)，而函数φ(μ)是严格单调增加的凹函数［3］，然后利用牛顿法求方程φ(μ)=0的近似根μ*，从而求出子问题(1)的解δ*=-(B+μ*I)-1g.牛顿法的缺点:初始迭代点μ0不好选取.因为利用牛顿法求方程φ(μ)=0的近似根μ*时，只有当初始迭代点μ0充分接近方程φ(μ)=0的精确根时所求得的近似根μ*才较准确.但方程φ(μ)=0的精确根不知道，因此，如果选取的初始迭代点μ0离方程φ(μ)=0的精确根很远时，则可能会导致所求得的近似根μ*与方程φ(μ)=0的精确根误差很大，从而导致求得的解δ*=-(B+μ*I)-1g不是信赖域子问题(1)的最优解.本文提出的分段折线法则有效避免了初始迭代点μ0选取范围的限制，从而提高了计算效率.数值实验表明，对给定的信赖域半径Δ，当选取的初始迭代点μ0非常接近方程φ(μ)=0的精确根时，分段折线法求得的信赖域子问题的最优解的函数值与牛顿法求得的最优解的函数值误差很小，而且比单折线，双折线，切线单折线的效果要好.2 分段折线法的思想根据信赖域子问题精确求解方法的思想，可以得到最优曲线的参数方程如下定义函数则信赖域子问题(1)的解δ*就是:当自变量μ=0时，解δ*=-B-1g;当μ＞0时，则通过求解一元非线性方程f(μ)-Δ=‖ -(B+μI)-1g‖2-Δ=0得到解μ*，此时解δ*=-(B+μ*I)-1g.由文献［3］可知函数f(μ) =‖ -(B+μI)-1g‖2是关于μ的连续单调减函数，而且当μ→+∞时，f(μ)→0.所以，当给定的信赖域半径Δ≥‖B-1g‖2时，令μ=μ0=0，则信赖域子问题(1)的最优解δ*=-B-1g;当给定的信赖域半径Δ＜‖B-1g‖2时，对任意给定的步长h ＞ 0，令μ = μk=kh，(k=1，2，3，…)，则肯定存在最小的正整数M，使得f(μM)-Δ＜0，从而得到了方程f(μ)- Δ =0的有根区间为［0，μM］.记节点μk=kh 处的函数值f(μk)为 yk，称(μk，yk)为插值节点(k=0，1，…，M).对节点(μk，yk)(k=0，1，…，M)进行线性插值［8］构造M条直线，每条直线的方程记为Lk(μ)(k=1，…，M).然后把这M条直线连接起来就构成折线y0y1…ykyk+1…yM-1yM，这里记折线y0y1…ykyk+1…yM-1yM为Γ，称Γ为分段折线.最后采用分段折线Γ在插值点(μM-1，yM-1)和(μM，yM)之间利用线性插值所构造的直线函数LM(μ)代替函数f(μ)来求解原方程f(μ)-Δ =0的根μ*，从而求出信赖域子问题(1)的解δ*=-(B+μ*I)-1g.这种做法相当于把非线性程度高的方程f(μ)- Δ =0在每个小区间［μk，μk+1］，(k=0，1，…，M-1)上转化为线性方程来求解δ*，进而大大降低了求解的难度，而且具有很好的数值结果.3 分段折线法的几何意义通过上述讨论，可以作出分段折线法的几何图形如下面的图1所示［9］图1 分段折线法的图示4 算法下面给出算法的具体步骤步1给定梯度g，正定矩阵B，信赖域半径Δ，任意步长h.步2 计算f(μ0)，μ0=0，令y0=f(μ0).如果y0≤ Δ，取δ*=-B-1g，停止计算.否则令k:=1转步3.步3 计算f(μk)，μk=kh，令yk=f(μk).在插值节点(μk-1，yk-1)和(μk，yk)之间用线性插值方法构造直线Lk(μ)，形成分段折线Γ.步4 如果yk≤Δ，取δ*=-(B+ μ*I)-1g，停止计算.其中否则，令k:=k+1，转步 3.5 分段折线路径的性质分析定理2 记4中算法中所构造的分段折线Γ为则L(μ)满足(a)L(μ)关于μ为连续单调减函数.(b)对任意给定的信赖域半径Δ＜‖-B-1g‖2，则一定存在μM，使得L(μM)-Δ ＜0. 证明由f(μ)的单调性及L(μ)的构造可知(a)显然成立.再由零点存在定理知(b)成立.证毕.定理2表明，对任意给定的信赖域半径Δ＜‖ -B-1g‖2，方程L(μ)-Δ =0的根存在且唯一.6 数值结果对给定的测试函数1和测试函数2的信赖域子问题，对于不同的信赖域半径Δ，取h=0.01，将4中算法利用MATLAB进行了数值实验.并用该算法求得的相关数据分别与牛顿法、单折线法、双折线法和切线单折线法求得的相关数据进行比较，数值结果分别列在表1、表2、表3和表4中，其中Δ 表示信赖域半径，fPDL、fNEW、fSDL、fDDL和 fTDL分别表示分段折线法、牛顿法、单折线法、双折线法和切线单折线法求得的测试函数最优解的函数值.测试函数为从下表1的数值结果可以看出，当信赖域半径Δ≥‖B-1g‖2(见文献［4］)时，分段折线法与牛顿法所求得的测试函数最优解的函数值相同;当信赖域半径Δ＜‖B-1g‖2时，分段折线法与牛顿法求得的测试函数最优解的函数值的误差非常小.从下表2和表3的数值结果可以看出，当信赖域半径Δ≥‖B-1g‖2时，分段折线法与单折线法和双折线法的效果一样;当信赖域半径Δ＜‖B-1g‖2时，分段折线法比单折线法和双折线法要好，而且当信赖域半径Δ接近‖δcp‖2(见文献［4］)附近时，分段折线法比单折线法和双折线法要好得多.表1 数值结果1Δ fPDL fNEW fPDL-fNEW (10-4 Function 1 0.4 -10.923 868 028 -10.923 868 045 0.)000 170 000 1.8 -43.701 194 676 -43.701 198 920 0.042 440 000 3.0 -66.220 757 441 -66.220 766 109 0.086 680 000 5.6 -101.259 485 330 -101.259 562 689 0.773 590 000 7.0 -113.387 596 114 -113.387 692 318 0.962 040 000 10.0 -124.900 770 548 -124.900 806 441 0.358 930 000 Δ ≥ 10.31 -125.000 000 000 -125.000 000 000 0.000 000 000002 640 000 1.5 -7.977 595 666 -7.977 603 395 0.077 290 000 3.0 -12.154 479 276 -12.154 561 029 0.817 530 000 4.0 -13.543 248 294 -13.543 632 283 3.839 890 000 6.0 -15.136 592 354 -15.138 043 834 14.514 800 000 10.0 -16.445 491 393 -16.445 884 807 3.934 140 000 Δ ≥ 11.05 -16.500 000 000 -16.500 000 000 0.Function 2 0.5 -3.118 073 116 -3.118 073 380 0.000 000 000从表4的数值结果可以看出，当信赖域半径Δ =‖δzp‖2(见文献［4］)时，分段折线法要明显优于切线单折线法;当信赖域半径Δ≥‖B-1g‖2时，分段折线法与切线单折线法求得的最优解的函数值相同;而对于其它给定的信赖域半径Δ分段折线法要稍微好于切线单折线法.表2 数值结果2Δ fPDL fNEW fPDL-fNEW (10-4)010 159 529 1.8 -43.701 194 676 -42.811 688 245 -0.889 506 431 2.83 -63.301 488 609 -60.022 237 630 -3.279 250 979 3.0 -66.220 757 441 -62.352 813 742 -3.867 943 699 5.65 -101.769 855 936 -79.999 882 548 -21.769 973 388 5.66 -101.871 284 560 -89.599 048 124 -12.272 236 436 5.68 -102.073 278 945 -89.911 928 099 -12.161 350 846 7.0 -113.387 596 114 -107.309 781 904 -6.077 814 210 10.0 -124.900 770 548 -124.849 370 263 -0.051 400 285 Δ ≥ 10.31 -125.000 000 000 -125.000 000 000 0.000 000 000 Function 1 0.4 -10.923 868 028 -10.913 708 499 -0.002 860 039 2.0 -9.749 596 265 -9.594 185 643 -0.155 410 622 3.0 -12.154 479 276 -11.524 611 797 -0.629 867 479 3.38 -12.764 916 981 -11.757 080 403 -1.007 836 578 3.49 -12.919 891 411 -11.772 869 502 -1.147 021 909 3.51 -12.947 180 026 -11.773 255 803 -1.173 924 223 3.53 -12.974 311 694 5.205 141 180 -18.179 452 874 4.0 -13.543 248 294 1.886 019 370 -15.429 267 664 6.0 -15.136 592 354 -7.732 689 943 -7.403902 411 9.0 -16.287 271 922 -15.116 755 421 -1.170 516 501 Δ ≥11.05 -16.500 000 000 -16.500 000 000 0.Function 2 0.5 -3.118 073 116 -3.115 213 077 -0.000 000 000表3 数值结果3Δ fPDL fNEW fPDL-fNEW (10-4)010 159 529 1.8 -43.701 194 676 -42.811 688 454 -0.889 506 222 2.83 -63.301 488 609 -60.022 237 630 -3.279 250 979 3.0 -66.220 757 441 -62.352 813 742 -3.867 943 699 5.65 -101.769 855 936 -79.999 882 582 -21.769 973 388 5.66 -101.871 284 560 -80.313 006 513 -21.558 278 047 5.67 -101.972 406 011 -81.262 021 961 -20.710 384 050 6.0 -105.180 136 680 -98.011 341 148 -7.168 795 531 7.34 -115.669 715 725 -114.632 000 000 -1.037 715 725 10.0 -124.900 770 548 -114.632 000 000 -10.268 770 548 Δ ≥ 10.31 -125.000 000 000 -125.000 000 000 -0.000 000 000 Function 1 0.4 -10.923 868 028 -10.913 708 499 -0.002 860 039 1.5 -7.977 595 666 -7.912 305 899 -0.065 289 767 3.0 -12.154 479 276 -11.524 611 797 -0.629 867 479 3.38 -12.764 916 981 -11.757 080 403 -1.007 836 578 3.49 -12.919 891 411 -11.772 869 502 -1.147 021 909 3.51 -12.947 180 026 -11.773 255 803 -1.173 924 223 3.53 -12.974 311 694 -12.023 539 017 -0.950 772 677 4.0 -13.543 248 294 -13.296 578 075 -0.246 670 219 6.0 -15.136 592 354 -14.977 358 622 -0.159 233 732 8.51 -16.174 377 749 -15.633 144 207 -0.541 233 542 9.0 -16.287 271 922 -15.633 396 922 -0.653 875 000 10.0 -16.445 491 393 -15.633 396 922 -0.812 094 471 Δ ≥11.05 -16.500 000 000 -16.500 000 000 -0.Function 2 0.5 -3.118 073 116 -3.115 213 077 -0.000 000 000表4 数值结果4Δ fPDL fNEW fPDL-fNEW (10-4)010 159 529 1.8 -43.701 194 676 -42.811 688 245 -0.889 506 431 2.83 -63.301 488 609 -60.034 008 146-3.267 480 463 4 -81.752 007 732 -80.915 320 937 -0.836 686 795 5 -94.675 250 520 -94.398 311 038 -0.276 939 482 5.66 -101.871 284 560 -101.741 707 624 -0.129 576 936 7.0 -113.387 596 114 -113.365 196 513 -0.022 399 601 10.0 -124.900 770 548 -124.900 805 570 0.000 350 220 Δ ≥ 10.31 -125.000 000 000 -125.000 000 000 0.000 000 000 Function 1 0.4 -10.923 868 028 -10.913 708 499 -0.002 860 039 1.5 -7.977 595 666 -7.912 305 899 -0.065 289 767 3.0 -12.154 479 276 -11.524 611 797 -0.629 867 479 3.38 -12.764 916 981 -11.757 080 403 -1.007 836 578 3.51 -12.947 180 026 -12.272 688 840 -0.674 491 186 4.0 -13.543 248 294 -13.216 785 622 -0.326 462 672 6.0 -15.136 592 354 -15.044 790 399 -0.091 801 955 9.0 -16.287 271 922 -16.276 841 769 -0.010 430 153 10.0 -16.445 491 393 -16.442 443 942 -0.003 047 451 Δ ≥ 11.05 -16.500 000 000 -16.500 000 000 0.Function 2 0.5 -3.118 073 116 -3.115 213 077 -0.000 000 000以上结果表明分段折线法是一种很好的求解信赖域子问题的精确求解方法.其中对于测试函数Function 1，‖B-1g‖2=10.31，‖δcp‖2=5.66，‖δzp‖2=2.83，测试函数Function 2，‖B-1g‖2=11.05，‖δcp‖2=3.51，‖δzp‖2=3.38.参考文献:【相关文献】［1］徐成贤，陈志平，李乃成.近代优化方法［M］.北京:科学出版社，2002.［2］李董辉，童小娇，万中.数值最优化算法与理论［M］.北京:科学出版社，2010.［3］袁亚湘，孙文瑜.最优化理论与方法［M］.北京:科学出版社，2007.［4］赵英良，徐成贤.解信赖域子问题的切线单折线法［J］.数值计算与计算机应用，2000，21(1):77-80.［5］ CHEN Jun，SUN Wen-yu.Nonmonotone Adaptive Trust Region Algorithms with Inde-finite Dogleg Path for Unconstrained Minimization［J］.Northeast Math，2008，24(1):19-30.［6］赵丹.解信赖域子问题的混合折线法［J］.徐州师范大学学报:自然科学版，2009，27(3):38-41.［7］王希云，邵安.一种双割线折线法求解信赖域子问题［J］.应用数学，2012，25(2):419-424. ［8］颜庆津.数值分析［M］.北京:北京航空航天大学出版社，2006.［9］任玉杰.数值分析及其MATLAB实现［M］.北京:高等教育出版社，2007.。

带回溯线搜索步的双子问题信赖域算法

带回溯线搜索步的双子问题信赖域算法唐明筠【摘要】无约束非线性优化问题广泛存在于工程、科学计算等实际应用领域.本文在信赖域算法的框架下提出无约束子问题,将它与信赖子问题相结合,构造了求解无约束优化问题的双子问题信赖域算法.同时利用信赖域子问题得到的试探步一定是目标函数充分下降方向的性质使得每次求解信赖域子问题之后均能得到使目标函数下降的步.在标准假设下证明了该算法具有全局收敛性和局部二次收敛速度.数值结果表明该算法比传统的信赖域算法速度更快更有效.【期刊名称】《工程数学学报》【年(卷),期】2010(027)004【总页数】10页(P627-636)【关键词】无约束优化;信赖域方法;双子问题;回溯;收敛性【作者】唐明筠【作者单位】中国农业大学理学院,北京100083【正文语种】中文【中图分类】O221.21 引言无约束优化是非线性最优化中的基本问题，它不但具有重要的理论意义，还在金融、工程、科学等许多领域都有着广泛的应用。

求解无约束优化问题的算法很多，信赖域方法就是其中一种非常有效的方法。

信赖域方法兴起于上个世纪七、八十年代，至今已建立了比较完善的框架和理论体系。

但有时候由于信赖域约束的影响，算法的迭代步过于保守。

比如当目标函数在一个比当前信赖域大很多的区域上凸时，可能需要很多步迭代才能使信赖域半径扩大到包含局部极小值点的区域。

为了尽量减少这种情况的产生我们设计了一个新的算法，力图在保持信赖域算法优越的收敛性的同时节省计算量和计算时间。

一方面，通过引入一个不要求信赖域约束的无约束子问题，我们可以求得一个步长为1的牛顿步。

根据模型函数的性质，我们选择求解信赖域子问题或者求解无约束问题。

另一方面，由于信赖域子问题得到的试探步一定是目标函数的充分下降方向，可以将信赖域与线搜索技巧相结合，在试探步失败时进行回溯的线搜索[1]。

2 无约束子问题和双子问题信赖域算法考虑无约束优化问题其中f是Rn上的实值二次连续可微函数，假设它是下方有界的。

一个新的带线性搜索的信赖域算法

一个新的带线性搜索的信赖域算法
蒋萍;王吉安
【期刊名称】《数学理论与应用》
【年(卷),期】2008(28)4
【摘要】本文对于无约束最优化问题提出了一个新的信赖域方法.在该算法中采用的是线性模型,并且当试探步不成功的时候,采用线性搜索,从而减少了计算量.文中证明了在适当的条件下算法的全局收敛性.
【总页数】4页(P76-79)
【作者】蒋萍;王吉安
【作者单位】中南大学数学科学与计算技术学院,长沙,410075;长沙理工大学数学与计算科学学院,长沙,410076
【正文语种】中文
【中图分类】O1
【相关文献】
1.等式约束下一个带线搜索的信赖域算法 [J], 李少娟;景书杰
2.基于简单锥模型的带线搜索的新信赖域算法 [J], 邢治业
3.一类新的带非单调线搜索的信赖域算法 [J], 曾宪廷
4.一个带线搜索的自适应信赖域算法 [J], 苗荣;景书杰
5.一个带不精确线性搜索的记忆梯度法 [J], 朱建伟
因版权原因，仅展示原文概要，查看原文内容请购买。

工程优化 信赖域方法



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

信赖域方法行业相关


2Mrk .
前面已经证明了lim k
rk
0，因此lim k
k
1.
另一方面，根据算法定义，当k
d12
d
2 2
s.t.d12
d
2 2
1
技术教学
15
5.例题讲解
得到子问题的K
T点，也是最优解d（1）
dd（ （1211） ）
0 1
函数值f（x（1） d（1）） 2，（1 d（1）） 2
实际下降量与预测下降量之比
1
f（x（1））- f（x（1） d（1））
f（x（1））-（1 d（1））
55-
2 2
3.信赖域算法
特点： 不要求目标函数的Hesse矩阵正定，在非正定的情况下也
能处理。 既有牛顿法的快速局部收敛性，也有理想的全局收敛性。 算法利用二次模型来修正步长，使得目标函数的下降比线
搜索方法更有效。 由于位移长度受到Taylor展开式有效的信赖域的限制，此
方法又称为有限步长法
技术教学
如果函数值实际下降量与预测下降量之比，即
k
f（x (k )）- f (x（k） d（k）)
f（x（k））- （k d（k））
太小，就认为逼近不成功，后继点仍取x（k），且信赖域半径rk1
1 2
rk；
若
比较大，则逼近成功，后
k
继点x（k
1）
x（k）
d（k），
且rk1 rk或rk1 2rk
技术教学
9
min：（k d）
f
(x(k)
)
f
(x(k)
)T
d
1 2
d T 2 f ( x（k)
)d
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

实际下降量(真实下降量):
Aredk f (xk ) f (xk sk )
(3)
称二次模型函数qk s的下降量(预测下降量)：
Predk qk 0 qk sk
(4)
定义比值:
rk
Aredk Predk
.
(5)
它衡量了二次模型与目标函数的逼近程度，rk 越接近于 1，表
明接近程度越好. 因此，我们也用这个量来确定下次迭代的信赖域半径.
Powell [1970 ]给出了求解(2) 的单折线法, 当 Bk 可逆时,用
连接初始点s0 及s1, s2 的单折线近似最优曲线,在该折线上取点s使 得 s 2 k 作为(2) 的解 sk .
13
其中s1是 Cauchy点 (由最速下降法产生的极小点 C.P.);
s2 是牛顿点
(由牛顿方法产生的极小点
22
[s,val,posdef,count,lambda] = TRUST(g(x),B,d) ; %TRUST是matlab自带的求解信赖域子问题的函数 利用它信赖域方法的程序就简单多了.
23
作业
P111. 习题7.
24
从点 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 满足下降性要求:
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 步的
否则，
xk1 xk sk ，
xk1 xk .
新的信赖域的大小取决于试探步的好坏，粗略地说，如果 试探步较好，在下一步信赖域扩大或保持不变，否则减小信赖域.
3
2．线性搜索与信赖域方法的联系 2.1 不同点: 与线性搜索方法相比，信赖域方法直接通过模型求解得到
试探步长，而不是先确定搜索方向，再寻找步长. 2.2 相同点: 线搜索方向可以看成是信赖域半径充分大时的信赖域步；
很成功迭代: 成功迭代: 不成功迭代:
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 是某个
f
(xk1())

)
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
正的常数. (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,
(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.
而信赖域方法所得出的试探步可看成是将二次逼近模型加上 一个惩罚项之后所导致的线搜索方向.
4
3．信赖域方法思想
设当前点 xk 的邻域定义为:
k x Rn x xk k
（1）
其中, k 称为信赖域半径. 目标函数在极值点附近近似一个二次函数，因此对于无约束
优化问题,利用二次逼近，构造如下信赖域子问题:
式(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 下降试探步.
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 ,连
算法的性态).
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 ), 其中, 为方程：
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 的解形成一条空间曲线, 称为最优曲线.
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 . 解二次方程:
定理 2 全局收敛性定理[袁亚湘，1994]
设函数 f (x)在 Rn上连续可微,如果1 0， Bk 2 M 对一切k 成立，则
对于 0信赖域算法必定经过有限次迭代后终止或者产生点列 xk 使 得:
lim
k
f
( xk
)
中必有一个成立.
lim
k
gk
0
2
12
7．解信赖域子问题 信赖域方法在每步迭代中求解下列形式的子问题:
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 :
xk 1
xk
xk
,
sk ,
if rk 1 .
or.
Step5.校正信赖域半径.令
k1 0,1k k1 1k , k