交替方向乘子法解對稱特征值互補問題

趙 寒，何洪津

(杭州電子科技大學理學院，浙江 杭州 310018)

0 引 言

特征值互補問題(Eigenvalue Complementarity Problem，ECP)是源于工程力學中的一類重要問題[1]。近年來，此類問題已被推廣至張量形式，并稱為張量特征值互補問題[2-3]。在特征值互補問題的內(nèi)嵌矩陣為嚴格協(xié)正矩陣條件下，Júdice等[4]證明了特征值互補問題至少有一個解，且可等價轉(zhuǎn)化為一個變分不等式問題。特別地，若相關矩陣為對稱的，特征值互補問題還可轉(zhuǎn)化為單純形約束的瑞利商極大化問題。從轉(zhuǎn)化后的等價形式上分析，瑞利商極大化問題為一般的約束優(yōu)化模型，可采用譜投影梯度算法(Spectral Projected Gradient, SPG)[5]進行求解。目前，針對特征值互補問題提出的眾多有效算法中，譜投影梯度算法是最受歡迎的方法之一，并被推廣至求解張量特征值互補問題[6-7]。但是，譜投影梯度算法并未充分利用單純形約束的特殊結(jié)構(gòu)，每次需調(diào)用子程序來實現(xiàn)單純形集合的投影。另外，譜投影梯度算法需調(diào)用線搜索尋找合適步長以保證目標函數(shù)值有一定的增長。對于大規(guī)模問題，線搜索無疑會增加計算成本。近年來，針對可分離結(jié)構(gòu)優(yōu)化問題設計的交替方向乘子法(Alternating Direction Method of Multipliers，ADMM)在大規(guī)模圖像處理、機器和統(tǒng)計學習等領域取得了巨大成功[8]。為了提高特征值互補問題的求解效率，本文引入輔助變量，將單純形約束進行分離，使得瑞利商優(yōu)化模型變成可分的優(yōu)化問題。在此基礎上，采用交替方向乘子法對新模型進行求解，使其子問題都具有封閉解，達到有效規(guī)避單純形約束的投影計算和線搜索循環(huán)過程的目的。

1 問題描述

特征值互補問題是指尋找1個實數(shù)μ>0和非零向量x∈Rn，使得

w=(μB-C)x，w≥0，x≥0，xTw=0

(1)

(2)

文獻[10]的命題9指出優(yōu)化模型(5)的穩(wěn)定點即為對稱特征值互補問題的解。此結(jié)論提供了一種求解對稱特征值互補問題的有效途徑。而且，文獻[10]的命題10揭示：若C為嚴格協(xié)正矩陣(即對任意n維向量x≥0且x≠0，都有xTCx>0)時，對稱特征值互補問題至少有1個解。本文假設對稱特征值互補問題的解集非空。

2 交替方向乘子法

不難發(fā)現(xiàn)，瑞利商極大化模型(2)的單純形約束可表示為2個簡單凸集的交集形式，即,Δn={x∈Rn|eTx=1,x≥0}=X∩Y，其中

(3)

因此，通過引入輔助變量x=y，則問題(2)等價為：

(4)

上述問題是一類具有可分結(jié)構(gòu)的簡單約束優(yōu)化模型。因此，本文采用交替方向乘子法對問題(4)進行求解。首先引入增廣拉格朗日函數(shù)：

其中，λ∈Rn為拉格朗日乘子，β>0為等式約束的罰參數(shù)。給定第k步迭代點(yk,λk),交替方向乘子法的迭代格式為：

(5)

迭代格式(5)中的xk+1,yk+1子問題都是約束優(yōu)化問題。但不難發(fā)現(xiàn)，xk+1子問題具有封閉解：

(6)

(7)

綜上，可得求解對稱特征值互補問題的交替方向乘子法，主要步驟如下。

初始化:給定初始迭代點(y0,λ0)∈YY×RRn,選擇β>0和γ>0。(1)若迭代點滿足某個停止準則,算法停止,否則轉(zhuǎn)步驟2;(2)按式(6)更新xk+1;(3)按式(7)更新yk+1;(4)更新λk+1=λk-β(xk+1-yk+1)。

從本文算法不難發(fā)現(xiàn)，每一個子問題都具有封閉迭代形式。相比以往的算法，其迭代格式簡單易實現(xiàn)。對于本文算法的停機準則，采用

來判斷算法是否停止，然后再根據(jù)返回結(jié)果驗證其是否為原問題的解。當然，也可根據(jù)優(yōu)化問題的一階最優(yōu)性條件設計停機準則，如文獻[5]中的停機準則。

由于優(yōu)化模型(4)的目標函數(shù)為2個二次函數(shù)的商，根據(jù)文獻[11]可知μ(y)為半代數(shù)函數(shù)，則μ(y)滿足Kurdyka-Lojasiewicz不等式。又因單純形約束集合為有界閉集，可知交替方向乘子法產(chǎn)生的迭代序列是有界的。因此，由文獻[12]的推論3.1可知，{(xk,yk,λk)}收斂到模型(4)的KKT點，即原對稱特征值互補問題的解點。因證明過程完全類似文獻[12]的證明，本文省略算法的收斂性證明。

3 數(shù)值實驗

本文通過2個算例來驗證本文算法求解對稱特征值互補問題的可行性。算法執(zhí)行過程中，統(tǒng)一設定線性化參數(shù)γ=1。根據(jù)計算經(jīng)驗發(fā)現(xiàn)，交替方向乘子法取固定參數(shù)β時，對不同規(guī)模問題有一定影響。因此本文采用簡單的調(diào)節(jié)準則調(diào)節(jié)算法，即每迭代10步，β值擴大0.2倍。所有試驗運行環(huán)境為Windows 10操作系統(tǒng)下的MATLAB R2016a，配置為Intel Core i7-7700HQ CPU, 8GB內(nèi)存的筆記本電腦。

算例1取B矩陣為單位矩陣，C矩陣為對稱正定矩陣，滿足C=MMT，

由文獻[10]可知，算例1和算例2都至少有1個解，這保證了問題解集的非空性。特別地，根據(jù)文獻[10]可知，算例1有唯一解，且解恰是C矩陣的最大特征值λmax(C)。

表1 2種算法求解算例1的數(shù)值結(jié)果

針對算例1，進一步討論不同初始迭代點對交替方向乘子法的影響。本文選取2組初始迭代點y0=(1,…,1)，λ0=(0,…,0)和隨機的y0=rand(n,1)，λ0=(0,…,0)進行分析，結(jié)果如表2所示。實驗結(jié)果表明，初始迭代點的選擇對本文算法影響較小，即使較大規(guī)模問題，本文算法依然能夠在較短的計算時間內(nèi)成功求解。

表2 不同初始迭代點對改進的交替方向乘子法求解算例1的影響

為了更進一步測試算法的收斂性，針對構(gòu)造的算例2對每一個維度情況進行100次實驗，并觀察100次實驗成功的次數(shù)Sn。表3列出了本文算法與SPG算法在停機精度取ε=10-6，罰參數(shù)β為103時的計算結(jié)果。實驗結(jié)果表明，本文算法能在更短的時間內(nèi)求解對稱的特征值互補問題，其成功率可達100%。

表3 2種算法求解算例2的數(shù)值結(jié)果

4 結(jié)束語

本文針對對稱特征值互補問題提出了一種改進的交替方向乘子法。在計算較大規(guī)模問題時，改進算法用時較少，且初始迭代點的選取表現(xiàn)較穩(wěn)定。但是，部分實際問題不一定滿足本文的對稱性要求，下一步將探討非對稱特征值互補問題的求解。