求解絕對值方程稀疏解的增廣拉格朗日方法

孫敏,田茂英

(1.棗莊學院 數(shù)學與統(tǒng)計學院,山東 棗莊 277160;2.山東煤炭衛(wèi)生學校,山東 棗莊 277160)

考慮如下絕對值方程的稀疏解問題:

(1)

其中x∈Rn,A∈Rn×n,b∈Rn,‖x‖0表示x的l0-范數(shù),|x|表示對x的每個分量取絕對值.

如果將問題(1)的目標函數(shù)去掉,則問題(1)退化成經(jīng)典的絕對值方程問題,因此問題(1)的研究范圍比絕對值方程更廣泛:如果絕對值方程有唯一解,則該唯一解也是問題(1)的最優(yōu)解;如果絕對值方程有多重解,則問題(1)可以求出其中最稀疏的解,即零元素最少的解.

近年來,絕對值方程逐漸成為優(yōu)化領(lǐng)域的一個研究熱點.目前相關(guān)研究內(nèi)容主要是其解存在的充分條件與具體的求解算法.在解的存在性條件方面的成果包括:Mangasarian給出了多種絕對值方程無解、唯一解或多重解的條件[13];雍龍泉給出了一個絕對值方程存在唯一解的條件[4].在求解算法方面的成果可以分為連續(xù)算法與離散算法,其中連續(xù)算法包括各類神經(jīng)網(wǎng)絡(luò)方法[5,6];離散算法包括各種迭代算法,比如不動點迭代法[4]、牛頓類迭代法[3],SOR類迭代法[7,8]等.最近幾年,關(guān)于絕對值方程的一些研究成果已經(jīng)被推廣到張量形式的絕對值方程[9,10].

目前國內(nèi)外對絕對值方程稀疏解問題的研究還比較少,主要研究成果包括:廖蕓等[11]最早給出了求解絕對值方程稀疏解的兩類方法,其中一類是將該問題轉(zhuǎn)換成松弛為l1-范數(shù)優(yōu)化問題,然后再繼續(xù)轉(zhuǎn)化為線性規(guī)劃問題,另一類是利用一個凹函數(shù)來逼近l0-范數(shù),并對該凹函數(shù)進行線性化,再通過求解一系列線性規(guī)劃問題來求解問題(1).王鵬等[12]借助prox算子,提出了求解問題(1)的松弛形式的不動點算法.基于不動點方程,張曉敏[13]設(shè)計了一類神經(jīng)網(wǎng)絡(luò)算法來求解問題(1)的松弛形式.

本文繼續(xù)研究問題(1)的數(shù)值算法.借鑒壓縮感知模型的轉(zhuǎn)換思想,首先將問題(1)的目標函數(shù)松弛為決策變量的l1-范數(shù).再結(jié)合增廣拉格朗日方法,將松弛問題轉(zhuǎn)化成4塊可分離的凸規(guī)劃問題,進而設(shè)計了一類預估-校正格式的增廣拉格朗日方法.與類似方法相比,本文設(shè)計的方法充分利用了迭代的最新信息,對決策變量采用交替、并行混合更新策略,同時校正步的步長取值范圍更大.

1 凸優(yōu)化模型

與壓縮感知模型相比,問題(1)的約束中多了一項|x|,這也是其名稱中“絕對值”的來歷.受壓縮感知模型的啟發(fā),將問題(1)松弛為如下形式

(2)

其中‖x‖1表示x的l1-范數(shù),即元素絕對值的和.令y=|x|,得問題(2)的等價形式

(3)

對問題(3)的約束進行松弛,得線性規(guī)劃問題

(4)

雖然問題(4)是問題(3)的松弛形式,但是由于目標函數(shù)的作用,問題(2)(3)與(4)是等價的.

繼續(xù)將問題(4)的不等式約束改寫成等式約束.為此,引入松弛變量u,v∈Rn,得

(5)

其中e=[1,1,…,1]T∈Rn.顯然問題(5)屬于如下4塊可分離凸規(guī)劃問題

(6)

顯然矩陣Ai(i=1,2,3,4)都是列滿秩的.

2 增廣拉格朗日方法

本節(jié)設(shè)計一類求解4塊可分離凸規(guī)劃(6)的增廣拉格朗日方法,并分析其全局收斂性.問題(6)的增廣拉格朗日函數(shù)是

其中β>0是罰參數(shù),λ∈R3n是拉格朗日乘子.

θ(w)-θ(w*)+(w-w*)TF(w)≥0,?w∈W,

(7)

(w-w')T(F(w)-F(w'))=0,?w,w'∈R7n.

(8)

基于前面的分析,下面給出求解問題(6)的增廣拉格朗日方法.

算法:增廣拉格朗日方法

(9a)

(9b)

(9c)

(9d)

(9e)

步3(收斂性檢驗)如果

步4(校正步)按下面的格式得到新的迭代點wk+1:

(10)

令k=k+1,返回第2步.

證明 對于任意的w∈W,由(9a)-(9d)的一階最優(yōu)性條件得

結(jié)合(9e),上面的4個不等式可以改寫成

(11)

其中

如果引理的條件成立,則由(11)得

基于引理1、(8)與(11),類似于[14]引理3、引理4與定理1的證明,下面的結(jié)論成立.

引理2對于問題(7)的任意解w*,算法生成的點列滿足

其中

引理3對于問題(7)的任意解w*,算法生成的點列滿足

其中

本節(jié)最后給出算法求解問題(6)的具體迭代格式.關(guān)鍵是(9)的前4個最優(yōu)化子問題的求解.結(jié)合問題(6)的特殊結(jié)構(gòu),利用(9)可得

其它步驟都是顯式迭代,不再列出.

3 數(shù)值實驗

本節(jié)給出一個利用算法求絕對值方程稀疏解的實驗.所有實驗都是利用MATLABR2014a編程實現(xiàn)的.

考慮問題(2),其中

這個問題有兩個可行解

顯然x1是問題(2)的最優(yōu)解.初始狀態(tài)的分量都取為1,β=1.仿真結(jié)果繪制在圖1中,其中橫坐標為迭代次數(shù),縱坐標是算法產(chǎn)生的點列與最優(yōu)解之間的距離.

圖1 算法的仿真結(jié)果

由圖1可以看出,算法成功求解了該問題.一開始收斂速度比較快,到迭代次數(shù)超過1600之后,算法趨于平穩(wěn),最后穩(wěn)定在大約10-5.

4 小 結(jié)

本文設(shè)計了一個求解絕對值方程稀疏解的增廣拉格朗日方法.該方法采用預估-校正格式,在預估步,采用增廣拉格朗日方法迭代格式,在校正步采用常步長,其中常步長的取值范圍大于其它類似的方法.數(shù)值實驗表明該方法可以求解絕對值方程的稀疏解,但是求解速度不快,下一步將研究加速增廣拉格朗日方法.