无约束最优化中行列修正拟牛顿法的计算效能和最佳换元周期

郑新宇，刘停战

(中国传媒大学 理学院，北京 100024)

无约束最优化中行列修正拟牛顿法的计算效能和最佳换元周期

郑新宇，刘停战

(中国传媒大学 理学院，北京 100024)

提出了一类适用于求解无约束最优化问题的行列同步修正算法，得到了新算法的收敛阶，通过优化算法的计算效能指数给出算法的最佳换元周期，并进行了数值比较试验。该算法同样适用于求解大型对称非线性方程组。

无约束最优化；拟牛顿法；换元周期

1 引言

考虑无约束最优化问题：

minf(x)

s.t.x∈Rn

(1)

其中f(x)：Rn→R二次连续可微。如果利用牛顿法求解该问题，则需要计算f(x)的Hessen矩阵或其逆阵，问题规模较大时工作量十分可观。而拟牛顿法则是以各种修正矩阵去近似代替Hessen矩阵或它的逆阵，算法的计算复杂性明显下降。

本文中提出了一类行列同步修正拟牛顿算法，每次修正近似矩阵中的几行及这几行对应的几列，其修正矩阵满足拟牛顿方程，每次修正的函数求值次数与PSB，DFP，BFGS等修正算法相同，且保持了原有的对称性，并在一定的条件下，获得了新算法的收敛阶，数值试验表明这是一个较为理想的修正算法。

2 无约束最优化问题中行列同步修正拟牛顿法及其效能指数

对于问题(1.1)，我们记f于x处的梯度为▽f(x)：Rn→Rn，由最优性条件，可考虑对称非线性方程组求解。令={1，2，…，n}，ei表示单位矩阵E的第i列，则任何n×n矩阵A可表示为。设lk⊂，则矩阵

于是，我们构造行列同步修正算法如下：

算法2.1

1°给定初始x0∈Rn，B0=Rn×n，控制误差ε>0，令k=0。

2°如果‖▽f(xk)‖≤ε，则停止计算，令x*=xk；否则，继续；

3°解Bkpk=-▽f(xk)得到下降方向pk。

5°令xk+1=xk+αkpk。

6°令

(2)

其中yki=▽f(xk+ηkiei)-▽f(xk)，0<ηki≤‖xk-xk-1‖，lk=kmodl，令k=k+1，转2°。

行列同步修正拟牛顿法有如下的收敛性定理。

定理2.1[1]设n维函数f(x)于D⊂Rn上二阶连续可微，存在x*∈D使得▽f(x*)=0且Hessen矩阵▽2f(x*)正定，Hessen矩阵满足Lipschitz条件，即存在κ>0，使得∀x，y∈D，有‖▽2f(x)-▽2f(y)‖F≤κ‖x-y‖，则由(2)定义的行列同步修正拟牛顿法局部超线性收敛且收敛阶至少为τ，其中τ为方程

τl+1-τl-1=0

(3)

的唯一正根。

(4)

定义2.1(效能指数)设解n阶方程组的某个迭代法的收敛阶为τ，每步迭代的计算量为μ，则称A=lnτ/μ为该迭代法的效能指数。

3 最佳换列周期的确定

由定义2.1，行列同步修正法的效能指数

(5)

其中，τ(l)为方程(3)的唯一正根。简记A(n，l)为A(l)或A，τ(l)为τ，则A(l)是[1，n]上的光滑函数，下面确定l*使A(l*)达到最大即可。

(6)

下面找A′(l)出的零点分布情况即可。

引理3.1[2]当t>1时，多项式p(t)=tl+1-tl-1关于t单调增加。

引理3.2将A(l)扩展到[1，2n]上，且τ(l)为方程(3)的唯一正根，则A′(l)=0在[1，2n]上必有根。

证明：

(7)

证明：

表1

4 计算效能及数值试验

我们将用最简单的例子对本文中的新算法进行计算，以验证以上结论。计算过程中令l分别取不同的值，并对计算过程的运行时间及迭代步数进行记录。表2中，t表示算法函数调用过程中CPU的占用时间，其单位为毫秒(ms)。k表示算法终止前运行的迭代次数。A(n，l)表示其计算效能。表2中，当l=27时，距离表1中的l*(最佳换元周期)最接近，所需计算时间较其他情况下更短，计算效能A(n，l)也较其他更高，与我们前面得出的结论一致。

表2

[1]冯果忱，亢政刚.论换元修正Newton型方法[J].高等学校计算数学学报，1985，7(3)：193-200.

[2]冯果忱，张德统，刘仃战.换元Newton型方法的计算效能和最佳换元周期[J].高等学校计算数学学报，1991，13(2)：218-225.

[3]王德人，杨永健.关于一类列修正算法的一点注记[J].上海大学学报(自然科学版)，1996，2(5)：493-498.

[4]Wang Deren，Yang Yongjian.On the Convergence of the Column-Updating Method[J].Numerical Mathematics，A Journal of Chinese Univercities，1997，1(3)：205-208.

[5]黄海，林穗华.几种修正拟牛顿法的比较[J].广西民族师范学院学报，2011，28(3)：8-11.

(责任编辑：王谦)

The Efficiency Index and the Optimal Update Period of Row-column Sync Updating Quasi-Newton Method in Unconstrained Optimization Problems

ZHENG Xin-yu，LIU Ting-zhan

(School of Science，Communication University of China，Beijing 100024，China)

A row-column sync updating quasi-Newton method for solving unconstrained optimization problems is considered. And we propose the speed of convergence of the new algorithm. By studying the efficiency index，the optimal update period of this method is given and numerical experiments are carried out. This method is also applicable to large scale symmetric nonlinear equations.

unconstrained optimization；Quasi-Newton method；update period

2015-01-27

郑新宇(1990-)，女(汉族)，河北唐山人，中国传媒大学硕士研究生.E-mail：997996804@qq.com

0241.7

A

1673-4793(2015)06-0035-05