張　瑩, 李慧玲

(1. 沈陽(yáng)大學(xué) 師范學(xué)院, 遼寧 沈陽(yáng)　110044; 2. 沈陽(yáng)第一私立高中, 遼寧 沈陽(yáng)　110021)

一類非光滑凸函數(shù)的超線性空間分解方法

張瑩1, 李慧玲2

(1. 沈陽(yáng)大學(xué) 師范學(xué)院, 遼寧 沈陽(yáng)110044; 2. 沈陽(yáng)第一私立高中, 遼寧 沈陽(yáng)110021)

摘要:討論了一類非光滑凸優(yōu)化的空間分解方法,其目標(biāo)函數(shù)是分片二次連續(xù)可微的凸函數(shù).首先給出該優(yōu)化的空間分解;然后給出優(yōu)化問題的U-拉格朗日函數(shù)及其一階、二階性質(zhì);最后給出該優(yōu)化的具有超線性收斂速度的分解算法,并證明了算法的收斂性.

關(guān)鍵詞:凸優(yōu)化; 空間分解; 超線性收斂; 非光滑

考慮如下的優(yōu)化問題

本文主要目的是應(yīng)用VU-理論給出優(yōu)化式(1)的空間分解方法.首先給出VU-空間分解;然后利用U-拉格朗日函數(shù)討論目標(biāo)函數(shù)f的二階展開;最后給出空間分解算法,并討論該算法的收斂性.

1VU空間分解

在凸優(yōu)化式(1)中,目標(biāo)函數(shù)f是分片二次連續(xù)可微的.具體的,對(duì)?x∈Rn,

其中,fi:Rn→R,i∈I是二次連續(xù)可微的,稱為結(jié)構(gòu)函數(shù).式(2)的一個(gè)典型例子是有限最大值函數(shù)f(x)=maxfj(x), j=0,1,…,m,其中fj(x)是二次連續(xù)可微的凸函數(shù).然而,式(2)不僅限于最大值函數(shù).

給定形如式(2)的凸函數(shù),它在點(diǎn)x∈Rn處的次微分是在點(diǎn)x處積極結(jié)構(gòu)函數(shù)的梯度的凸組合,即

其中,

給定x∈Rn,g∈?f(x),x點(diǎn)處的VU空間分解如下:

假設(shè)A假設(shè)在x點(diǎn)處,集合{是線性無(wú)關(guān)的.

若假設(shè)A成立,則有

根據(jù)投影理論,?x∈Rn可以被分解為x=(xu,xv)T,在本文中我們使用記號(hào)xu⊕xv表示xu與xv的直和.即

本節(jié)給出U-拉格朗日函數(shù)的定義及一階、二階性質(zhì).

由文獻(xiàn)[1]知,式(1)的U-拉格朗日函數(shù)為

其最優(yōu)解集為

定理1若假設(shè)A成立,則對(duì)于?u足夠小,式(4)中的W(u)有唯一解w(u),滿足下面方程組

證明對(duì)式(5)左端關(guān)于v求導(dǎo),有

2.2二階展開

證明由式(3)和定理1,有

(1) Lu的梯度為

其中,

特別地,

其中,

(2) Lu的Hessian陣為

其中,

特別地,當(dāng)u=0時(shí),有

其中,

證明(1) 對(duì)式(6)關(guān)于u求導(dǎo),根據(jù)鏈?zhǔn)椒▌t知

根據(jù)文獻(xiàn)[8]中的式(6.11)有結(jié)果成立.

(2) 對(duì)式(7)兩端關(guān)于u求導(dǎo),有

其中,

由文獻(xiàn)[8]中定理6.3的證明有

因此,

當(dāng)u=0時(shí),

其中,

下面的定理給出函數(shù)f的二階展開式.

證明由Lu的定義,有

由于Lu是二階連續(xù)可微的,則有

即

3算法和收斂性

算法

Step 0(初始化)

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

若‖g(k)‖≤ε,則算法停止.

其中

Step 4(V-步)計(jì)算

其中

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

下面給出上述算法的收斂性證明.

并且

因此,v(k)∈W(u(k)).由文獻(xiàn)[1]中推論3.5,有

由式(8)知,

故

結(jié)合式(9)和式(10)有結(jié)論成立.

參考文獻(xiàn):

[1]ROCKAFELLARRT.Monotoneoperatorsandtheproximalpointalgorithm[J].SIAMJournalonControlandOptimization, 1976,14(5):877-898.

[2]WRIGHTSJ.Identifiablesurfacesinconstrainedoptimization[J].SIAMJournalonControlandOptimization, 1993,31(4):1063-1079.

[3]LEWISAS.Activesets,nonsmoothnessandsensitivity[J].SIAMJournalonOptimization, 2001,13(3):702-725.

[4]LEMARéCHALC,OUSTRYF,SAGASTIZBALC.TheU-Lagrangianofaconvexfunction[J].TransactionsoftheAmericanMathematicalSociety, 2000,352(2):711-729.

[5]LUY,PANGLP,XIAZQ.VU-decompositionmethodforasecond-orderconeprogrammingproblem[J].AppliedMathematicsandMechanics(EnglishEdition), 2010,31(2):263-270.

[6]LUY,PANGLP,LIANGXJ,etal.Anapproximatedecompositionalgorithmforconvexminimization[J].JournalofComputationalandAppliedMathematics, 2010,234(3):658-666.

[7]MIFFLINR,SAHASTIZBALC.Primal-dualgradientstructuredfunctions:second-orderresults;linkstoepi-derivativesandpartlysmoothfunctions[J].SIAMJournalonOptimization, 2002,13(4):1174-1197.

[8]MIFFLINR,SAGASTIZBALC.OnVU-theoryforfunctionswithprimal-dualgradientstructure[J].SIAMJournalonOptimization, 2000,11(2):547-571.

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

ASuperlinearSpace-DecompositionMethodforaClassofNonsmoothConvexFunction

Zhang Ying1,LiHuiling2

(1.NormalCollege,ShenyangUniversity,Shenyang110044,China; 2.ShenyangNo.1PrivateHighSchool,Shenyang110021,China)

Abstract:Thespacedecompositionmethodforaclassofnonsmoothconvexoptimizationproblemsisdiscussed.Theobjectivefunctionispiecewisetwicecontinuousdifferentiablefunction,whichhastheconnectionwithspacedecomposition.Firstly,thespacedecompositionisgiven.Secondly,theU-Lagrangianfunctionanditsfirstandsecond-orderpropertiesarediscussed.Atlast,analgorithmwithsuperlinearconvergencerateisproposedandthismethodisprovedtobeconverged.

Keywords:convexoptimization;space-decomposition;superlinearconvergence;nonsmooth

中圖分類號(hào):O 221

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

文章編號(hào):2095-5456(2015)06-0503-04

作者簡(jiǎn)介:張瑩(1973-),女,吉林長(zhǎng)春人,沈陽(yáng)大學(xué)講師.

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

收稿日期:2015-06-15