一種求解3塊變量線性約束凸優化問題的新鄰近部分平行分裂算法

王鈺淇， 申 遠

(南京財經大學 應用數學學院， 江蘇 南京 210023)

0 引言

討論如下可分離為3塊變量的線性約束凸優化問題：

(1)

其中θi:Rni→(-∞,+∞)為凸函數(不一定光滑)；Ai∈Rl×ni為滿秩矩陣；b∈Rl為列向量；Xi?Rni為非空閉凸集；n1+n2+n3=n.

求解可分離為2塊變量的線性約束凸優化問題一般使用交替方向乘子法(ADMM)，相較于求解該類問題的經典算法——增廣Lagrange乘子法，ADMM更加高效.該算法利用了問題的可分離結構，將迭代步驟分解為多個規模較小的子問題分別求解，并在所有子問題求解之后更新對偶變量(乘子).當問題只可分離為2塊變量時，ADMM可以保證收斂性.

當求解3塊及以上變量問題時，我們稱ADMM為直接擴展的交替方向乘子法(EADMM).在求解實際問題時EADMM有較高的計算效率，例如線性相關圖像對齊[1]；給定矩陣的低秩和稀疏分量恢復[2];基追蹤、穩健主成分分析和潛變量高斯圖形模型選擇[3]等.在大多數數值試驗中EADMM表現出收斂性，并且數值表現較好.但已知EADMM在理論上無法保證收斂[4].目前主要有兩類方法可使算法收斂，一類是在不改變算法的前提下增加其他假設條件，包括但不限于：設目標函數中含有一個強凸的函數，并適當限制懲罰參數[5]；設目標函數為若干個沒有耦合變量的凸函數之和，并且所涉及的函數具有強凸性[6].另一類是針對EADMM算法本身進行改造，包括但不限于：基于ADMM，在優化問題的目標函數上加一個特殊的鄰近項[7]；對于目標函數為二次函數的特殊多塊優化模型，提出一種基于舍爾補的鄰近ADMM[8]；對迭代后的變量使用高斯回代法進行校正[9]；……