一类不可微规划算法的线性收敛性
2013-01-29郑颖春王雪峰
郑颖春， 王雪峰
(西安科技大学 理学院， 陕西 西安 710054)
0 引言
不可微优化(或非光滑优化)讨论具有不连续一阶偏导数的函数的极小化(或极大化)问题，在经济数学与其它一些实际问题中往往会遇到，近三十余年来，不可微优化的理论与方法有了很大的发展.作者Sachs.E在文献[1]给出了一种不可微优化的拟牛顿算法，作者Alexander.Shapiro， M.S.KIM，D.H.CHOI and Y.HWAN，Womersley.R.S分别在文献[2]、[3]、[4]中给出了合成函数的不可微优化算法，作者Israel Zang在文献[5]提出了一类有效的极小极大问题的算法.这些算法代表了不可微优化算法的发展方向，但都没有讨论算法的收敛速度，而本文将着重研究一类不可微优化算法的线性收敛性.
1 算法描述
本文主要讨论如下一类不可微最优化问题
式中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 基本概念与基本引理
下面首先给出线性收敛及二阶方向导数的定义，然后证明几个积分中值定理.
定义1[10]设序列{x(k)}⊂Rn收敛于x*.
若存在常数ρ∈(0,1)，使得当k充分大时，
‖x(k+1)-x*‖≤ρ‖x(k)-x*‖
则称{x(k)}线性收敛于x*，或称{x(k)}的收敛速度是线性的.
定义2 (二阶方向导数)设f:Rn→R1是局部李普希兹函数，f′(x,d)对x也是局部李普希兹的，若极限
设x(t)是[0,T]上的n维连续且可微的向量函数，令φ(t)=f[x(t)]，不难证明φ(t)在[0,T]是绝对连续函数，故存在可积函数ω(t)使得
(1)
这里的积分是Lebsegue积分，并且几乎对所有的t∈[0,T]，有：
也就是说函数φ(t)几乎处处可微.
引理1 设函数f:Rn→R1在点x0是局部李普希兹的，则f在x0具有以下性质
∀v∈Rn.由(1)及引理1可知，
故
(2)
这就是一阶的积分中值定理.
引理2 设f:Rn→R1是局部李普希兹的，f′(x,d)对x也是局部李普希兹的，则下列积分中值定理成立：
(3)
f(x+λd)=f(x)+λf′(x,d)
(4)
证明：(3)式由二阶方向导数的定义立即可得.
以下证明(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)在区间[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*)]，其中
θ=
f(xk+1)-f(x*)≤θ2(f(xk)-f(x*))
≤…≤θ2k(f(x1)-f(x*))
即‖xk+1-x*‖≤sθk，(k=1,2,…),其中
4 数值例子
下面用场址的合理选定问题来验证算法的可行性.假设要选定一个供应中心，(例如超市、影院、奶站等)的位置，该中心为m个具有固定位置(ai,bi),i=1,2,…，m的用户服务，而中心的定位准则是使中心到用户的某个距离函数取最小等，试求供应中心的位置[12].
为此需先建立该问题的数学模型，设供应中心的位置为(x,y)可建立以下数学模型：
如给定
距离总和为10.667 4，中心到用户的距离分别是：2.777 73,3.777 91,4.111 10.
即有‖xk+1-x*‖ ≤sθk,(k=1,2,…)
从而算法具有线性收敛性.
5 结束语
本文给出了二阶方向导数的定义，并在此基础上证明了不可微情形下的一阶及二阶积分中值定理，这些中值定理和可微情形是相似的，进而证明了一类不可微优化算法具有线性收敛性，数值例子表明算法是有效的，并具有线性收敛性.
[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] 王雪峰.基于次微分集的外接长方体的不可微优化算法[J].西北大学学报,2009，39(2):196-198.
[10] 袁亚湘，孙文瑜.最优化理论与方法[M].北京：科学出版社，2005.
[11] 华东师范大学数学系.数学分析[M].北京：高教出版社，2002.
[12] 阳明盛，罗长童.最优化原理、方法及求解软件[M].北京：科学出版社，2006:240-242.
