徐　琳, 李　丹

(1. 沈陽大學 師范學院, 遼寧 沈陽　110044; 2. 沈陽市第二中學, 遼寧 沈陽　110016)

?

隨機約束非光滑凸優(yōu)化的空間分解方法

徐琳1, 李丹2

(1. 沈陽大學 師范學院, 遼寧 沈陽110044; 2. 沈陽市第二中學, 遼寧 沈陽110016)

摘要:討論了隨機約束非光滑凸優(yōu)化的基于空間分解的樣本均值近似(SAA)方法.在適當?shù)臈l件下,SAA問題的解以概率1收斂到其真實解,并且隨著樣本容量的增加,收斂速度是指數(shù)的.基于分解理論,給出了求解SAA問題的超線性收斂速度的算法框架.

關(guān)鍵詞:隨機優(yōu)化; 樣本均值近似; 空間分解; 超線性收斂

考慮如下的隨機約束非光滑凸優(yōu)化

(1)

式中,f(x)=max{E[fi(x,ξ)]:i∈I=0,…,m}.對每個固定的ξ和和η,函數(shù)fi(·,ξ),i∈I和gj(·,η),j∈J是二次連續(xù)可微的凸函數(shù).ξ和η是概率空間(Ω,γ,P)的兩個隨機變量,E是數(shù)學期望.

假設(shè)對任意x∈Rn,E[fi(x,ξ)],i∈I和E[gj(x,η)],j∈J有定義,令ξ1,…,ξN是ξ的樣本,并且η1,…,ηN是η的樣本.本文考慮基于樣本的均值近似(SAA)方法,即利用fi(·,ξ)和gj(·,η)的樣本均值近似它們的期望值.式(1)的SAA問題為

(2)

目前,SAA方法是隨機優(yōu)化的研究熱點.文獻[1]是隨機優(yōu)化和SAA方法的一個概述,亦可參見文獻[2-6].SAA方法的基本思想是由蒙特卡羅模擬產(chǎn)生獨立同分布的樣本,并利用樣本均值函數(shù)近似代替目標函數(shù),然后利用確定型的優(yōu)化方法來解決SAA問題,最后得到原問題的近似解.由于文獻[1-6]中的目標函數(shù)均是光滑的,因此,其SAA問題都可由光滑牛頓法求解.

1SAA問題的收斂性分析

是在x處的積極指標集.

接下來討論隨著N的增大,式(2)收斂到式(1).具體地,當N→∞時,式(2)的SAA問題的解收斂到原問題的解.下面給出SAA方法的基本假設(shè).

假設(shè)1

② 對任意的s∈X,矩母函數(shù)MS(t)在原點鄰域內(nèi)是有限值;

③ 對任意的ξ∈Ω,s′,s∈X,存在函數(shù)k:Ω→R+,使得

④ k(ξ)的矩母函數(shù)Mk(t)=E[etk(ξ)]在原點鄰域內(nèi)是有限值,其中Ms(t)=E[et(g(s,ξ)-G(s))]是隨機變量g(s,ξ)-G(s)的矩母函數(shù).

由假設(shè)1知,對于任意ε1>0,ε2>0,存在M1和M2,若N>M=max{M1,M2},則

令N>M且ε=ε1+ρε2,有

下面討論隨著樣本容量的增加,式(2)的SAA問題的指數(shù)收斂率.

定理2令xN是式(2)的SAA問題的解,S*是原問題式(1)的解決.假設(shè)1成立,則對于ε>0,存在正常數(shù)c(ε)和d(ε),使得對于充分大的N,有

(3)

證明令ε>0,ε1>0,ε2>0,由定理1及

有d(xN,S)<ε.因此由假設(shè)1知

2SAA問題的分解理論

定義了VU-空間分解,并且Rn=U⊕V,其中⊕是空間的直和.

定理3假設(shè)2成立,則有如下結(jié)論:

V=lin{[

有

則由V空間的定義知

并且由U=V⊥知U空間的結(jié)構(gòu).

V—空間的最優(yōu)解集為

定理4假設(shè)2成立,則對于充分小的u有如下結(jié)論成立:

① 非線性方程組

(4)

有唯一解v=v(u),并且v:RdimU→RdimV是二次連續(xù)可微的;

隨著蔬菜價格上漲，部分菜農(nóng)在經(jīng)濟利益的驅(qū)使下只看重眼前利益，不注重長遠發(fā)展，過早采收，長期單一施用化肥農(nóng)藥，不斷加大農(nóng)藥、化學肥料使用量等諸多影響蔬菜產(chǎn)業(yè)發(fā)展的不良現(xiàn)象依然存在，且有抬頭之勢，這些都不利于蔬菜產(chǎn)業(yè)的持續(xù)健康發(fā)展。一是長期偏施化肥，導致菜園土壤肥力明顯下降，蔬菜抗病蟲害能力減弱。二是過量施用農(nóng)藥、化肥，導致蔬菜中農(nóng)藥殘毒量增高，使蔬菜中有害農(nóng)藥殘留量和有害重金屬不斷增高聚積，直接影響了人們的食用安全，加重了生產(chǎn)者對化學農(nóng)藥的依賴，使噴藥濃度不斷加大，次數(shù)變多，造成了對環(huán)境的污染和生態(tài)系統(tǒng)的破壞。因此，研究天水市蔬菜農(nóng)藥殘留現(xiàn)狀，做好農(nóng)產(chǎn)品質(zhì)量安全監(jiān)督管理工作，顯得十分必要。

下面的定理給出了U-拉格朗日函數(shù)的一些性質(zhì).

①Lu是二次連續(xù)可微函數(shù);

②Lu的梯度為,其中

特別地,當u=0時,有

特別地,當u=0時,有

證明① 由定理4③,知

由于fi與v(u)均是二次連續(xù)可微的,知①成立.

② 根據(jù)鏈式法則,將下面的方程組

關(guān)于u求導,有

③對②關(guān)于u求導,有

根據(jù)文獻[10]中定理6.3的證明知

則有

3算法收斂性分析

算法1

Step 1(停止準則)若

(5)

則停.

(6)

Step 6(校正)置k=k+1,轉(zhuǎn)步1.

(7)

(8)

結(jié)合式(7)和式(8)有結(jié)論成立.

4結(jié)論

針對隨機約束非光滑凸優(yōu)化式(1),本文給出了基本空間分解理論的算法研究.該算法交替執(zhí)行V-步及U-牛頓步以獲得超線性的收斂速度.應(yīng)用束方法的思想及迫近點落在原始軌道上的理論,算法1中的V-步可迭代求出,這也是本文的一個后續(xù)工作.

參考文獻:

[1]SHAPIROA,DENTCHEVAD,RUSZCZYNSKIA.Lectureonstochasticprogramming,modellingandtheory[R].Philadelphia:SIAM, 2009.

[2] PAGNONCELLI B K, AHMED S,SHAPIRO A. Sample average approximation method for chance constrained programming: theory and application[J]. Journal of Optimization Theory and Applications, 2009,142(2):399-416.

[3] ROCKAFELLAR R T. Monotone operators and the proxiral point algorithm[J]. SIAM Journal on Control and optimization, 1976,14(5):877-898.

[4] WANG M Z, LIN G H, GAO Y L, et al. Sample average approximation method for a class of stochastic variational inequality problems[J]. Journal of Systems Science and Complexity, 2011,24(6):1143-1153.

[5] LIU Y C, ZHANG Y. Penalized sample average approximation methods for stochastic mathematical programs with complementarity constraints[J]. Mathematics of Operations Research, 2011,36(4):670-694.

[6] SHUANG C, PANG L P, GUO F F, et al. Stochastic methods based on Newton method to the stochastic variational inequality problem with constraint conditions[J]. Mathematical and Computer Modeling[J], 2012,55(3):779-784.

[7] LEMARECHAL C, OUSTRY F, SAGASTIZABAL C. The U-Lagrangian of a convex function[J]. Transactions of the American Mathematical Society, 2000,352(2):711-729.

[8] MIFLIN R, SAGASTIZABAL C. VU-decomposition derivatives for convex max-functions[M]∥Lecture Notes in Economics and Mathematical Systems. Berlin: Springer, 1999:167-186.

[9] LEMARECHAL C, SAGASTIZABAL C. More than first-order developments of convex functions: primal-dual relations[J]. Journal of Convex Analysis, 1996,3(2):1-14.

[10] MIFLIN R, SAGASTIZABAL C. On VU-theory for functions with primal-dual gradient strcture[J]. SIAM Journal on Optimization, 2000,11(2):547-571.

[11] MIFLIN R, SAGASTIZABAL C. Functions with primal-dual gradient structure and U-Hessians[M]∥Nonlinear Optimization and Related Topics. Norwell, MA: Kluwer Academic Publishers B.V, 2000:219-233.

[12] MIFLIN R, SAGASTIZABAL C. Primal-dual gradient structured functions: second-order results, links to epi-derivatives and partly smooth functions[J]. SIAM Journal on Optimization, 2003,13(4):1174-1194.

[13] LANG S. Real and function analysis[M]. 3rd ed, New York: Springer-Verlag, 1993.

[14] 張瑩. 一類非光滑凸函數(shù)的超線性空間分解方法[J]. 沈陽大學學報(自然科學版), 2015,27(6):501-506.

(ZHANG Y. A superlinear space-decomposition method for a class of nonsmooth convex function[J]. Journal of Shenyang University(Natural Sciences), 2015,27(6):501-506.)

【責任編輯: 肖景魁】

A Space Decomposition Method for Stochastic Constrained Nonsmooth Convex Optimization

XuLin1,LiDan2

(1. Normal School, Shenyang University, Shenyang 110044, China; 2. Shenyang No.2 High School, Shenyang 110016, China)

Abstract:Sample average approximation (SAA) method based on space-decomposition method to solve stochastic constrained nonsmooth convex optimization is discussed. Under some moderate conditions, the SAA solution converges to its true counterpart with probability approaching one and convergence is exponential fast with the increase of sample size. Based on the decomposition theory, a superlinear convergent algorithm frame is designed to solve the SAA problem.

Key words:stochastic optimization; sample average approximation; space decomposition; superlinear convergent

中圖分類號:O 221

文獻標志碼:A

文章編號:2095-5456(2016)02-0160-06

作者簡介:徐琳(1966-),女,遼寧沈陽人,沈陽大學副教授.

基金項目:國家自然科學基金資助項目(11301347).

收稿日期:2015-10-07