分析一类新的自适应信赖域算法
来源：UC论文网2015-11-30 20:31
摘要：
导读:：对无约束优化问题提出一种类似带记忆的自适应信赖域算法，迭代过程中利用前面得到的迭代点的导数的信息自动产生一个信赖域半径。在一定的条件下，证明了算法的收敛性，
导读:：对无约束优化问题提出一种类似带记忆的自适应信赖域算法，迭代过程中利用前面得到的迭代点的导数的信息自动产生一个信赖域半径。在一定的条件下，证明了算法的收敛性，并通过数值实验验证了算法的有效性。
论文关键词：无约束优化，自适应信赖域算法，全局收敛性
1 引言
考虑无约束优化问题：
，其中
是二次连续可微函数。传统的信赖域[1]是一种迭代的方法，每次迭代要求计算如下信赖域子问题:
（1）
其中
，
是近似于Hessian阵
的对称矩阵，
是信赖域半径。
传统的信赖域算法都是根据实际下降量与预测下降量的比值比值来控制信赖域半径的变化[1]，这样可能会增加算法的计算量。基于此，许多自适应信赖域算法[1-6]被提出。其中Sartenaer[2]，张[3-4]都提出依赖于目标函数的一阶梯度及二阶Hessian矩阵(或其近似矩阵)的无记忆型信赖域半径选取机制。这类无记忆信赖域迭代由于缺乏更全局的信息，可能会使收敛过程过早地陷入局部极小点。本文基于这类记忆性的信赖域方法，提出一种全新的半径构造机制，提出了一种无约束问题的自适应信赖域算法。
2 非单调自适应信赖域算法
具体算法如下：
算法2.1 （非单调自适应信赖域算法）
步1 给定
，
，
，
，
，
，
。
步2 若
则终止算法。
步3 令
全局收敛性，
=
，
，计算信赖半径
求解子问题(1.2)得到试探步
，计算
。
步4 若
，则
；否则
转步2。
步5 修正，，
，转步2。
3 算法的收敛性分析
假设3.1（
）：对任意的
，存在有节有界闭集
使得
、
。
（
）：对
，
使得：
成立，且
也成立。
引理3.2[1]
引理3.3[1]
引理3.3[5] 算法是适定的，即算法2.1中步2与步4间的循环是有限的。
定理3.4 若假设3.1成立且
则算法有限终止于某个
或产生无穷点列使得：
证明若结论不成立，即
，则对任意，存在
使得
。则
由算法2.1步4可得：
。
故可得
，而
是收敛的，故有
，类似[5]中的定理3.7可得：与算法的是适定的矛盾的。故结论成立。证毕！
参考文献
[1]袁亚湘，孙文瑜.最优化理论与方法［Ｍ］.北京：科学出版社，1997.
[2]Sartenaer.A. Automaticdetermination of an initial trust region in nonlinear programming [J], SIAMJournal on Scientific Computing, 1997, 18 (5): 1788-1803.
[3]Zhang.X.S, Chen.Z.W and Liao.L.Z.A self-adaptive trust region method for unconstrained optimization [J],Oper.Res.Trans, 2001, 5 (2): 53-62.
[4]Zhang.X.S, Zhang.J.L and Liao.Z. Anadaptive trust region method and its convergence [J], Science in China (Series A), 2002, 45 (4): 620-631.
[5]李树君，张红霞。无约束优化问题的非单调自适应信赖域算法[J].长沙交通学院学报，2008，24(1):843 -848.
论文关键词：无约束优化，自适应信赖域算法，全局收敛性
1 引言
考虑无约束优化问题：
，其中是二次连续可微函数。传统的信赖域[1]是一种迭代的方法，每次迭代要求计算如下信赖域子问题: （1）其中
，是近似于Hessian阵的对称矩阵，是信赖域半径。传统的信赖域算法都是根据实际下降量与预测下降量的比值比值来控制信赖域半径的变化[1]，这样可能会增加算法的计算量。基于此，许多自适应信赖域算法[1-6]被提出。其中Sartenaer[2]，张[3-4]都提出依赖于目标函数的一阶梯度及二阶Hessian矩阵(或其近似矩阵)的无记忆型信赖域半径选取机制。这类无记忆信赖域迭代由于缺乏更全局的信息，可能会使收敛过程过早地陷入局部极小点。本文基于这类记忆性的信赖域方法，提出一种全新的半径构造机制，提出了一种无约束问题的自适应信赖域算法。
2 非单调自适应信赖域算法
具体算法如下：
算法2.1 （非单调自适应信赖域算法）
步1 给定
，，，，，，。步2 若
则终止算法。步3 令
全局收敛性，=，，计算信赖半径求解子问题(1.2)得到试探步，计算。步4 若
，则；否则 转步2。步5 修正
，，，转步2。3 算法的收敛性分析
假设3.1（
）：对任意的，存在有节有界闭集使得、。（
）：对，使得：成立，且也成立。引理3.2[1]
引理3.3[1]
引理3.3[5] 算法是适定的，即算法2.1中步2与步4间的循环是有限的。
定理3.4 若假设3.1成立且
则算法有限终止于某个或产生无穷点列使得：证明若结论不成立，即
，则对任意，存在使得。则由算法2.1步4可得：
。故可得
，而是收敛的，故有，类似[5]中的定理3.7可得：与算法的是适定的矛盾的。故结论成立。证毕！参考文献
[1]袁亚湘，孙文瑜.最优化理论与方法［Ｍ］.北京：科学出版社，1997.
[2]Sartenaer.A. Automaticdetermination of an initial trust region in nonlinear programming [J], SIAMJournal on Scientific Computing, 1997, 18 (5): 1788-1803.
[3]Zhang.X.S, Chen.Z.W and Liao.L.Z.A self-adaptive trust region method for unconstrained optimization [J],Oper.Res.Trans, 2001, 5 (2): 53-62.
[4]Zhang.X.S, Zhang.J.L and Liao.Z. Anadaptive trust region method and its convergence [J], Science in China (Series A), 2002, 45 (4): 620-631.
[5]李树君，张红霞。无约束优化问题的非单调自适应信赖域算法[J].长沙交通学院学报，2008，24(1):843 -848.
