一种求解二次模型信赖域子问题的Adams方法

王英慧，王希云

(太原科技大学 应用科学学院，太原 030024)



一种求解二次模型信赖域子问题的Adams方法

王英慧，王希云

(太原科技大学 应用科学学院，太原 030024)

摘要：针对最优曲线的微分方程模型，在Hessian矩阵正定的前提下，采用Adams显式二步公式构造一条折线，称为Adams折线，用其代替最优曲线，提出求解子问题的新算法——Adams算法。通过数值试验，表明Adams二步算法比切线单折线法具有明显的优势。

关键词：微分方程模型；信赖域子问题；Adams算法

信赖域方法实现的关键是每步迭代时要求解一个二次模型信赖域子问题，其形式如下：

s.t.‖δ‖2≤△

(1)

(1)中的各个参数表示的含义分别是：g∈Rn：目标函数在当前点的梯度(graidient)，B∈Rn×n：目标函数在当前点处的Hessian矩阵或者它的近似矩阵，△∈R：信赖域半径，δ∈Rn：要求的变量。当△发生变化时，子问题(1)的解δ*在空间形成一条曲线——最优曲线。

对于子问题(1)的求解，目前提出的方法主要有单折线法、双折线法、切线单折线法以及基于最优曲线微分方程模型的欧拉算法。本文主要讨论在微分方程模型基础上的解决子问题(1)的算法。针对最优曲线的参数方程，在Hessian矩阵正定的前提下，文献[1]中提出了一种微分方程模型，形式如下：

(2)

利用这个微分方程模型，文献[2-4]分别提出了求解二次模型信赖域子问题的欧拉算法和休恩算法，并取得了较好的实验结果。

1Adams折线法的思想及其构造

根据微分方程模型(2)，采用Adams显式二步公式[5]构造折线Γ，用Γ代替最优曲线来求解信赖域子问题(1)，提出求解子问题的新算法——Adams算法。在理论上给予了该算法的证明，并且通过实验验证了算法的有效性。

Adams显式二步公式如下：

(3)

其中：fn=-(B+μnI)-1δn，fn-1=-(B+μn-1I)-1δn-1，μn=nh.

(4)

注：为了使构造的折线满足引理6.4.1[6]，则步长h需满足下式：

(5)

2折线性质分析

定理1设B对称正定，且有：n=1,2,3,L,N-1时，下式成立。

(6)

则δ(τ)满足：

(1)‖δ(τ)‖2关于τ为单调减函数；

(2)q[δ(τ)]关于τ为单调增函数。

证明：(1)当τ∈[μ0,μ1]，即τ∈[0,h0]时:

则:

因为由式(5)可得:

所以：

因此，‖δ(τ)‖2在区间[μ0,μ1]上为单调减函数。

对∀τ∈(μi,μi+1)，即(τ-μi)∈(0,h),i=1,2,3,…,N-1时:

则:

因为由式(5)可得:

所以：

因此‖δ(τ)‖2在区间(μi,μi+1),i=1,2,3，…,N-1上为单调减函数。

(2)当τ∈[μ0,μ1]，即τ∈[0,h]时:

则:

所以q[δ(τ)]在区间[μ0,μ1]上关于τ为单调增函数。

对∀τ∈(μi,μi+1)，即(τ-μi)∈(0,h),i=1,2,3,…,N-1时：

[(3fi-fi-1)TB(3fi-fi-1)]

则:

由式(6)，得：

(q[δ(τ)])≥0,τ∈(μi,μi+1)

所以q[δ(τ)]在区间(μ1,μi+1)，i=1,2,3,…,N-1上关于τ为单调增函数。证毕。

3算法描述

步1：已知目标函数在当前迭代点的梯度是g，正定矩阵是B和信赖域半径△.

步2：令δ0=-B-1g，若△≥‖δ0‖2,则终止计算，得子问题的解δ*=δ0，否则，转步3.

4数值试验

对于附录中给定的的测试函数Funtion1和Funtion2对应的子问题(1)，取固定步长h=0.5，选取不同的信赖域半径△，利用MATLAB对Adams算法进行了数值实验，并将此实验结果与文献[7-8]中提出的切线单折线法的实验结果做了比较，结果见表1和表2.

通过观察表1和表2，发现：对于不同的信赖域半径，不管对Funtion1还是对Funtion2，都有q1-q2≤0，即：在靠近最优曲线的程度上，Adams折线表现的更好。对于Funtion1，当信赖域半径△落在‖δzp‖2附近时，Adams算法求得的近似最优解比切线单折线法明显要好；对于Funtion2，Adams算法求得的近似最优解也比切线单折线法要好，特别地，当信赖域半径△落在‖δzp‖2附近时，Adams算法求得的近似最优解比切线单折线法明显要好。当信赖域半径△≥‖B-1g‖2时，两种算法的实验结果一样。因此，本论文所构造的Adams算法也是一种有效的求解二次模型信赖域子问题(1)的折线法。对于测试函数1，‖δzp‖2=2.99，‖B-1g‖2=15.34.对于测试函数2，‖δzp‖2=3.64，‖B-1g‖2=11.00.

表1　测试函数1的数值结果

表2　测试函数2的数值结果

附录：测试函数

Funtion1:

Funtion2:

参考文献：

[1]王希云，李亮，于海波.解决信赖域子问题的隐式分段折线算法[J].应用数学和力学，2014，35(6)：610-619.

[2]王希云，李亮，张雅琦，等.一种求解二次函数模型信赖域子问题的分段切线法[J].应用数学，2015，28(1)：26-32.

[3]朱帅，李亮，王希云.一种求解二次模型信赖域子问题的新算法[J].西南民族大学学报，2014，40(1)：91-96.

[4]李亮，王希云，张雅琦，等.一种求解二次模型信赖域子问题的休恩算法[J].太原科技大学学报，2014，35(2)：151-155.

[5]林成森.数值计算方法[M].北京：科学出版社，2005.

[6]李董辉，童晓娇，万中.数值最优化算法与理论[M].北京：科学出版社，2010.

[7]赵英良，徐成贤.解决信赖域子问题的切线单折线法[J].数值计算与计算机应用，2000，21(1)：77-80.

[8]任玉杰.数值分析及其MATLAB实现[M].北京：高等教育出版社，2007.

Adams′s Algorithm for Solving Trust-region Subproblems with Quadratic Model

WANG Ying-hui，WANG Xi-yun

(School of Applied Science，Taiyuan University of Science and Technology，Taiyuan 030024，China)

Abstract：In the premise of Hessian matrix as a positive definite matrix，a broken line was constructed by Adams′method according to differential equation model in literature.Meanwhile，an Adams′algorithm for solving trust-region subproblems with quadratic model was presented by using the broken line instead of the optimal curve.Through comparison with tangent single dogleg method，the results of numerical experiments indicate that the new algorithm has obvious advantage over the tangent single dogleg method.

Key words：differential equation model，trust-region subproblems，Adams method

中图分类号：O221

文献标志码：A

doi：10.3969/j.issn.1673-2057.2016.01.016

文章编号：1673-2057(2016)01-072-05

作者简介：王英慧(1987-)女，硕士研究生，主要研究方向为最优化理论与应用。

基金项目：山西省自然科学基金(2008011013)；山西省 ‘131’领军人才工程项目

收稿日期：2015-04-02