呂佩雯

（華南理工大學(xué)，廣東 廣州 510640）

一、引言

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

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

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

二、零模正則化

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

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

三、零模正則化問(wèn)題的等價(jià)模型

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

因此，問(wèn)題的等價(jià)問(wèn)題為：

問(wèn)題的可行集中包含著如下互補(bǔ)約束條件：

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

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

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

所以，只需證明：

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

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

所以，

再加上ρ＞VLf，可得：

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

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

所以，

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

(S2)求解極小化問(wèn)題：

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

四、結(jié)束語(yǔ)

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