康立泉，牛善洲，黃進(jìn)紅

(贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000)

?

·計(jì)算方法·

單調(diào)變分不等式的一種自適應(yīng)譜梯度投影算法*

康立泉，牛善洲，黃進(jìn)紅

(贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000)

本文提出了求解單調(diào)變分不等式問題的一種自適應(yīng)譜梯度投影算法,并在一定條件下建立了算法的全局收斂性結(jié)果.初步的數(shù)值實(shí)驗(yàn)結(jié)果表明該算法能夠有效提高原有算法的計(jì)算效率.

變分不等式；譜梯度算法；投影算法；自適應(yīng)；全局收斂

1 引言

變分不等式在線性規(guī)劃、網(wǎng)絡(luò)經(jīng)濟(jì)、交通平衡、博弈論等領(lǐng)域都有非常廣泛的應(yīng)用.無約束優(yōu)化問題在轉(zhuǎn)化為變分不等式問題后,將變得更容易求解. 對于下述無約束優(yōu)化問題：

(1)

其中f為連續(xù)可微可導(dǎo)的凸函數(shù),Rn是n維歐式空間.上述問題的一階必要性條件等價(jià)于一個(gè)單調(diào)變分不等式問題,即尋找u*∈Ω使得?u∈Rn,滿足

(2)

其中Ω是Rn中的一個(gè)非空閉凸集,F為Rn→Rn的連續(xù)單調(diào)算子.通常記變分不等式問題為:VI(Ω,F)問題.

投影算法是求解VI(Ω,F)問題簡單且效果明顯的算法,其迭代格式為:

(3)

Barzilai和Borwein提出了求解無約束優(yōu)化問題的譜梯度算法也稱為BB算法[7], Dai在譜梯度算法及其應(yīng)用方面也做了大量的工作[8-12].進(jìn)一步,Zhou和Dai提出一個(gè)自適應(yīng)步長的梯度方法，實(shí)驗(yàn)結(jié)果表明該方法十分有效[13].此外,Yu提出了一個(gè)修正的自適應(yīng)梯度算法并應(yīng)用于圖像去噪問題,并得到了非常好的數(shù)值表現(xiàn)[14].

鑒于譜梯度算法在求解優(yōu)化問題上的優(yōu)越表現(xiàn),本文提出求解單調(diào)變分不等式問題的一種自適應(yīng)譜梯度投影算法.

2 自適應(yīng)譜梯度投影方法

BB算法利用當(dāng)前迭代步以及前一步的信息來確定步長因子,其基本思想是利用一個(gè)數(shù)量矩陣δkI近似代替目標(biāo)函數(shù)的Hessian 矩陣.Han在譜梯度算法的基礎(chǔ)上提出了一個(gè)變分不等式問題的譜梯度投影算法迭[15]代格式為:

(4)

(5)

(6)

γ是一個(gè)大于0的常數(shù),βk+1為步長.

為了改善上述譜梯度算法的計(jì)算效率,本文提出如下自適應(yīng)交替選取大步長和小步長的方式：

(7)

具體算法如下

算法1 (自適應(yīng)譜梯度投影算法:APBB)

步1: 給出初始點(diǎn)u0∈Rn,精度ε>0,設(shè)置最大迭代步為M及參數(shù)γ,β1;

步2: u1=PΩ(u0-β1F(u0)),設(shè)置k=1;

步3: 由(7)式計(jì)算βk+1;uk+1=PΩ(uk-γβk+1F(uk));

步4: e(uk+1)=uk+1-PΩ(uk+1-F(uk+1));

步5: 如果‖e(uk+1)‖≤ε或者k>M則迭代終止,否則設(shè)置k=k+1轉(zhuǎn)步3.

3 算法收斂性分析

本文在變分不等式的框架下對于上述自適應(yīng)譜梯度投影算法(APBB)進(jìn)行收斂性分析.

假設(shè)1 算子F滿足Lipschitz連續(xù)且強(qiáng)凸,即存在實(shí)數(shù)L和η使得:對于任意有u,v∈Ω有

(8)

(9)

在假設(shè)1成立的基礎(chǔ)上,根據(jù)Cauchy-Schwarz不等式可知L>η且不等式:

(10)

成立.

由文獻(xiàn)[16]重要投影性質(zhì)可得

引理2 對于?β1,β2,且β2≥β1>0,有

(11)

(12)

定理 通過APBB算法產(chǎn)生的序列{uk}全局收斂于VI(Ω,F)問題最優(yōu)解.

證明 由(11)與(10)式及投影性質(zhì)：

(13)

可知：

‖uk+1-PΩ[uk+1-γβk+1F(uk+1)]‖2=‖PΩ[uk-γβk+1F(uk)]-PΩ[uk+1-γβk+1F(uk+1)]‖2≤

設(shè)λ1是方程：

(14)

的最大實(shí)數(shù)解,其中ξ1∈(0,0.1),實(shí)數(shù)L,η滿足不等式:η

因此可得：

(15)

再由文獻(xiàn)[15]引理1可知βk>η/L2，以及引理2可得：

(16)

設(shè)c1=1-ξ1<1,因?yàn)棣耴+1

所以{uk}是柯西列且收斂于u∞.既然{u-PΩ[u-γβF(u)]}在Ω上連續(xù),因此可得:

因?yàn)镕強(qiáng)凸,可知變分不等式只有唯一解,即u∞=u*,所以點(diǎn)列{uk}收斂于VI(Ω,F)問題的最優(yōu)解.

4 實(shí)驗(yàn)與結(jié)果

問題1 在線性互補(bǔ)問題中,F(u)=Mu+q其中q=(-1,-1,…,-1),在實(shí)驗(yàn)中條件數(shù)設(shè)定為100.

圖1 APBB，PBB-I，PBB-II，算法運(yùn)行時(shí)間表現(xiàn)圖

問題2 在對稱非線性互補(bǔ)問題中,F(u)=Mu+D(u)+q,其中Dj(u)=aj,且aj由區(qū)間(0,1)中的數(shù)隨機(jī)生成.

問題3 對于上一個(gè)對稱非線性互補(bǔ)問題2,aj由區(qū)間(-500,500)中的數(shù)隨機(jī)生成.

表1 PBB-I,PBB-II,APBB算法對于互補(bǔ)問題實(shí)驗(yàn)數(shù)據(jù)結(jié)果

表2 取不同值互補(bǔ)問題實(shí)驗(yàn)數(shù)據(jù)

由表1可知:無論是迭代步還是CPU運(yùn)行時(shí)間,APBB在絕大多情況下比PBB-I,PBB-II更有優(yōu)勢.另外,再以不同的參數(shù)γ,不同的維數(shù)n=500,n=1 500,n=3 000進(jìn)行實(shí)驗(yàn)，代入以上四個(gè)互補(bǔ)問題中驗(yàn)證算法的有效性,從實(shí)驗(yàn)結(jié)果表2可知:自適應(yīng)譜梯度投影算法表現(xiàn)優(yōu)越.

為了更好說明算法APPB的效果,本節(jié)分別選用不同的初始迭代點(diǎn)u0=0n×1,u0=1n×1,u0=rand(n,1)再以不同的維數(shù)n為50,200,500,800進(jìn)行實(shí)驗(yàn),繪制出PBB-I,PBB- II,APBB三種方法相對于函數(shù)值的計(jì)算時(shí)間的表現(xiàn)分析圖.該曲線圖是根據(jù)Dolan和Moré提供的分析方法和工具,對不同算法的數(shù)值表現(xiàn)進(jìn)行分析[18].每條曲線對應(yīng)一種算法數(shù)值表現(xiàn)的概率分布.曲線的最左端表示該方法數(shù)值表現(xiàn)最有效的概率,曲線的最右端表示該方法能成功解決所有測試問題的概率.所以其它曲線右上方的曲線對應(yīng)的方法是最有效和最穩(wěn)定的算法.由分析圖可知,APPB算法的數(shù)值表現(xiàn)是最好的,其中APPB算法大約對75%的測試函數(shù)CPU的計(jì)算時(shí)間是最省的,PBB-I方法大約對20%的測試函數(shù)CPU的計(jì)算時(shí)間是最省,而PBB-II法只對大約8%的測試函數(shù)CPU計(jì)算時(shí)間是最省的,從整體上看:自適應(yīng)譜梯度投影算法穩(wěn)定且效果好.

5 結(jié)論

本文提出了求解單調(diào)單調(diào)變分不等式問題的一種自適應(yīng)譜梯度投影算法,一定條件下建立了算法的全局收斂性結(jié)果.初步的數(shù)值實(shí)驗(yàn)結(jié)果表明該算法能夠有效提高原有算法的計(jì)算效率,有一定的應(yīng)用前景.

[1] A.A.Goldsten. Convex programming in Hilbert space[J].Bulletin of the American Mathematical Socitey,1964,70(5):709-710.

[2] E.SLevitin, B.T.Polyak. Constrained minimiztion problems[J].USSR computional Mathematics and Mathematical Physics,1966,6(5):1-50.

[3] B.s. He,X.M.Yuan, J.Z.Zhang. Comparison of two kind of prediction-correction methods for monotonevaritionalinequalition[J].Computational Optimization and Applications, 2004,27(3):247-267.

[4] B.S.He, X.Z.He, X.H.Liu, T.Wu. A Self-adaptive projectivon methods for co-coercive variationalinequalities[J].EuropeanJournal of Operational resarch, 2009,196(1):43-48.

[5] D.R.Han, H.K.Lo. Two new self-adaptive projection methods for variational inequality problems[J].Computers and Mathematics with Applications, 2002,43(12):1529-1537.

[6] D.R.Han, W.Y.Sun. A new modified Goldstein-Levitin-Polyak projection method for variational inequality problems[J].Computers and Mathematics with Applications, 2005,47(12):1817-1825.

[7] J.Barzilai, J.M.Borwein. Two-point step size gradient methods[J].IMA Journal of Numerical Analysis,1988,8(1):141-148.

[8] Y.H Dai, .J.Y.Yuan, Y.X.Yuan.. Modified two-point stepsize gradient methods for unconstrained optimization[J].Computational Optimization and Applications,2001,22(1):103-109.

[9] Y.H. Dai, W.W. Hager, K Schittkowshi, H. Zhang. The cyclic Barzilai-Borwein method for unconstrained optimization[J].IMA Journal of Numerical Analysis,2006,26(3):604-627.

[10] Y.H. Dai, .R. Fletcher. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds[J].Mathematical Programming,2006,106(3):403-421.

[11] Y.H. Dai, R. Fletcher. On the asymptotic behaviour of some new gradient meth-ods[J].Mathematical Programming,2005,103(3):541-559.

[12] Y.H. Dai, R. Fletcher. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming[J].Numerische Mathematik,2005,100(1):21-47.

[13] B. Zhou. L. Gao, Y. H. Dai. Gradient methods with adaptive step size[J].Computational Optimization and Applications,2006,35(1):69-86.

[14] G. H. Yu, L .Q. Qi, Y. M. Sun, Y. Zhou. Impulse noise removal by a nonmonotone adaptive gradient method[J].Signal Processing,2010,90(10):2891-2897.

[15] H.J. He, D. R. Han, Z. B. Li. Some projection methods with the BB step sizes for variational inequalities[J].Journal of Computational and Applied Mathematics,2012,236(9):259-604.

[16] T. Zhu, Z.G. Yu. A simple proof for some important properties of the projection mapping[J].Mathematical Inequalities and Applications,2004,7:453-456.

[17] B.S. He. On the 0(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschiz continuous monotone operators,manuscript[M].Availabl on Optimization Online,2011.

[18] E. Dolan, J. Moré. Benchmarking optimization software with performance profiles[J].Mathematical Programming,2002,91(2):201-213.

An Adaptive Spectral Gradient Projection Method for Monotone Variational Inequalities

KANG Liquan, NIU Shanzhou, HUANG Jinhong

(SchoolofMathematicsandComputerScience,GannanNormalUniversity,Ganzhou34100,China)

This paper presents an adaptive spectral gradient projection method for monotone variational inequalities. Under suitable conditions, its global convergence result is established. Numberical results illustrate that the proposed method is more efficient than classical projection-like methods.

variational inqualities; spectral gradient method; projection method; global convergence

2016-02-15

10.13698/j.cnki.cn36-1346/c.2016.06.003

江西省研究生創(chuàng)新基金項(xiàng)目編號(hào)(YC2014-S411)

康立泉，男，贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2013級研究生；牛善洲，男，贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院教師，研究方向：最優(yōu)化方法及其應(yīng)用；黃進(jìn)紅，男，贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院教師，研究方向：最優(yōu)化方法及其應(yīng)用.

http://www.cnki.net/kcms/detail/36.1037.C.20161209.1500.008.html

O22

A

1004-8332(2016)06-0012-05