一类非光滑凸函数的超线性空间分解方法

张　莹, 李慧玲

(1. 沈阳大学 师范学院, 辽宁 沈阳　110044; 2. 沈阳第一私立高中, 辽宁 沈阳　110021)

一类非光滑凸函数的超线性空间分解方法

张莹1, 李慧玲2

(1. 沈阳大学 师范学院, 辽宁 沈阳110044; 2. 沈阳第一私立高中, 辽宁 沈阳110021)

摘要:讨论了一类非光滑凸优化的空间分解方法,其目标函数是分片二次连续可微的凸函数.首先给出该优化的空间分解;然后给出优化问题的U-拉格朗日函数及其一阶、二阶性质;最后给出该优化的具有超线性收敛速度的分解算法,并证明了算法的收敛性.

关键词:凸优化; 空间分解; 超线性收敛; 非光滑

考虑如下的优化问题

本文主要目的是应用VU-理论给出优化式(1)的空间分解方法.首先给出VU-空间分解;然后利用U-拉格朗日函数讨论目标函数f的二阶展开;最后给出空间分解算法,并讨论该算法的收敛性.

1VU空间分解

在凸优化式(1)中,目标函数f是分片二次连续可微的.具体的,对∀x∈Rn,

其中,fi:Rn→R,i∈I是二次连续可微的,称为结构函数.式(2)的一个典型例子是有限最大值函数f(x)=maxfj(x), j=0,1,…,m,其中fj(x)是二次连续可微的凸函数.然而,式(2)不仅限于最大值函数.

给定形如式(2)的凸函数,它在点x∈Rn处的次微分是在点x处积极结构函数的梯度的凸组合,即

其中,

给定x∈Rn,g∈∂f(x),x点处的VU空间分解如下:

假设A假设在x点处,集合{是线性无关的.

若假设A成立,则有

根据投影理论,∀x∈Rn可以被分解为x=(xu,xv)T,在本文中我们使用记号xu⊕xv表示xu与xv的直和.即

本节给出U-拉格朗日函数的定义及一阶、二阶性质.

由文献[1]知,式(1)的U-拉格朗日函数为

其最优解集为

定理1若假设A成立,则对于∀u足够小,式(4)中的W(u)有唯一解w(u),满足下面方程组

证明对式(5)左端关于v求导,有

2.2二阶展开

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

(1) Lu的梯度为

其中,

特别地,

其中,

(2) Lu的Hessian阵为

其中,

特别地,当u=0时,有

其中,

证明(1) 对式(6)关于u求导,根据链式法则知

根据文献[8]中的式(6.11)有结果成立.

(2) 对式(7)两端关于u求导,有

其中,

由文献[8]中定理6.3的证明有

因此,

当u=0时,

其中,

下面的定理给出函数f的二阶展开式.

证明由Lu的定义,有

由于Lu是二阶连续可微的,则有

即

3算法和收敛性

算法

Step 0(初始化)

Step 1(停止准则)

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

其中

Step 4(V-步)计算

其中

Step 6(校正)置k=k+1,转Step 1.

下面给出上述算法的收敛性证明.

并且

因此,v(k)∈W(u(k)).由文献[1]中推论3.5,有

由式(8)知,

故

结合式(9)和式(10)有结论成立.

参考文献:

[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.

【责任编辑: 肖景魁】

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

中图分类号:O 221

文献标志码:A

文章编号:2095-5456(2015)06-0503-04

作者简介:张莹(1973-),女,吉林长春人,沈阳大学讲师.

基金项目:国家自然科学基金资助项目(11301347).

收稿日期:2015-06-15