非凸優(yōu)化問題的慣性鄰近梯度算法

劉 倩，張 征

( 西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009 )

?

非凸優(yōu)化問題的慣性鄰近梯度算法

劉 倩，張 征

( 西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009 )

研究了慣性鄰近梯度法求解極小化一個(gè)非光滑函數(shù)與一個(gè)光滑函數(shù)之和的優(yōu)化問題。通過假定目標(biāo)函數(shù)滿足KL不等式,證明了該算法的收斂性。

慣性鄰近梯度法；非凸優(yōu)化；KL不等式

0 引 言

本文中,我們考慮如下優(yōu)化問題:

(1)

近年來,問題(1)受到了極大的關(guān)注。鄰近梯度法是求解問題(1)的經(jīng)典方法。2015年,PeterOchs等人在文獻(xiàn)[1]中提出了求解問題(1)的如下慣性鄰近梯度法:

xn+1=proxαnf(xn-αn▽g(xn)+βn(xn-xn-1)。

(2)

由于g為非凸函數(shù),通過假定目標(biāo)函數(shù)滿足KL不等式(定義3), 他們證明了算法的收斂性。若目標(biāo)函數(shù)f,g都為凸函數(shù),通過借助Nesterov加速梯度方法的思想,Lorenz和Pock在文獻(xiàn)[2]中提出了如下慣性鄰近梯度法,

(3)

在一定的假設(shè)下,文獻(xiàn)[2]中證明了算法(3)的收斂性。若假定為光滑函數(shù)(不一定凸),則算法(3)為

(4)

本文的目的是通過假定g為光滑函數(shù), 借助文獻(xiàn)[1]中證明算法(2)的思想來研究算法(4)的收斂性。值得注意的是,由文獻(xiàn)[2]知,算法(4)比算法(2)數(shù)值效果好。這也是促使我們研究算法(4)的動(dòng)機(jī)。

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

在本節(jié)中, 我們給出一些概念和預(yù)備知識(shí)。

(ⅲ)h在x∈domh處的極限次微分,記作?h(x),定義為

注1 由定義1知,

0∈?h(x)。

(5)

(ⅲ)若h為凸函數(shù),則?h(x)退化為凸分析中經(jīng)典的次微分定義。

注2 滿足(5)的點(diǎn)x稱為h的穩(wěn)定點(diǎn)。h的所有穩(wěn)定點(diǎn)集合記為crit(h)。

(ⅰ)φ(0)=0 ;(ⅱ)φ在(0,η)上連續(xù)可微且在0處連續(xù);(ⅲ)φ′(s)>0,?x∈(0,η);

(ⅳ) 對任意的x∈U∩[h(x*)

φ′(h(x)-h(x*))d(0,?h(x))≥1。

注3 記Φη為滿足(i),(ii),(iii)的函數(shù)集合。若h在dom?h的每一點(diǎn)滿足KL性質(zhì),則稱h為KL函數(shù)。

有

引理4[8]設(shè){ak}k∈N和{bk}k∈N為實(shí)數(shù)數(shù)列滿足bk≥0,?k∈N,{ak}k∈N下有界且ak+1+bk≤ak,對任意的k∈N。則{ak}k∈N單調(diào)遞減且收斂,∑k∈Nbk<+∞。

3 收斂性分析

為方便起見, 我們將算法1.4重述于下。

其中,

(6)

慣性鄰近梯度算法:

(7)

引理5 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生,則有

(f+g)(xn+1)+M1‖xn+1-xn‖2≤(f+g)(xn)+M2‖xn-xn-1‖2,?n≥1。

(8)

其中,

證明 由(7)的第二式得

(9)

因?yàn)閒為凸函數(shù),則有

(10)

在(10)式中令得x=xn,

(11)

由引理2知,

(12)

將(11)與(12)相加可得,

(f+g)(xn)≥(f+g)(xn+1)+〈▽g(xn)-▽g(yn),xn-xn+1〉+

(13)

由于yn-xn+1=xn-xn+1+βn(xn-xn-1),則有

〈yn-xn+1,xn-xn+1〉=‖xn-xn+1‖2+βn〈xn-xn-1,xn-xn+1〉。

(14)

根據(jù)Cauchy-Schwarz不等式有,

(15)

且

(16)

又因?yàn)楱実為Lipschitz連續(xù)且yn=xn+βn(xn-xn-1),則

‖▽g(xn)-▽g(yn)‖≤L‖xn-yn‖=Lβn‖xn-xn-1‖。

(17)

將(14)-(17)代入(13)得

即證。

引理6 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生, 則有

ξn+1∈?(f+g)(xn+1)，

證明 由(9)及注1(ⅳ)知,ξn+1∈?(f+g)(xn+1) 。 因此,

其中,第二個(gè)不等式是根據(jù)▽g的Lipschitz連續(xù)性,第三個(gè)不等式是根據(jù)(7)的第一式。即證。

引理7 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生。則

(ⅱ)數(shù)列{(f+h)(xn)+M2‖xn-xn-1‖2}n∈N單調(diào)遞減且收斂;

(ⅲ)數(shù)列{(f+g)(xn)}n∈N收斂。

證明 對任意的n≥1,記αn=(f+g)(xn)+M2‖xn-xn-1‖2,bn=(M1-M2)‖xn+1-xn‖2。由引理3.1知,

an+1+bn=(f+g)(xn+1)+M1‖xn+1-xn‖2≤(f+g)(xn)+M1‖xn-xn-1‖2=an。

根據(jù)引理4, 可知引理7的結(jié)論成立。即證。

引理8 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生。假定f+g滿足強(qiáng)制性條件,即

則存在{xn}n∈N的子序列收斂到f+g的穩(wěn)定點(diǎn)。事實(shí)上,{xn}n∈N的每一聚點(diǎn)都為f+g的穩(wěn)定點(diǎn)。

證明 由于f+g為正常下半連續(xù)凸函數(shù)且滿足強(qiáng)制性條件,則有f+g下有界。根據(jù)引理5有,

(f+g)(xn)≤(f+g)(xn)+M2‖xn-xn-1‖2≤(f+g)(x1)+M2‖x1-x0‖2,?n≥1。

ξnk-▽g(xnk)∈?f(xnk)

(18)

引理9 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生。 考慮函數(shù)

則存在M3,M4>0使得下述結(jié)論成立:

(ⅰ)S(xn+1,xn)+M3‖xn+1-xn‖2≤S(xn,xn-1);

(ⅱ)d(0,?S(xn+1,xn))≤M4(‖xn+1-xn‖+‖xn-xn-1‖)。

證明 (i)令M3=M1-M2,由引理5及注4知, 結(jié)論成立。

(ⅱ) 因?yàn)?/p>

?xS(x,y)=?(f+g)(x)+2M2(x-y),?yS(x,y)=2M2(y-x)。

(19)

則,vn+1∈?S(xn+1,xn)。更多地,

≤‖ξn+1‖+4M2‖xn+1-xn‖

≤M4(‖xn+1-xn‖+‖xn-xn-1‖)

引理10 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生。 假定f+g滿足強(qiáng)制性條件。 考慮函數(shù)

則下述結(jié)論成立:

(iii)S在ω({(xn,xn-1)}n∈N)上有限且為常值。

證明 (i)由定義易知該結(jié)論成立。

所以,S在ω({(xn,xn-1)}n∈N)上有限且為常值。即證。

接下來, 我們證明本文的主要結(jié)論。

定理1 設(shè)序列{xn}n∈N由算法1.4迭代產(chǎn)生。假定f+g滿足強(qiáng)制性條件且函數(shù)

由于Ω為緊集且S在Ω上為常數(shù), 由引理1知,當(dāng)n>n0時(shí)有,

(20)

(21)

由引理9(i)知,

M3‖xn+1-xn‖2≤S(xn,xn-1)-S(xn+1,xn)。

(22)

將(20)和(22)代入(21), 由引理9(ii)可得

上式可等價(jià)地寫為,

由Cauchy-Schwarz不等式，有

由于φ≥0,則對任意的n>n0,有

[1] OCHS P,CHEN Y J,BROX T,et al.IPiano: inertial proximal algorithm for nonconvex optimization[J].SIAM J.Imaging Sci.,2015,7:1388-1419.

[2] LORENZ D A,POCK T.An inertial forward-backward algorithm for monotone inclusions[J].J Math Imaging Vis.51:311-325.DOI 10.1007/s10851-014-0523-2.

[3] ROCKAFELLAR R T,WETS R J B.Variational analysis[M].Berlin:Springer,1998.

[4] ATTOUCH H,BOLTE J,REDONT P,et.al.Proximal alternating minimization and projection methods for nonconvex problems:an approach based on the Kurdyka-Lojasiewicz inequality[J].Mathematics of Operations Research,2010,35(2):438-457.

[5] ATTOUCH H,BOLTE J,SVAITER B F.Convergence of descent methods for semi-algebraic and tame problems:proximal algorithms,forward-backward splitting,and regularized Gauss-Seidel methods[J].Mathematical Programming,2013,137(1):91-129.

[6] NESTEROY Y.Introductory Lectures on Convex Optimization:A Basic Course[M].Boston:Kluwer Academic Publishers,2004.

[7] BOT R I,CSETNET E R.An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problem[J/OL].(2015-03-31)[2015-5-25].http://link.springer.com/article/10.1007/s10957-015-0730-z DOI:10.1007/s10957-015-0730-z.

[8] BAUSCHKE H H,COMBETTES P L.Convex analysis and monotone operator theory in Hilbert space[M].New York:Springer,2011.

Inertial Proximal Gradient Method for Nonconvex Optimization Problem

LIU Qian,ZHANG Zheng

(College of Mathematics and Information,China West Normal University,Nanchong Sichuan 637009,China)

In this paper,we investigate the inertial proximal gradient method for minimizing the sum of a nonsmooth convex function with a smooth one.By assuming the objective functions satisfy the KL inequality,we illustrate the convergence of the algorithm.

Inertial proximal gradient method;Nonconvex optimization;KL inequality

1673-5072(2016)03-0303-06

2016-03-31 基金項(xiàng)目：國家自然科學(xué)基金( 11371015);教育部科學(xué)技術(shù)重點(diǎn)項(xiàng)目(211163);四川省青年科技基金(2012JQ0035) 作者簡介：劉 倩(1989—),女,新疆阿勒泰人,碩士研究生,主要從事優(yōu)化理論研究。 通訊作者：張 征(1974—)，女，四川南充人，副教授，主要從事優(yōu)化理論研究。E-mail: hi_zhangzheng@126.com

O177.91

A

10.16246/j.issn.1673-5072.2016.03.013