程 鵬

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

一種解可分凸優(yōu)化問(wèn)題的外梯度并行分裂算法*

程 鵬

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

并行分裂法是求解兩個(gè)可分離變量線性約束凸優(yōu)化問(wèn)題的重要方法,該方法通常要求兩個(gè)凸函數(shù)有鄰近映射，對(duì)于其中一個(gè)函數(shù)具有鄰近映射，另一個(gè)函數(shù)光滑但不具有鄰近映射的情況,此處提出了一種基于并行分裂的外梯度算法,并在假設(shè)光滑函數(shù)梯度Lipschitz連續(xù)條件下證明了該算法的O(1/ε)迭代復(fù)雜度。

凸優(yōu)化;可分離結(jié)構(gòu);增廣拉格朗日法;并行分裂法

可分離變量的線性約束可分凸優(yōu)化問(wèn)題，是研究數(shù)學(xué)、工程科學(xué)和管理科學(xué)的一個(gè)重要工具，其目標(biāo)函數(shù)是可分離函數(shù)的和，且約束是線性約束。

He B S[1]給出了求解含兩個(gè)可分離變量的凸優(yōu)化問(wèn)題的并行分裂增廣拉格朗日算法，這個(gè)算法能夠很好地利用問(wèn)題的可分離結(jié)構(gòu)，因此在應(yīng)用領(lǐng)域得到了大家的廣泛認(rèn)可。在此基礎(chǔ)上許多讀者提出了各種改進(jìn)算法，如鄰近點(diǎn)并行分裂算法[2]、非精確并行分裂算法[3]、預(yù)測(cè)校正并行分裂算法[4]等。Gabay D及Mercier B[5]提出的交替方向分裂法也是求解可分凸優(yōu)化問(wèn)題的一種有效方法，根據(jù)交替方向法的求解優(yōu)勢(shì),Chen G和Teboul M等人[6-8]通過(guò)求解一系列凸極小化問(wèn)題得出了一種改進(jìn)的交替方向法，Ma S Q, et al[9]對(duì)于只有一個(gè)目標(biāo)函數(shù)有鄰近映射的優(yōu)化問(wèn)題提出了基于外梯度的交替方向分裂法。受He B S[1]和Ma S Q[9]的啟發(fā)，此處提出基于外梯度的并行分裂算法。

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

這篇文章中考慮以下凸規(guī)劃約束模型：

minf(x)+g(y)

s.t.Ax+By=b

x∈X,y∈Y

(1)

其中f和g是凸函數(shù),X∈Rn,Y∈Rp,A∈Rm×n,B∈Rm×p,b∈Rm，X和Y是凸集且在它們上的投影很容易求得。求解問(wèn)題(1)通常采用經(jīng)典的增廣拉格朗日法(ALM)，產(chǎn)生的迭代格式如下：

其中L(x,y,λ)是問(wèn)題(1)的增廣拉格朗日函數(shù)，定義為

λ是與線性約束Ax+By=b有關(guān)的拉格朗日乘子，γ是罰參數(shù)。

2009年，He B S[1]等人提出關(guān)于兩個(gè)可分離凸優(yōu)化問(wèn)題的并行分裂算法迭代如下：

(2)

受文獻(xiàn)[9]的啟發(fā)，此處提出了外梯度并行分裂法并在假設(shè)函數(shù)梯度滿足lipschitz連續(xù)的條件下證明了ε最優(yōu)解的迭代復(fù)雜度。

2 外梯度并行分裂算法

若f,g均容易求得鄰近映射，則問(wèn)題(1)用迭代步驟(2)可以求得。這部分考慮函數(shù)f有鄰近映射，函數(shù)g光滑但不容易得到鄰近映射的情況，提出以下的基于外梯度的并行分裂增廣拉格朗日法解決問(wèn)題(1)。以任意初始點(diǎn)y0∈Y，λ0∈Rm開(kāi)始，迭代形式如下：

(3)

L(x,y,λ)=f(x)+g(y)-λT(Ax+By-b)

所以式子(3)中第一個(gè)子問(wèn)題可以表示為

因?yàn)楣饣购瘮?shù)g不容易求解，所以優(yōu)化問(wèn)題miny∈YLγ(x,y,λ)對(duì)于給定的x和λ也不容易求解，因此在外梯度并行分裂增廣拉格朗日法中不能直接求解miny∈YLγ(x,y,λ)。采用的方法是固定x和λ，用拉格朗日函數(shù)投影步去校正y。

關(guān)于λ,拉格朗日函數(shù)L(x,y,λ)的梯度為

▽?duì)薒(x,y,λ)=-(Ax+By-b)

關(guān)于λ的兩個(gè)迭代步為

▽?duì)薒(xk,yk,λk)

因此式(3)等價(jià)于:

(4)

3 算法的迭代復(fù)雜度

這部分分析新方法的迭代復(fù)雜度，證明在假設(shè)光滑函數(shù)g的梯度滿足Lipschitz連續(xù)條件下，式(3)對(duì)于式(1)在O(1/ε)迭代內(nèi)找到一個(gè)ε最優(yōu)解,問(wèn)題(1)的對(duì)偶問(wèn)題為

(5)

下面定義式(1)的ε最優(yōu)解。

(6)

其中，x*×y*是式(1)的最優(yōu)解，Λ*是對(duì)偶問(wèn)題(5)的最優(yōu)解。

(7)

證明 由式(4)的子問(wèn)題，有

(8)

所以：

(9)

第2個(gè)式子和第4個(gè)式子求和可以變形為

所以：

(10)

結(jié)合式(9)(10)得:

其中，

因此有

(11)

令y=yk+1,λ=λk+1，則有

引理1得證。

引理2 假設(shè)▽g(y)是Lipschitz連續(xù)，Lg是Lipschitz常數(shù)，則有

?y1,y2∈Y

(12)

證明 對(duì)于?y1,y2∈Y,?λ1,λ2∈Λ，有

結(jié)合引理1則引理2得證。

(14)

證明 式(8)中的第3個(gè)式子和第4個(gè)式子求和得：

(15)

(16)

因此引理3得證。

(17)

證明 由式(3)中關(guān)于x的子問(wèn)題的最優(yōu)性條件：

〈?f(xk+1)-ATλK+γAT(Axk+1+Byk-b)+

H(xk+1-xk),x-xk+1〉≥0，x∈X

▽?duì)薒(xk,yk,λk)

=λk-γ(Axk+Byk-b)

所以可以得到:

γATA(xk+1-xk),x-xk+1〉≥0,x∈X

結(jié)合引理3，有

因?yàn)?/p>

〈(H+γATA)(xk-xk+1),x-xk+1〉=

(18)

當(dāng)k=0,1，…,N時(shí)，對(duì)式(18)求和，有

(19)

L(x,y,λN)-L(xN,yN,λ)

因此得到：

因?yàn)閤*,y*,λ*有界且N=O(1/ε)，所以可以保證：

4 結(jié) 論

提出了求解具有特殊結(jié)構(gòu)的可分離凸優(yōu)化問(wèn)題(1)的一種外梯度并行分裂算法,與文獻(xiàn)[1]提出的并行分裂算法相比，本文提出的方法可以求解可分離的目標(biāo)函數(shù)沒(méi)有鄰近映射的情況，并在假設(shè)另一個(gè)函數(shù)的梯度滿足Lipschitz連續(xù)的條件下，證明了該算法的O(1/ε)迭代復(fù)雜度。

[1] HE B S.Parallel Splitting Augmented Lagrangian Methods for Monotone Structued Variational Inequalities[J].Computational Optimization and Applications,2009(42):195-212

[2] HAN D,HE H J,XU L L.A Proximal Parallel Splitting Method for Minimizating Sum of Convex Functions with Linear Constraints[J].Journal of Computational and Applied Mathematics,2014(256):36-51

[3] PENG Z,WU D H.An Inexact Proximal Alternating Directions Method for Monotone Structured Variational Inequalities[C]∥Proceedings of the International MultiConference of Engineers and Computer Scientists.2010:1977-1984

[4] 王凱.解可分離凸優(yōu)化的兩個(gè)并行分裂算法[D].南京:南京師范大學(xué),2012 WANG K.Two Parallel Splitting Algorithms for Solving Separable Convex Optimization[D].Nanjing:Nanjing Normal University,2012

[5] GABAY D,MERCIER B.A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite-Element Approximations[J].Computers Mathematics with Applica-tions,1976(2):17-40

[6] CHEN G,TEBOULLE M.A Proximal-Based Decomposition Method of Convex Minimiaztion Problems[J].Mathematical Programming,1994(64):81-101

[7] HE B S,YANG H,ZHANG C S.A Modified Augmented Lagrangian Method for a Class of Monotone Variational Inequalities[J].European Journal of Operational Research,2004(159):35-51

[8] ROCKAFELLAR R T.Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming[J].Mathematics of Operations Research,1976(1):76-112

[9] MA S Q,ZHANG S Z.An Extragradient-Based Alternating Direction Method for Convex Minimization[J].Foundations of Computational Mathematics,2015(1):1-25

[10] 劉川何.求解分裂可行問(wèn)題的一種松弛投影算法[J].重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版),2016(1):16-18

LU C H.A Relaxation Projection Algorithm for Solving the Split Feasibility Problem[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2016(1):16-18

責(zé)任編輯：李翠薇

An Extragradient Parallel Split Algorithm for Solving Separable Convex Optimization Problem

CHENG Peng

(College of Mathematics,Chongqing Normal University, Chongqing 401331, China)

Parallel splitting method is an important method for solving the convex optimization problem with two separable variables.The methods usually requires that the two convex functions have relatively easy proximal mappings, for the structure that only one of the two functions has easy proximal mapping and the other one is smoothly convex but does not have an easy proximal mapping.We propose in this paper an extragradient algorithm based on parallel splitting.Under the assumption that the smooth function has a Lipschitz continuous gradient condition, we prove theO(1/ε)iterationcomplexityofthemethod.

convex optimization; separable structure; augmented Lagrangian method; parallel splitting method

10.16055/j.issn.1672-058X.2017.0000.007

2016-05-03；

2016-06-25.

重慶市自然科學(xué)基金(CSTC2015JCYJBX0029).

程鵬(1990-),女，重慶墊江人，碩士研究生，從事最優(yōu)化理論與應(yīng)用研究.

O224

A

1672-058X(2017)01-0034-07