一類不可微規(guī)劃算法的線性收斂性

鄭穎春， 王雪峰

(西安科技大學 理學院， 陜西 西安 710054)

0 引言

不可微優(yōu)化(或非光滑優(yōu)化)討論具有不連續(xù)一階偏導數(shù)的函數(shù)的極小化(或極大化)問題，在經(jīng)濟數(shù)學與其它一些實際問題中往往會遇到，近三十余年來，不可微優(yōu)化的理論與方法有了很大的發(fā)展.作者Sachs.E在文獻[1]給出了一種不可微優(yōu)化的擬牛頓算法，作者Alexander.Shapiro， M.S.KIM，D.H.CHOI and Y.HWAN，Womersley.R.S分別在文獻[2]、[3]、[4]中給出了合成函數(shù)的不可微優(yōu)化算法，作者Israel Zang在文獻[5]提出了一類有效的極小極大問題的算法.這些算法代表了不可微優(yōu)化算法的發(fā)展方向，但都沒有討論算法的收斂速度，而本文將著重研究一類不可微優(yōu)化算法的線性收斂性.

1 算法描述

本文主要討論如下一類不可微最優(yōu)化問題

式中f(x)在Rn中是局部李普希茲的[6，7,8].文獻[9]已給出這類問題的一種有效算法，并且證明了該算法具有線性收斂性，文獻[9]的算法和次梯度算法具有相同的收斂速度，本文借助文獻[9]的證明方法證明了一般的次梯度算法都具有線性收斂性.

次梯度算法及收斂性可用以下定理描述：

xk+1=xk-hk‖gf(xk)‖-1gf(xk)k=0,1,2,…

文獻[9]給出了次微分集的外接長方體的概念，并證明了次微分集的外接長方體的中心元一定是一個次梯度，這時次梯度法可簡化為：給定初始點x0，可以用迭代公式：

xk+1=xk-hk+1‖yk‖-1yk

2 基本概念與基本引理

下面首先給出線性收斂及二階方向?qū)?shù)的定義，然后證明幾個積分中值定理.

定義1[10]設序列{x(k)}?Rn收斂于x*.

若存在常數(shù)ρ∈(0,1)，使得當k充分大時，

‖x(k+1)-x*‖≤ρ‖x(k)-x*‖

則稱{x(k)}線性收斂于x*，或稱{x(k)}的收斂速度是線性的.

定義2 (二階方向?qū)?shù))設f:Rn→R1是局部李普希茲函數(shù)，f′(x,d)對x也是局部李普希茲的，若極限

設x(t)是[0,T]上的n維連續(xù)且可微的向量函數(shù)，令φ(t)=f[x(t)]，不難證明φ(t)在[0,T]是絕對連續(xù)函數(shù)，故存在可積函數(shù)ω(t)使得

(1)

這里的積分是Lebsegue積分，并且?guī)缀鯇λ械膖∈[0,T]，有：

也就是說函數(shù)φ(t)幾乎處處可微.

引理1 設函數(shù)f:Rn→R1在點x0是局部李普希茲的，則f在x0具有以下性質(zhì)

?v∈Rn.由(1)及引理1可知，

故

(2)

這就是一階的積分中值定理.

引理2 設f:Rn→R1是局部李普希茲的，f′(x,d)對x也是局部李普希茲的，則下列積分中值定理成立：

(3)

f(x+λd)=f(x)+λf′(x,d)

(4)

證明：(3)式由二階方向?qū)?shù)的定義立即可得.

以下證明(4)

由(2)式可知

故

f(x+λd)-f(x)-λf′(x,d)

即

由于[11]

所以(4)式成立.

引理3 若存在m,M1,K使得：

‖ξ(x)‖≤m‖x-x*‖，其中M=M1+K,ξ(x)滿足<ξ(x),x-x*>=f′(x,x-x*).

由引理2及定積分的保序性易證這個引理，這里從略.

引理4 設φ(λ)在[0,b]上是局部李普希茲的，且φ′(0,1)<0,(φ′(0,-1)<0),若φ(λ)在[0,b]上的極小點λ*∈(0,b)，則有

其中Q是φ″(0,1),(φ″(0,-1))的正上界.

3 算法的線性收斂性

下面用上述引理來證明算法的線性收斂性.

‖xk+(λk+δ)dk-x*‖=‖xk+1-x*+δdk‖<ε

考慮對φ(λ)=f(xk+λdk)在區(qū)間[0,λk+δ]上應用引理4，并注意dk的取法，

φ′(0,1)=f′(xk,dk),

φ′(λ,1)=f′(xk+λdk,dk),φ″(λ,1)

=f″(xk+λdk,dk)，由于f″(xk+dk,dk)有界，所以φ″(λ,1)有界.由引理3知φ(λ)在[0,λk+δ]上的整體極小點λk滿足：

其中:M=M1+K,〈ξ(xk),dk〉=f′(xk,dk) ,α(xk)∈(0,1).

于是f(xk+1)-f(x*)≤θ[f(xk)-f(x*)]，其中

θ=(α(xk)mM)2〗12，則有：

f(xk+1)-f(x*)≤θ2(f(xk)-f(x*))

≤…≤θ2k(f(x1)-f(x*))

即‖xk+1-x*‖≤sθk，(k=1,2,…),其中

4 數(shù)值例子

下面用場址的合理選定問題來驗證算法的可行性.假設要選定一個供應中心，(例如超市、影院、奶站等)的位置，該中心為m個具有固定位置(ai,bi),i=1,2,…，m的用戶服務，而中心的定位準則是使中心到用戶的某個距離函數(shù)取最小等，試求供應中心的位置[12].

為此需先建立該問題的數(shù)學模型，設供應中心的位置為(x,y)可建立以下數(shù)學模型：

如給定

距離總和為10.667 4，中心到用戶的距離分別是：2.777 73,3.777 91,4.111 10.

即有‖xk+1-x*‖ ≤sθk,(k=1,2,…)

從而算法具有線性收斂性.

5 結(jié)束語

本文給出了二階方向?qū)?shù)的定義，并在此基礎上證明了不可微情形下的一階及二階積分中值定理，這些中值定理和可微情形是相似的，進而證明了一類不可微優(yōu)化算法具有線性收斂性，數(shù)值例子表明算法是有效的，并具有線性收斂性.

[1] Sachs E.Quasi-newton methods foraclass of nonsmooth constrained oplmization problems[J].Lectur Notesin Contraland InformationSci,1982，38(4):42-45.

[2] Alexander,Shapiro.On a class of nonsmooth composite functions[J].Mathematics of Operations Research,2003，28(4)，677-692.

[3] M.S.KIM,D.H.CHOI,Y.H.WANG.Composite nonsmooth optimization using approximate generalized gradient vectors[J].Journal of Optimiaztion Theory and Applications,2002,112(1),145-165.

[4] Womersley.R.S,Fletcher.R.An algorithm for composite nonsmooth optimization problems[J].Journal of Optimization Theory and Applications,1986，48(2),493-523.

[5] Israel Zang.A smoothing-out technique for min-max optimization. Math Prog,1980,19(2):61-76.

[6] Rokafellar.R.T.Convex analysis[M].Princetion:New Jersey,1970:56-112.

[7] Shor.N Z.Minimization Methods for Nondiffenrentiable Function[M].New York:Springer-Verlag,1979:231-244.

[8] F.H.Clarke.Nonsmooth nalysis and optimization[M].New York: Wiley-Interscience,1983:37-41.

[9] 王雪峰.基于次微分集的外接長方體的不可微優(yōu)化算法[J].西北大學學報,2009，39(2):196-198.

[10] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學出版社，2005.

[11] 華東師范大學數(shù)學系.數(shù)學分析[M].北京：高教出版社，2002.

[12] 陽明盛，羅長童.最優(yōu)化原理、方法及求解軟件[M].北京：科學出版社，2006:240-242.