左鑫怡, 蔣 毅*, 楊 嵐
(1. 四川師范大學 數學科學學院, 四川 成都 610066; 2. 四川師范大學 可視化計算與虛擬現實四川省重點實驗室, 四川 成都 610066)
本文考慮一類截斷函數的最優化問題
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單位矩陣.
本節主要介紹求解截斷函數最優化問題(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]中的相關條件可得到全局最優解.
在本節中,使用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的速度更快.