一种求解二次模型信赖域子问题的休恩算法

李 亮，王希云，张雅琦，于海波(太原科技大学 应用科学学院，太原 030024)

无约束最优化问题如下：

minf(x),x∈Rn

(1)

其中f(x)∶Rn→R是目标函数，x∈Rn是待求变量。

对于求解无约束最优化问题(1)，在现代优化方法中，信赖域方法是一种被广泛应用而且具有全局收敛性的方法。所以，近二十多年来受到了非线性最优化研究界的高度重视，成为了与传统的线搜索方法并列的两类主要算法之一。

当用信赖域方法求解无约束最优化问题(1)时，关键在于每步迭代时都需要求解下面形式的二次模型信赖域子问题：

(2)

其中g∈Rn为目标函数在当前迭代点的梯度，B∈Rn×n为目标函数在当前迭代点的Hessian矩阵或其近似，△∈R为信赖域半径，δ∈Rn为待求变量。当△变化时，上述二次模型信赖域子问题(2)的解δ*形成一条空间曲线，称为最优曲线[1]。

如何求解二次模型信赖域子问题(2)，目前已经提出了很多方法[2-11]。在Hessian矩阵正定的情况下，目前常用的折线法主要有单折线法、双折线法和切线单折线法[12-14]。文献[14]的数值实验表明，切线单折线法比单折线法、双折线法求解二次模型信赖域子问题(2)更有效。切线单折线法的思想：连接点θ,δzp,δnp形成一条折线，称为切线单折线，然后用该切线单折线近似最优曲线来求解二次模型信赖域子问题(2).其中θ是初始点，δnp=-B-1g，δzp是最优曲线在点δnp处的切线与-g方向的交点。与其它折线法相比，切线单折线法中所构造的折线则更近似最优曲线，但是当信赖域半径小于‖δzp‖2时，切线单折线法的数值结果是很不理想的。

折线法的基本思想就是寻找一条折线能够很好的近似最优曲线，从而用该折线代替最优曲线来求解二次模型信赖域子问题(2).本文根据最优曲线的参数方程首先构造出了一个微分方程模型，从而采用求解微分方程的休恩方法[15]构造一条折线Υ，进而用该折线Υ代替最优曲线来求解二次模型信赖域子问题(2).数值结果表明新算法较切线单折线法具有很好的效果，尤其是当信赖域半径小于‖δzp‖2时，更显示了其明显的优越性。

1 微分方程模型的构造

定理1.1[16]δ*是二次模型信赖域子问题(2)的解，当且仅当存在μ*≥0，使得：

而且(B+μ*I)是半正定矩阵。

由定理1.1可知，二次模型信赖域子问题的精确求解方法的思想即解如下的方程组：

(3)

当μ=0时，二次模型信赖域子问题(2)的解δ*=-B-1g；当μ>0时，则是通过求解一元非线性方程‖(B+μI)-1g‖2-△=0得到解μ*，然后把μ*代入式(3)的第一个方程，则可以求出二次模型信赖域子问题(2)的解δ*=-(B+μ*I)-1g.

根据二次模型信赖域子问题的精确求解方法的思想，则可以得到最优曲线的参数方程如下：

δ=-(B+μI)-1g(μ>0)

(4)

对参数方程(4)求导，可得：

Bδ′+δ+μδ′=0

即

(B+μI)δ′=-δ

故求出最优曲线上任意一点的切线斜率如下：

δ′=-(B+μI)-1δ(μ≥0)

从而构造的微分方程模型如下：

(5)

对于微分方程(5)，利用求解微分方程的休恩方法，构造了一条折线Υ，从而用该折线代替最优曲线来求解二次模型信赖域子问题(2).

2 折线Υ的构造

休恩公式如下：

从初始点P0(μ0,δ0)开始，先由公式：

求出下一点P1(μ1,δ1)，其中μ1=h.

…再从Pk-1(μk-1,δk-1)开始，先由公式：

求出下一点Pk(μk,δk)，其中μk=kh.

…再从点PN-1(μN-1,δN-1)开始，先由公式：

求出下一点PN(μN,δN)，其中μN=Nh.

依次作下去，直到满足‖δN‖2≤△时停止。然后分别连接点P0，P1，…，PN，则可以得到折线P0P1…Pk…PN，这里记折线P0P1…Pk…PN为Υ，然后用Υ作为最优曲线的近似，进而来求解二次模型信赖域子问题(2)的解δ*.

3 休恩算法

通过上面的讨论，下面给出休恩算法的具体步骤：

步0给定梯度g，正定矩阵B，信赖域半径△.

步1令δ0=δnp=-B-1g，如果△≥‖δ0‖2，则取δ0=δ0.停止计算，否则转步2.

停止计算，否则令n∶=1，转步4.

4 数值结果

取步长h=0.5，对给定的测试函数1和测试函数2的二次模型信赖域子问题，选取不同的信赖域半径△，然后将休恩算法利用MATLAB进行了实验。并且用该算法求得的相关数值结果与切线单折线法求得的相关数值结果进行了比较。相关数据分别列在表1和表2中，其中△表示信赖域半径，q表示测试函数的最优解的函数值，TDL表示切线单折线法，HML表示休恩算法，qHML-qTDL表示使用休恩算法与切线单折线法所求得的测试函数的最优解的函数值之差，该值越小，表明休恩算法越好。测试函数见附录。

从表1和表2的数值结果可以看出，对给定的不同的信赖域半径△，都有qHML-qTDL≤0.故本文构造的折线Υ比切线单折线更好的近似了最优曲线。当信赖域半径△≤‖δzp‖2[14]时，休恩算法所求得的测试函数的最优解比切线单折线法好很多；当信赖域半径‖δzp‖2<△<‖B-1g‖2时，休恩算法求得的测试函数的最优解也好于切线单折线法；当信赖域半径△≥‖B-1g‖2时，休恩算法与切线单折线法所求得的测试函数的最优解相同。因此，休恩算法是一个比切线单折线法更好的求解信赖域子问题的折线法。对于测试函数Function 1，‖δzp‖2=2.99，‖B-1g‖2=15.34.对于测试函数Function 2，‖δzp‖2=3.64，‖B-1g‖2=11.00.

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

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

附录：测试函数

参考文献：

[1] 徐成贤，陈志平，李乃成.近代优化方法[M].北京：科学出版社，2002.

[2] CHEN J，SUN W Y.Nonmonotone Adaptive Trust Region Algorithms with Indefinite Dogleg Path for Unconstrained Minimization[J].Northeast Math J，2008，24(1)：19-30.

[3] 赵英良，徐成贤.信赖域子问题使用重新开始策略的共轭梯度法[J].高校应用数学学报：A辑，2003，18(3)：341-349.

[4] 后六生，孙文瑜.三项预处理共轭梯度法与信赖域子问题[J].南京师大学报：自然科学版，2001，24(3)：1-6.

[5] 陈争，马昌风.求解信赖域子问题的一个光滑牛顿法[J].福建师范大学学报：自然科学版，2011，27(4)：31-35.

[6] ZHANG X S，CHEN Z W，ZHANG J L.A Self-adaptive Trust Region Method For Unconstrained Optimization[J].Operation Research Transactions，2001，5(1)：53-62.

[7] 赵丹.解信赖域子问题的混合折线法[J].徐州师范大学学报：自然科学版，2009，27(3)：38-41.

[8] 杨郁，王希云.基于信赖域子问题的共轭梯度法[J].太原科技大学学报，2010，31(6)：481-484.

[9] 张立，唐志强.解信赖域子问题的混合折线法[J].南京师大学报：自然科学版，2001，24(1)：28-32.

[10] TOINT P L，TOMANOS D.A Multilevel Algorithm for Solving the Trust-region Subproblem[J].Optimization Methods and Software，2009，24(2)：299-311.

[11] 吕立波.解决大规模信赖域子问题的一种新算法[J].运筹与管理，2007，16(5)：48-52.

[12] POWELL M J D.A Hybrid Method for Nonlinear Equations.In：Numerical Methods for Nolinear Algebraic Equations，Rabinowitz P.ed.London：Gordon and Breach，1970.

[13] DENNIS J E，MEI H H W.Two New Unconstrained Optimization Algorithms Which Use Function and Gradient Values[J].Journal of Optimization Theory and Applications，1979，28(4)：453-482.

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

[15] 颜庆津.数值分析[M].北京：北京航空航天大学出版社，2006.

[16] 袁亚湘，孙文瑜.最优化理论与方法[M].北京：科学出版社，2007.