一類截斷函數最優化問題的求解方法

左鑫怡, 蔣 毅*, 楊 嵐

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

1 預備知識

本文考慮一類截斷函數的最優化問題

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

(1)

其中x∈Rn是變量,

f0:Rn→R∪{+∞},

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

min

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

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

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

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

2 計算方法

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

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

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

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

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

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

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

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

(2)

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

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

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

然后對目標函數關于λ計算其梯度

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

λ的迭代如下

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

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

(Π[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是一種下降算法,當固定λi時,問題(2)的目標函數值在每次迭代后都會減少,并且因為λi的取值是有限的,所以這個算法可以保證在有限的時間內終止.在實踐中,發現算法2.1在一定的條件下可以達到全局最優解,而且在一些更復雜的情況下能實現得更好.

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

截斷函數最優化問題(1)等價于下列問題

(3)

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

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

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

φ(x)=|x|

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

φ(x;p)=pln(ee

該光滑函數有如下性質.

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

φ(x;p):R→R+

滿足:

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

pln(ee

因此,關于原問題(1)的光滑無約束優化問題定義為

(4)

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

Φ(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)中的目標函數滿足文獻[9]中的相關條件可得到全局最優解.

3 舉例說明

在本節中,使用AMDR5 2.1GHz個人電腦,在MatlabR2019b環境下,應用算法2.1和算法2.2分別求解如下經驗風險最小化(ERM)問題

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

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

(10)

下面對具有離群點的數據進行擬合.

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

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

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

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

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