朱小蘭

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 401331)

?

一種解可分凸優(yōu)化問(wèn)題的分裂算法

朱小蘭

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 401331)

摘要：對(duì)于三個(gè)可分離變量的線性約束可分凸優(yōu)化問(wèn)題，提出了一種新的分裂算法，給出了算法的一個(gè)性質(zhì)，最后通過(guò)數(shù)值實(shí)驗(yàn)證明了該方法的可用性和有效性.

關(guān)鍵詞：凸規(guī)劃；可分離結(jié)構(gòu)；變分不等式；分裂算法

對(duì)于可分離變量的線性約束可分凸優(yōu)化問(wèn)題，可分離的凸函數(shù)的和，而且約束集是一些簡(jiǎn)單的約束和線性約束的交.這類優(yōu)化問(wèn)題在運(yùn)籌學(xué)、圖像修復(fù)和去噪、經(jīng)濟(jì)、交通均衡等方面有著廣泛的應(yīng)用.

He[1]給出了求解單調(diào)變分不等式收縮算法的統(tǒng)一框架.在此基礎(chǔ)上，還有許多作者提出了各種改進(jìn)算法，如改進(jìn)的臨近點(diǎn)分裂算法[2]、臨近點(diǎn)平行分裂算法[3]、非精確平行分裂增廣拉格朗日法[4]等.He[5]給出了m個(gè)可分離變量的線性約束可分凸優(yōu)化問(wèn)題的一種分裂算法.受He[5]的啟發(fā)，充分利用每次迭代中變量的更新值，提出了一種新的分裂方法.

1預(yù)備知識(shí)

本文主要考慮如下具有特殊的分離結(jié)構(gòu)的凸優(yōu)化問(wèn)題：

(1)

通篇假設(shè)：(1)f:Rn1→R，g:Rn2→R，h:Rn3→R都是閉真凸函數(shù)(但不需要是光滑函數(shù)).A∈Rl×n1，B∈Rl×n2，C∈Rl×n3都是給定的列滿秩矩陣，b∈Rl是給定的向量，X∈Rn1,Y∈Rn2，Z∈Rn3都是閉凸集合，且n1+n2+n3=n.

由上述假設(shè)，問(wèn)題(1)的解集非空.

為了方便分析，記W=X×Y×Z×Rl，w=(x,y,z,λ),v=(y,z,λ)，由最優(yōu)性條件得，問(wèn)題(1)等價(jià)于求解如下問(wèn)題[6]：找w*=(x*,y*,z*)∈W，使得

(2)

2算法的描述

初始步：設(shè)迭代計(jì)數(shù)k:=0，任意選取一個(gè)初始迭代點(diǎn)w0=(x0,y0,z0,λ0)∈Y×Z×Rl，ε為給定的誤差，通過(guò)以下產(chǎn)生新的迭代點(diǎn).

步1：通過(guò)下式更新xk+1

(3)

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

(4)

步3：通過(guò)下式更新yk+1

(5)

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

(6)

步5：通過(guò)下式更新zk+1

(7)

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

(8)

步7：終止準(zhǔn)則

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

對(duì)于上述的算法，作出以下幾點(diǎn)說(shuō)明.

說(shuō)明1：當(dāng)問(wèn)題(1)目標(biāo)函數(shù)和約束條件都退化到只含一個(gè)變量x，再令H=β·Il，其中Il是l×l階單位矩陣，則上述算法正是經(jīng)典拉格朗日算法[7].

說(shuō)明2：當(dāng)問(wèn)題(1)目標(biāo)函數(shù)和約束條件都退化到只含兩個(gè)變量x、y，則上述算法正是He[5]提出的算法.

3算法的性質(zhì)

引理令U∈Rn×n為對(duì)稱正定矩陣，則對(duì)?a,b,c∈Rn有

和

證根據(jù)范數(shù)的定義直接可證得.

(9)

對(duì)于yk+1∈Y，有

(10)

對(duì)于zk+1∈Z，有

(11)

證先證(9)式成立.

根據(jù)上式的一階最優(yōu)性條件，可得xk+1∈X滿足：

結(jié)合(4)式得：

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

故(9)式得證.

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

4數(shù)值實(shí)驗(yàn)

本節(jié)為了考查新算法(簡(jiǎn)記“VHTY”) 的數(shù)值有效性，用Matlab7.0進(jìn)行編程實(shí)現(xiàn).同時(shí)，將新算法與He[5]中的算法進(jìn)行比較，且將這種比較的方法簡(jiǎn)記為HTY.在數(shù)據(jù)結(jié)果中，用“Its.” 表示迭代次數(shù), “CPU(s)” 表示計(jì)算機(jī)的CPU運(yùn)行時(shí)間，“opt”表示最優(yōu)目標(biāo)函數(shù)值，“w*”表示最優(yōu)解.

例1考慮如下凸優(yōu)化問(wèn)題

實(shí)驗(yàn)參數(shù)設(shè)定：ε=1.0×10-5，μ=3，H=2，初始點(diǎn)：v0=(3,0,6).

實(shí)驗(yàn)結(jié)果由表1給出，由于測(cè)試問(wèn)題是隨機(jī)產(chǎn)生的，表中顯示的數(shù)據(jù)是10次測(cè)試的平均值.

表1　VHTY和HTY實(shí)驗(yàn)結(jié)果

5結(jié)論

本文提出了求解一類具有特殊結(jié)構(gòu)的可分離凸優(yōu)化問(wèn)題(1)的分裂算法.與He[5]所提出的算法相比，本文所提出方法是在求解了Y子問(wèn)題后再次更新了拉格朗日乘子，隨后再利用更新后的拉格朗日乘子求解Z子問(wèn)題，充分利用了迭代中的信息，從而在一定程度上加快了收斂速度.初步數(shù)值實(shí)驗(yàn)說(shuō)明了算法的可用性與有效性.

參考文獻(xiàn)：

[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]張敏, 韓德仁, 何洪津, 等. 解可分離結(jié)構(gòu)變分不等式的一種新的交替方向法[J]. 中國(guó)科學(xué)：數(shù)學(xué), 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

作者簡(jiǎn)介：朱小蘭(1991-) ，女，重慶開縣人，碩士，從事最優(yōu)化控制研究．

中圖分類號(hào)：O224

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

文章編號(hào)：1671-9476(2016)02-0044-04

DOI：10.13450/j.cnki.jzknu.2016.02.009