呂佩雯

（華南理工大學，廣東 廣州 510640）

一、引言

設Rn是賦予了內(nèi)積及誘導范數(shù)的有限維向量空間，考慮稀疏邏輯回歸問題：令為樣本，為類別標簽，則邏輯回歸模型為：

其中Prob(y=1/β)是在給定樣本觀測值β后，類別標簽為l的條件概率，x為特征向量。

這是一個光滑的凸函數(shù)[1,3]，可以通過最小化邏輯損失的均值來求解特征向量x。

二、零模正則化

當訓練集里的樣本數(shù)m小于維數(shù)n時，直接求解容易出現(xiàn)過擬合，一般使用正則化來避免過擬合問題的出現(xiàn)。本文將使用零模正則，即求解零模正則極小化問題：

零模優(yōu)化問題是一類帶有組合性質的向量優(yōu)化問題，（1）這種問題在計算上通常是NP難的，難以求得其全局最優(yōu)解。而且，源于實際應用的零模優(yōu)化問題通常具有較高的維數(shù)，根本不適合采用全局優(yōu)化方法去尋求全局最優(yōu)解。一個常用的處理方法是使用凸松弛技術,這種方法通過解一個或一系列易于處理的凸優(yōu)化問題來產(chǎn)生一個理想的可行解或局部最優(yōu)解。

三、零模正則化問題的等價模型

首先，從零模函數(shù)的變分刻畫入手，可以得到零模正則問題的等價全局Lipschitz連續(xù)優(yōu)化模型。對任意的，容易得到：

因此，問題的等價問題為：

問題的可行集中包含著如下互補約束條件：

這說明零模正則化問題也是一個帶有互補約束的數(shù)學規(guī)劃問題(MPEC)。需要注意的是，MPEC在優(yōu)化中也是一類很難的問題。雖然問題（2）的目標函數(shù)比原問題（1）簡單，但卻含有非凸互補約束，這比非凸目標函數(shù)更難處理。為解決這個非凸約束，考慮問題（2）的罰問題：

其中ρ＞0是罰參數(shù)。下面的定理1將說明問題（3）是問題（2）的全局精確罰，即他們有相同的全局最優(yōu)解集[5]。在此之前，先建立定理證明需要用到的引理。

引理2.設函數(shù)f在集合上全局Lipschitz連續(xù)，若ρ＞VLf，則對任意的和，有：

所以，只需證明：

由引理1，若wρ是下面問題的最優(yōu)解則wρ的形式可以為對t=1,2,...n.所以，

第一部分得證。下面證明第二部分：當?shù)仁匠闪r，

所以，

再加上ρ＞VLf，可得：

下面給出問題（3）是問題（2）的全局精確罰的理論保證：

證明.設問題（2）和問題（3）的可行集分別為 S 和 Sρ，問題（2）和問題（3）的全局最優(yōu)解集分別為S*和S*ρ。令ρ＞vLf,首先證明：對任意的，有，且由引理2，

所以，

這樣，求解問題（1）轉化為求解罰問題（3）。雖然罰問題（3）非凸，但是這種結構使得它比零模正則化問題更好解決。當變量w選定時，f(x)為邏輯損失函數(shù)，罰問題（3）退化為關于x的凸的極小化問題；當變量x選定時，罰問題（3）退化為關于w的凸的極小化問題，這樣的問題是有閉式解的。為此，針對f(x)為邏輯損失函數(shù)，將選用多階段凸松弛法[4]來求解問題（3）。多階段凸松弛法的主要步驟為：

(S2)求解極小化問題：

由引理1可知Wk是容易求得的，該方法的主要工作都在于解決一個加權的L1-正則化邏輯回歸問題[6,9,10]。這是一類凸優(yōu)化問題，所以它可以通過標準的凸優(yōu)化方法求解，比如:增廣拉格朗日法，內(nèi)點法[7]，IRLS-LARS[8],路徑跟蹤法，迭代加權最小二乘法等。

四、結束語

本文借助零模函數(shù)的變分刻畫，將零模正則化邏輯回歸問題等價的寫為帶有互補約束的數(shù)學規(guī)劃問題(簡稱MPEC問題)；然后證明將互補約束直接罰到目標函數(shù)上所誘導的罰問題是MPEC問題的全局精確罰(即與MPEC問題有相同的全局最優(yōu)解集)。正如文中所說，此精確罰問題的目標函數(shù)不僅在可行集上全局Lipschitz連續(xù)，而且還具有滿意的雙線性結構，為設計零模正則化問題的多階段凸松弛算法提供了滿意的等價Lipschitz優(yōu)化模型。