一類截斷函數(shù)最優(yōu)化問題的求解方法

左鑫怡, 蔣 毅*, 楊 嵐

(1. 四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 四川 成都 610066; 2. 四川師范大學(xué) 可視化計算與虛擬現(xiàn)實四川省重點實驗室, 四川 成都 610066)

1 預(yù)備知識

本文考慮一類截斷函數(shù)的最優(yōu)化問題

min{fi(x),hi(x)},

(1)

其中x∈Rn是變量,

f0:Rn→R∪{+∞},

fi,hi:Rn→R,i=1,2,…,m

min

截斷函數(shù)的最優(yōu)化問題(1)在稀疏性正則化[1-4]、基于穩(wěn)健估計的圖像恢復(fù)[5]以及穩(wěn)健回歸[6-9]等方面都有廣泛應(yīng)用.

關(guān)于這類截斷函數(shù)的最優(yōu)化問題(1),許多學(xué)者考慮hi(x)=α(α為常數(shù))的情況[1,10-11].Barratt等[10]首先利用截斷函數(shù)的相關(guān)公式得到問題(1)的等價模型,然后運用啟發(fā)式方法的思想進行求解.Liu等[11]提出了一種在低維空間下可得到全局最優(yōu)化的通用算法.Ong等[1]首先利用截斷函數(shù)的相關(guān)公式把問題(1)轉(zhuǎn)化為DC問題的形式,然后利用求解DC問題的算法對其進行求解.本文考慮了hi(x)不是常數(shù)的情況,基于這些方法的啟發(fā),運用了啟發(fā)式方法和ADMM方法的思想對問題(1)求解.

本文共分為三節(jié):第一節(jié)為預(yù)備知識.第二節(jié)提出了截斷函數(shù)最優(yōu)化問題的兩種計算方法,第一種方法首先對問題(1)中的模型進行等價替換,基于Barratt等[10]的研究,運用啟發(fā)式方法的思想進行求解;第二種方法是在截斷函數(shù)為非光滑函數(shù)的基礎(chǔ)上,運用光滑逼近的思想使目標(biāo)函數(shù)光滑化,然后運用ADMM方法[12]的思想進行求解.兩種算法在滿足一定的條件下都可以得到全局最優(yōu)解.第三節(jié)應(yīng)用了本文提出的兩種計算方法求解經(jīng)驗風(fēng)險最小化問題(ERM),給出數(shù)值實驗結(jié)果,表明兩種方法都有效.

在本文中,所有向量都是列向量,In表示n×n單位矩陣.

2 計算方法

本節(jié)主要介紹求解截斷函數(shù)最優(yōu)化問題(1)的兩種計算方法:

第一種計算方法首先對問題(1)中的截斷函數(shù)進行轉(zhuǎn)換,得到其等價模型,然后在文獻[10]的方法的啟發(fā)下,運用啟發(fā)式方法的思想進行求解.

第二種計算方法由于截斷函數(shù)是一個不可微函數(shù),因此應(yīng)用光滑逼近的思想使截斷函數(shù)光滑化,把問題(1)轉(zhuǎn)化為光滑的優(yōu)化問題,再運用文獻[13-16]中ADMM算法的思想進行求解.

下面介紹第一種計算方法.首先給出引理2.1,運用該引理給出問題(1)的等價模型.

引理 2.1[8]函數(shù)min{fi(x),hi(x)}滿足

min{fi(x),hi(x)}=

由引理2.1,可推出截斷函數(shù)最優(yōu)化問題(1)等價于下列問題

0≤λi≤1,i=1,2,…,m,

(2)

其中λi∈R(i=1,2,…,m)和x∈Rn是變量.

對于問題(2),當(dāng)fi(x)可微時,可以用非線性規(guī)劃方法求解,也可以用交替最小化求解.但在實際問題中發(fā)現(xiàn),對λi實行非精確交替最小化效果更好.

首先,固定問題(2)中的λi,求解相應(yīng)的最小化問題,將此時x的值記作xk.

然后對目標(biāo)函數(shù)關(guān)于λ計算其梯度

gi=(▽λL(xk,λ))i=fi(xk)-hi(xk).

λ的迭代如下

λk=Π[0,1]m(λk-1-βsign(g)),

其中sign是符號函數(shù),Π[0,1]m代表一種投影函數(shù),其解析式為

(Π[0,1]m(z))

下面給出算法2.1.

算法 2.1步驟 1 初始化:

λ0≥0,β>0,ε>0.

1) 計算xk+1:通過求解下列問題,使其取最小值時x的取值記為xk+1,滿足

gi=fi(xk+1)-hi(xk+1).

λk+1=Π[0,1]m(λk-βsign(g)).

算法2.1是一種下降算法,當(dāng)固定λi時,問題(2)的目標(biāo)函數(shù)值在每次迭代后都會減少,并且因為λi的取值是有限的,所以這個算法可以保證在有限的時間內(nèi)終止.在實踐中,發(fā)現(xiàn)算法2.1在一定的條件下可以達到全局最優(yōu)解,而且在一些更復(fù)雜的情況下能實現(xiàn)得更好.

下面介紹第2種計算方法.

截斷函數(shù)最優(yōu)化問題(1)等價于下列問題

(3)

問題(1)中的截斷函數(shù)滿足等式

min{f1i(x),hi(x)}=

因此問題(1)等價于上述問題(3).由于絕對值函數(shù)是不可微的,所以本文利用絕對值函數(shù)

φ(x)=|x|

的光滑函數(shù)對其進行逼近,應(yīng)用文獻[17-19]的如下光滑函數(shù):對任意p>0,

φ(x;p)=pln(ee

該光滑函數(shù)有如下性質(zhì).

引理 2.2[18]對任意p>0,光滑函數(shù)

φ(x;p):R→R+

滿足:

φ(fi(x)-hi(x);p):=

pln(ee

因此,關(guān)于原問題(1)的光滑無約束優(yōu)化問題定義為

(4)

引理 2.3問題(4)中定義的函數(shù)Φ(x;p)具有以下性質(zhì):

Φ(x;p1)<Φ(x;p2);

證明1)由引理2.2條件2),顯然成立.

Φ(x;p)-Φ(x)=

|fi(x)-hi(x)|]=

plne

(5)

因此

0=ln1<
ln(ee
ln(1+1)=ln2.

(6)

由(5)式和(6)式可得

(7)

綜上所述,引理2.3得證.

由引理2.2和2.3可知問題(4)是問題(3)的光滑逼近.

(8)

考慮增廣拉格朗日乘子法[20],得

(9)

其中

Lβ(x,y,ω)=f0(x)+

下面介紹算法2.2.

算法 2.2步驟 1 初始化:

(y0,ω0)∈Rn×Rm,

p0>0,σ∈(0,1),

β>0,ε1>0,ε2>0.

xk+1:=argxminLβ(x,yk,ωk);

yk+1:=argyminLβ(xk+1,y,ωk);

ωk+1:=ωk+β(xk+1-yk+1);

4) 若

‖xk+1-yk+1‖<ε1

且

‖-β(yk-yk+1‖<ε1,

pt+1=σpt,

算法2.2是對變量進行交替最小化,若問題(7)中的目標(biāo)函數(shù)滿足文獻[9]中的相關(guān)條件可得到全局最優(yōu)解.

3 舉例說明

在本節(jié)中,使用AMDR5 2.1GHz個人電腦,在MatlabR2019b環(huán)境下,應(yīng)用算法2.1和算法2.2分別求解如下經(jīng)驗風(fēng)險最小化(ERM)問題

其中x1,…,xN∈Rn,y1,…,yN∈Y,Y是輸出空間,θ∈R是擬合參數(shù),l:R×Y→R是損失函數(shù),r:Rn→R是正則化函數(shù).

這里把l(xTiθ,yi)≥0.5的點(xi,yi)視為離群點,其余的視為內(nèi)線點.在一些實際問題中ERM問題執(zhí)行得很好,但是當(dāng)數(shù)據(jù)中具有離群點時,它的性能就很會很差,因此本文考慮下列截斷回歸模型

(10)

下面對具有離群點的數(shù)據(jù)進行擬合.

然后隨機選取5個點,將這5個點中的yi轉(zhuǎn)化為-yi，

xi～N(0,1),yi=xi+0.1zi,
zi～N(0,1),i=1,2,…,N.

最后應(yīng)用算法2.1和算法2.2求解截斷回歸模型(10).

(a) N=100時,算法2.1的計算結(jié)果

數(shù)值實驗結(jié)果表明兩種計算方法都有效,并且算法2.1的速度更快.