隨機(jī)二階錐規(guī)劃問題的快速空間分解方法

陸　媛

(沈陽大學(xué) 師范學(xué)院, 遼寧 沈陽　110044)

?

隨機(jī)二階錐規(guī)劃問題的快速空間分解方法

陸媛

(沈陽大學(xué) 師范學(xué)院, 遼寧 沈陽110044)

摘要:討論了基于空間分解的隨機(jī)二階錐規(guī)劃問題的樣本均值近似方法(簡稱SAA方法),在適當(dāng)?shù)臈l件下,證明了SAA問題的解以概率1收斂到原問題的解,并且隨著樣本容量的增加收斂速度是指數(shù)的. 基于分解理論,給出了SAA問題的超線性收斂算法框架.

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

考慮如下的隨機(jī)二階錐規(guī)劃(SSOCP)問題

(1)

m+1維的二階錐定義如下:

由Qm+1誘導(dǎo)的序關(guān)系Qm+1定義如下

本文討論SSCOP(1)問題的樣本均值近似方法(SAA). Shapiro在文獻(xiàn)[1]中討論了隨機(jī)廣義方程的SAA方法,亦可參見文獻(xiàn)[2-6]. SAA方法的基本思想是由蒙特卡羅模擬產(chǎn)生獨(dú)立同分布的樣本,并且使用函數(shù)的樣本均值來近似代替目標(biāo)函數(shù),然后利用確定型優(yōu)化方法求解SAA問題,最后得到原始問題的近似解.

令ξ1,ξ2,…,ξN和η1,η2,…,ηN分別是隨機(jī)變量ξ和η的樣本. 問題(1)的SAA問題如下

(2)

稱問題(2)是SAA問題,(1)為原問題.

本文的結(jié)構(gòu)如下:首先問題(2)通過精確罰函數(shù)被轉(zhuǎn)化為無約束問題,然后在浩斯道夫距離的意義下證明了近似解集收斂到原問題的解集.給出SAA問題的分解理論. 文章最后給出SAA問題的空間分解算法框架.

1SAA問題的收斂性分析

由二階錐的定義,SSOCP問題可以被轉(zhuǎn)化為

(3)

等價的,

并且

則式(3)可以轉(zhuǎn)化為

(4)

令x為式(4)的可行點(diǎn),定義如下的指標(biāo)集

其中μ>0是罰參數(shù). 具體的,

其中

因此,

并且

下面討論隨著N的增加,問題(4)收斂到問題(1). 特別的,將討論當(dāng)N→∞時,SAA問題(4)的解收斂到原問題的解. 首先,給出SAA方法的基本假設(shè).

假設(shè)1

(2) 對于任意的s∈X以及足夠小的t,矩母函數(shù)Ms(t)是有限的;

(3) 存在可測函數(shù)κ:Ω→R+,使得對所有的ξ∈Ω,s′,s∈X,有

(4) 對于足夠小的t,κ(ξ)的矩母函數(shù)為Mk(t)=E[etk(ξ)],其中Ms(t)=E[et(g(s,ξ)-G(s))] 是隨機(jī)變量g(s,ξ)-G(s)的矩母函數(shù).

并且

令N>M,ε=ε1+με2,有

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

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

(5)

證明令ε>0,ε1>0,ε2>0,由定理1知,存在δ>0使得

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

c(ε)e-Nd(ε).

2SAA問題的分解理論

首先介紹如下的定義和假設(shè).

為VU-子空間,并且Rn=U⊕V,其中⊕表示空間的直和.

并且由U=V⊥知結(jié)論的第二部分成立.

相應(yīng)的,V-子空間上的最優(yōu)解集為

(1) 關(guān)于變量u,v的非線性方程組

(6)

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

引理1關(guān)于αj的方程組

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

(1)Lu關(guān)于變量u是二階連續(xù)可微函數(shù);

特別的,當(dāng)u=0時,有,其中

其中

證明 (1) 由定理3結(jié)論(3),有

由于函數(shù)f和v(u)是二階連續(xù)可微的,結(jié)論(1)成立.

(2) 根據(jù)鏈?zhǔn)椒▌t,將下面的方程組關(guān)于變量u求導(dǎo)數(shù),

即

其中

其中

根據(jù)文獻(xiàn)[14]中的定理6.3的證明,有

因此

3算法和收斂性分析

算法1(算法框架)

Step 1(停止準(zhǔn)則)若

(7)

則停.

(8)

其中

Step6(校正)置k=k+1,轉(zhuǎn)Step1.

(9)

由式(8)知,

故

4結(jié)論

首先針對二階錐規(guī)劃問題,給出基于VU-空間分解的樣本均值近似方法(SAA). 然后討論了SAA子問題目標(biāo)函數(shù)具有與VU-空間分解相關(guān)的原始對偶梯度結(jié)構(gòu). 進(jìn)而,Rn空間可以分解為U和V兩個直交的子空間. 目標(biāo)函數(shù)在U-空間上是光滑的,具有與二階展開相關(guān)的U-海賽陣. 因此,在設(shè)計(jì)求解SAA問題的算法上采用Newton方法以獲得超線性的收斂速度.

參考文獻(xiàn):

[ 1 ]SHAPIROA,DENTCHEVAD,RUSZCZYNSKIA.Lecturesonstochasticprogramming:modelingandtheory[R].Philadelphia:SIAM, 2009.

[ 2 ]PAGNONCELLIBK,AHMEDS,SHAPIROA.Sampleaverageapproximationmethodforchanceconstrainedprogramming:theoryandapplication[J].JournalofOptimizationTheoryandApplications, 2009,142(2):399-416.

[ 3 ]FLIEGEJ,XUH.Stochasticmultiobjectiveoptimization:sampleaverageapproximationsandapplication[J].JournalofOptimizationTheory&Applications, 2011,151(1):135-162.

[ 4 ]WANGMZ,LINGH,GAOYL,etal.Sampleaverageapproximationmethodforaclassofstochasticvariationalinequalityproblems[J].JournalofSystemScienceandComplexity, 2011,24(6):1143-1153.

[ 5 ]LIUYC,XUHF,YEJJ.Penalizedsampleaverageapproximationmethodsforstochasticmathematicalprogramswithcomplementarityconstraints[J].MathematicsofOperationsResearch, 2010,36(36):670-694.

[ 6 ]SHUANGC,PANGLP,GUOFF,etal.StochasticmethodsbasedonNewtonmethodtothestochasticvariationalinequalityproblemwithconstraintconditions[J].MathematicalandComputerModeling, 2012,55(3):779-784.

[ 7 ]KANZOWC,FERENCZII,FUKUSHIMAM.Semismoothmethodsforlinearandnonlinearsecond-oderconeprograms[R].DepartmentofAppliedMathematicsandPhysics,KyotoUniversity, 2006.

[ 8 ]LIUYJ,ZHANGLWANDWANGYH.Convergencepropertiesofasmoothingmethodforlinearsecond-orderconeprogramming[J].AdvancesinMathematics, 2007,36(4):491-502.

[ 9 ]LIUYJ,ZHANGLW.ConvergenceofaugmentedLagrangianmethodfornonlinearoptimizationproblemsoversecond-ordercones[J].JournalofOptimizationTheoryandApplications, 2008,139(3):557-575.

[10]BAIYQ,WANGGQ.Primal-dualinterior-pointalgorithmsforsecond-orderconeoptimizationbasedonanewparametrickernelfunction[J].ActaMathematicaSinica(EnglishSeries), 2007,23(11):2027-2042.

[11]LEMARECHALC,OUSTRYF,SAGASTIZABALC.TheU-Lagrangianofaconvexfunction[J].TransactionsoftheAmericanMathematicalSociety, 2000,352(2):711-729.

[12]MIFFLINR,SAGASTIZABALC.VU-decompositionderivativesforconvexmax-functions[M]∥Ⅲ-posedVariationalProblemsandRegularizationTechniques.Berlin:SpringerBerlinHeidelberg, 1999:167-186.

[13]LEMARECHALC,SAGASTIZABALC.Morethanfirst-orderdevelopmentsofconvexfunctions:primal-dualrelations[J].JournalofConvexAnalysis, 1996,3(2):1-14.

[14]MIFFINR,SAGASTIZABALC.OnVU-theoryforfunctionswithprimal-dualgradientstructure[J].SIAMJournalonOptimization, 2000,11(2):547-571.

[15]MIFFINR,SAGASTIZABALC.Functionswithprimal-dualgradientstructureandU-Hessians[M]∥NonlinearOptimizationandRelatedTopics.NewYork:SpringerUS, 2000:219-233.

[16]MIFFINR,SAGASTIZABALC.Primal-dualgradientstructuredfunctions:second-orderresults;linkstoEpi-derivativesandpartlysmoothfunctions[J].SIAMJournalonOptimization, 2002,13 (4): 1174-1194.

[17]LANGS.Realandfunctionanalysis[M]. 3rded.NewYork:Springer-Verlag, 1993.

【責(zé)任編輯: 肖景魁】

A Fast Space Decomposition Method for Stochastic Second-Order Cone Programming Problem

LuYuan

(Normal School, Shenyang University, Shenyang 110044, China)

Abstract:Sample average approximation (SAA) method based on the space decomposition method to solve stochastic second-order cone programming problem 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; second-order cone programming; sample average approximation; space decomposition; superlinear convergent

文章編號:2095-5456(2016)03-0250-06

收稿日期:2016-01-06

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(11301347).

作者簡介:陸媛(1981-),女,遼寧沈陽人,沈陽大學(xué)副教授,博士.

中圖分類號:O 221

文獻(xiàn)標(biāo)志碼:A