無約束最優(yōu)化中行列修正擬牛頓法的計算效能和最佳換元周期

鄭新宇，劉停戰(zhàn)

(中國傳媒大學 理學院，北京 100024)

無約束最優(yōu)化中行列修正擬牛頓法的計算效能和最佳換元周期

鄭新宇，劉停戰(zhàn)

(中國傳媒大學 理學院，北京 100024)

提出了一類適用于求解無約束最優(yōu)化問題的行列同步修正算法，得到了新算法的收斂階，通過優(yōu)化算法的計算效能指數(shù)給出算法的最佳換元周期，并進行了數(shù)值比較試驗。該算法同樣適用于求解大型對稱非線性方程組。

無約束最優(yōu)化；擬牛頓法；換元周期

1 引言

考慮無約束最優(yōu)化問題：

minf(x)

s.t.x∈Rn

(1)

其中f(x)：Rn→R二次連續(xù)可微。如果利用牛頓法求解該問題，則需要計算f(x)的Hessen矩陣或其逆陣，問題規(guī)模較大時工作量十分可觀。而擬牛頓法則是以各種修正矩陣去近似代替Hessen矩陣或它的逆陣，算法的計算復雜性明顯下降。

本文中提出了一類行列同步修正擬牛頓算法，每次修正近似矩陣中的幾行及這幾行對應(yīng)的幾列，其修正矩陣滿足擬牛頓方程，每次修正的函數(shù)求值次數(shù)與PSB，DFP，BFGS等修正算法相同，且保持了原有的對稱性，并在一定的條件下，獲得了新算法的收斂階，數(shù)值試驗表明這是一個較為理想的修正算法。

2 無約束最優(yōu)化問題中行列同步修正擬牛頓法及其效能指數(shù)

對于問題(1.1)，我們記f于x處的梯度為▽f(x)：Rn→Rn，由最優(yōu)性條件，可考慮對稱非線性方程組求解。令={1，2，…，n}，ei表示單位矩陣E的第i列，則任何n×n矩陣A可表示為。設(shè)lk?，則矩陣

于是，我們構(gòu)造行列同步修正算法如下：

算法2.1

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

2°如果‖▽f(xk)‖≤ε，則停止計算，令x*=xk；否則，繼續(xù)；

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，轉(zhuǎn)2°。

行列同步修正擬牛頓法有如下的收斂性定理。

定理2.1[1]設(shè)n維函數(shù)f(x)于D?Rn上二階連續(xù)可微，存在x*∈D使得▽f(x*)=0且Hessen矩陣▽2f(x*)正定，Hessen矩陣滿足Lipschitz條件，即存在κ>0，使得?x，y∈D，有‖▽2f(x)-▽2f(y)‖F(xiàn)≤κ‖x-y‖，則由(2)定義的行列同步修正擬牛頓法局部超線性收斂且收斂階至少為τ，其中τ為方程

τl+1-τl-1=0

(3)

的唯一正根。

(4)

定義2.1(效能指數(shù))設(shè)解n階方程組的某個迭代法的收斂階為τ，每步迭代的計算量為μ，則稱A=lnτ/μ為該迭代法的效能指數(shù)。

3 最佳換列周期的確定

由定義2.1，行列同步修正法的效能指數(shù)

(5)

其中，τ(l)為方程(3)的唯一正根。簡記A(n，l)為A(l)或A，τ(l)為τ，則A(l)是[1，n]上的光滑函數(shù)，下面確定l*使A(l*)達到最大即可。

(6)

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

引理3.1[2]當t>1時，多項式p(t)=tl+1-tl-1關(guān)于t單調(diào)增加。

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

證明：

(7)

證明：

表1

4 計算效能及數(shù)值試驗

我們將用最簡單的例子對本文中的新算法進行計算，以驗證以上結(jié)論。計算過程中令l分別取不同的值，并對計算過程的運行時間及迭代步數(shù)進行記錄。表2中，t表示算法函數(shù)調(diào)用過程中CPU的占用時間，其單位為毫秒(ms)。k表示算法終止前運行的迭代次數(shù)。A(n，l)表示其計算效能。表2中，當l=27時，距離表1中的l*(最佳換元周期)最接近，所需計算時間較其他情況下更短，計算效能A(n，l)也較其他更高，與我們前面得出的結(jié)論一致。

表2

[1]馮果忱，亢政剛.論換元修正Newton型方法[J].高等學校計算數(shù)學學報，1985，7(3)：193-200.

[2]馮果忱，張德統(tǒng)，劉仃戰(zhàn).換元Newton型方法的計算效能和最佳換元周期[J].高等學校計算數(shù)學學報，1991，13(2)：218-225.

[3]王德人，楊永健.關(guān)于一類列修正算法的一點注記[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