一种解可分凸优化问题的分裂算法

朱小兰

(重庆师范大学 数学学院，重庆 401331)



一种解可分凸优化问题的分裂算法

朱小兰

(重庆师范大学 数学学院，重庆 401331)

摘要：对于三个可分离变量的线性约束可分凸优化问题，提出了一种新的分裂算法，给出了算法的一个性质，最后通过数值实验证明了该方法的可用性和有效性.

关键词：凸规划；可分离结构；变分不等式；分裂算法

对于可分离变量的线性约束可分凸优化问题，可分离的凸函数的和，而且约束集是一些简单的约束和线性约束的交.这类优化问题在运筹学、图像修复和去噪、经济、交通均衡等方面有着广泛的应用.

He[1]给出了求解单调变分不等式收缩算法的统一框架.在此基础上，还有许多作者提出了各种改进算法，如改进的临近点分裂算法[2]、临近点平行分裂算法[3]、非精确平行分裂增广拉格朗日法[4]等.He[5]给出了m个可分离变量的线性约束可分凸优化问题的一种分裂算法.受He[5]的启发，充分利用每次迭代中变量的更新值，提出了一种新的分裂方法.

1预备知识

本文主要考虑如下具有特殊的分离结构的凸优化问题：

(1)

通篇假设：(1)f:Rn1→R，g:Rn2→R，h:Rn3→R都是闭真凸函数(但不需要是光滑函数).A∈Rl×n1，B∈Rl×n2，C∈Rl×n3都是给定的列满秩矩阵，b∈Rl是给定的向量，X∈Rn1,Y∈Rn2，Z∈Rn3都是闭凸集合，且n1+n2+n3=n.

由上述假设，问题(1)的解集非空.

为了方便分析，记W=X×Y×Z×Rl，w=(x,y,z,λ),v=(y,z,λ)，由最优性条件得，问题(1)等价于求解如下问题[6]：找w*=(x*,y*,z*)∈W，使得

(2)

2算法的描述

初始步：设迭代计数k:=0，任意选取一个初始迭代点w0=(x0,y0,z0,λ0)∈Y×Z×Rl，ε为给定的误差，通过以下产生新的迭代点.

步1：通过下式更新xk+1

(3)

步2：利用xk+1更新拉格朗日乘子

(4)

步3：通过下式更新yk+1

(5)

步4：利用xk+1，yk+1更新拉格朗日乘子

(6)

步5：通过下式更新zk+1

(7)

步6：利用xk+1，yk+1，zk+1更新拉格朗日乘子

(8)

步7：终止准则

若‖f(xk+1)+g(yk+1)+h(zk+1)-[f(xk)+g(yk)+h(zk)]‖<ε，则算法停止；否则k:=k+1，转步1.

对于上述的算法，作出以下几点说明.

说明1：当问题(1)目标函数和约束条件都退化到只含一个变量x，再令H=β·Il，其中Il是l×l阶单位矩阵，则上述算法正是经典拉格朗日算法[7].

说明2：当问题(1)目标函数和约束条件都退化到只含两个变量x、y，则上述算法正是He[5]提出的算法.

3算法的性质

引理令U∈Rn×n为对称正定矩阵，则对∀a,b,c∈Rn有

和

证根据范数的定义直接可证得.

(9)

对于yk+1∈Y，有

(10)

对于zk+1∈Z，有

(11)

证先证(9)式成立.

根据上式的一阶最优性条件，可得xk+1∈X满足：

结合(4)式得：

F(x)-F(xk+1)=

故(9)式得证.

同理可证(10)式和(11)式.

4数值实验

本节为了考查新算法(简记“VHTY”) 的数值有效性，用Matlab7.0进行编程实现.同时，将新算法与He[5]中的算法进行比较，且将这种比较的方法简记为HTY.在数据结果中，用“Its.” 表示迭代次数, “CPU(s)” 表示计算机的CPU运行时间，“opt”表示最优目标函数值，“w*”表示最优解.

例1考虑如下凸优化问题

实验参数设定：ε=1.0×10-5，μ=3，H=2，初始点：v0=(3,0,6).

实验结果由表1给出，由于测试问题是随机产生的，表中显示的数据是10次测试的平均值.

表1　VHTY和HTY实验结果

5结论

本文提出了求解一类具有特殊结构的可分离凸优化问题(1)的分裂算法.与He[5]所提出的算法相比，本文所提出方法是在求解了Y子问题后再次更新了拉格朗日乘子，随后再利用更新后的拉格朗日乘子求解Z子问题，充分利用了迭代中的信息，从而在一定程度上加快了收敛速度.初步数值实验说明了算法的可用性与有效性.

参考文献：

[1]HeBS,XuMH.Ageneralframeworkofcontractionmethodsformonotonevariationalinequalities[J].Pacificjournalofoptimization, 2008, 4(2): 195-212.

[2]LiM,YuanXM.Animprovedproximal-baseddecompositionmethodforstructuredmonotonevariationalinequalities[J].AppliedMathematicsandMechanics, 2007, 28(12):1659-1668.

[3]HanD,HeHJ,XuLL.Aproximalparallelsplittingmethodforminimizingsumofconvexfunctionswithlinearconstraints[J].JournalofComputationalandAppliedMathematics, 2014, 256: 36-51.

[4]PengZ,WuDH.Aninexactproximalalternatingdirectionsmethodformonotonestructuredvariationalinequalities[C]//ProceedingsoftheInternationalMultiConferenceofEngineersandComputerScientists, 2010: 1977-1984.

[5]HeBS,TaoM,YuanXM.Asplittingmethodforseparableconvexprogramming[J].IMAJournalofNumericalAnalysis, 2015, 35(1): 394-426.

[6]FacchineiF,PangJS.Finite-dimensionalvariationalinequalitiesandcomplementarityproblems[M].SpringerScience&BusinessMedia, 2007.

[7]HestenesMR.Multiplierandgradientmethods[J].Journalofoptimizationtheoryandapplications, 1969, 4(5): 303-320.

[8]CaiXJ,HanD,YuanXM.ThedirectextensionofADMMforthree-blockseparableconvexminimizationmodelsisconvergentwhenonefunctionisstronglyconvex[J].OptimizationOnline, 2014.

[9]PowellM.Amethodfornonlinearconstraintsinminimizationproblems[M].Optimization(R.Fletchered.).NewYork:AcademicPress, 1969:283-298.

[10]HanD,YuanX,ZhangW,etal.AnADM-basedsplittingmethodforseparableconvexprogramming[J].ComputationalOptimizationandApplications, 2013, 54(2): 343-369.

[11]张敏, 韩德仁, 何洪津, 等. 解可分离结构变分不等式的一种新的交替方向法[J]. 中国科学：数学, 2012, 42(2): 133-149.

A solution separable convex optimization problem of split algorithm

ZHU Xiaolan

(Chongqing Normal University, Chongqing 401331,China)

Abstract:For three separable variables separable convex optimization problem with linear constraints, we propose a new division algorithm gives a nature algorithms, numerical experiments finally proved the usability and effectiveness of the method.

Key words:convex programming; separable structure; variational inequality; split algorithm

收稿日期：2015-12-01;修回日期：2015-12-17

作者简介：朱小兰(1991-) ，女，重庆开县人，硕士，从事最优化控制研究．

中图分类号：O224

文献标志码：A

文章编号：1671-9476(2016)02-0044-04

DOI：10.13450/j.cnki.jzknu.2016.02.009