求解不可微凸優(yōu)化問題的充分下降共軛梯度法

黃元元

(河南科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 河南 洛陽 471023)

0 引言

考慮無約束優(yōu)化問題：

minf(x)，x∈Rn，

(1)

其中f：Rn→R是連續(xù)的凸函數(shù)，但不一定可微。該問題在機(jī)器學(xué)習(xí)、數(shù)據(jù)分析、信號處理和圖像處理等領(lǐng)域[1-4]均有應(yīng)用。若f是連續(xù)可微的，則共軛梯度(conjugate gradient,CG)法是求解問題(1)較常用且有效的一類方法。若f為連續(xù)的凸函數(shù)但不可微，則求解問題(1)的較早算法是鄰近點(diǎn)方法 (proximal point methods, PPM)[5-6]，將問題(1)轉(zhuǎn)化為極小化問題：

minF(x)，x∈Rn，

(2)

進(jìn)行求解，其中：

(3)

為函數(shù)f的Moreau-Yosida正則化函數(shù)。鑒于兩者解集相同[7]，文獻(xiàn)[8]引入近似求解函數(shù)F(x)的值及其梯度值的策略，在鄰點(diǎn)算法基礎(chǔ)上設(shè)計(jì)了求解問題(2)的一種切實(shí)可行的算法，該算法是Moreau-Yosida正則化和一般牛頓法的結(jié)合。之后，文獻(xiàn)[9]提出求解問題(2)的兩項(xiàng)和三項(xiàng)Polak-Ribière-Polyak(PRP)共軛梯度法，文獻(xiàn)[10-11]提出求解問題(2)的改進(jìn)的PRP共軛梯度法和Hestenes-Stiefel(HS)共軛梯度法，文獻(xiàn)[12]提出共軛參數(shù)非負(fù)的改進(jìn)共軛梯度法。但在求解光滑的無約束優(yōu)化問題上非常具有優(yōu)勢且滿足充分下降條件的CG_DESCENT方法[13-14]，在求解問題(1)方面卻未有相關(guān)文獻(xiàn)進(jìn)行研究。本文將基于CG_DESCENT方法求解光滑無約束優(yōu)化問題的更一般形式[15]，給出求解問題(1)的一類具有充分下降條件的共軛梯度法，并證明它們在不依賴于任何線搜索的情況下滿足充分下降條件且全局收斂。

1 預(yù)備知識

下面給出本文要用到的基本命題和引理，具體證明過程請參閱相關(guān)文獻(xiàn)。

命題1[7]設(shè)函數(shù)F如式(3)定義，則函數(shù)F是有界的凸函數(shù)且處處可微，其梯度為g(x)=▽F(x)=λ(x-p(x))。該梯度映射g:Rn→Rn是逆強(qiáng)單調(diào)的，即

并且是λ-Lipschitz 連續(xù)的，即

(4)

命題2[7]若x*是問題(1)的最優(yōu)解，則x*也是問題(2)的最優(yōu)解，且與以下幾條陳述相互等價(jià)：

(i)x*=p(x*)；(ii)▽F(x*)=0；(iii)f(x*)=f(p(x*))；(iv)f(x*)=F(x*)。

(5)

(6)

(7)

(i)F(x)≤Fa(x,ε)≤F(x)+ε；

2 算法設(shè)計(jì)

本文利用Moreau-Yosida正則化策略，給出求解不可微優(yōu)化問題(1)的算法。若已知當(dāng)前迭代點(diǎn)xk，通過xk+1=xk+αkdk計(jì)算新的迭代點(diǎn)，步長αk通過線搜索得到，搜索方向dk為：

(8)

算法1：

步驟3 對α∈{ρtj|j=0,1,2,…}，選取使得不等式

(9)

成立的最大的α作為步長αk。計(jì)算xk+1=xk+αkdk。令k:=k+1，并轉(zhuǎn)至步驟2。

3 收斂性分析

為了分析算法1的收斂性質(zhì)，首先給出以下假設(shè)。

(10)

引理2若ξk≠0，θk≥1/4，且dk由式(8)生成，則對任意的k≥0都有：

(11)

(12)

引理2證畢。

(13)

證明假設(shè)在第k次迭代仍未找到最優(yōu)解，對所有的j=0,1,2,…，不等式(9)均不成立，即

Fa(xk+ρtjdk,εk+1)>Fa(xk,εk)+σ1ρtjga(xk,εk)Tdk-σ2ρ2t2j‖dk‖2+εk。

(14)

將式(14)兩邊同時(shí)關(guān)于j取極限，得：

Fa(xk,εk+1)≥Fa(xk,εk)+εk。

(15)

由引理1中(i)可知：Fa(xk,εk+1)≤Fa(xk)+εk+1且Fa(xk,εk)≥Fa(xk)。將這兩個不等式與式(15)相結(jié)合得εk+1≥εk,這與εk+1<εk相矛盾。從而步長αk是有定義的，可以在有限次嘗試后得到。

(16)

由引理1可知：

Fa(xk+αkdk，εk+1)≤F(xk+αkdk)+εk+1；

(17)

F(xk)≤Fa(xk,εk)；

(18)

(19)

由式(17)～式(19)得：

F(xk+αkdk)-F(xk)-αkg(xk)Tdk。

(20)

由式(11)可知：ga(xk,εk)Tdk<0。因?yàn)棣?∈(0,1)，則

ga(xk,εk)Tdk≤σ1ga(xk,εk)Tdk，

將其與不等式(16)和不等式(20)相結(jié)合得式(13)。

引理3證畢。

證明由線搜索準(zhǔn)則可知，對于步長αk，式(9)成立，即

(21)

結(jié)合引理2，有：

Fa(xk+1,εk+1)≤Fa(xk,εk)+εk。

(22)

(23)

選取K∈K1且K≥max{K1,K2,K3}。對所有的k≥K，結(jié)合式(22)，有：

(24)

引理4證畢。

定理1若假設(shè)1和假設(shè)2成立，則算法1產(chǎn)生的序列{xk}的任何聚點(diǎn)都是問題(1)的最優(yōu)解。

證明設(shè)x*是序列{xk}的一個聚點(diǎn)，必存在{xk}的一個子列{xk}k∈K收斂到x*。由式(4)和引理1中(iii)可知：

由引理1中(i)可知：

F(xk)≤Fa(xk,εk)；

(25)

Fa(xk+ρ-1αkdk,εk+1)≤F(xk+ρ-1αkdk)+εk+1。

(26)

由步長αk的選取準(zhǔn)則可知：

將其與式(25)、式(26)及εk+1<εk相結(jié)合，得：

從而有：

(27)

定理1證畢。

4 結(jié)論

通過非精確求解Moreau-Yosida正則化函數(shù)的函數(shù)值和梯度值，將被廣泛認(rèn)同的求解無約束優(yōu)化問題的有效共軛梯度算法推廣到求解非光滑優(yōu)化問題上，從理論上分析了算法的可行性，具有一定的理論價(jià)值。