求解一類二次規(guī)劃反問題的同倫交替方向法

高 峰，宇振盛

（上海理工大學(xué) 理學(xué)院，上海 200093）

反問題研究在投資組合優(yōu)化和生成樹逆問題中具有廣泛而極高的應(yīng)用價值，特別是在網(wǎng)絡(luò)流逆問題中，為解決信息資源配置問題提供了理論依據(jù)和支持。針對反問題，已有大量學(xué)者在理論上和算法上進(jìn)行了深入的研究，并取得了豐碩的成果。早在1996 年，Zhang等[1-2]就已著手研究線性規(guī)劃反問題，Iyengar等[3]則在2005 年討論了錐規(guī)劃反問題。2018 年，Khan等[4]研究了擬變分不等式中參數(shù)辨識的反問題，并提出了一種抽象的非光滑正則化方法。具體到二次規(guī)劃反問題上，Zhang等[5]于2010 年發(fā)現(xiàn)此類問題的對偶問題是一個SC1凸問題(即目標(biāo)函數(shù)連續(xù)可微并且梯度半光滑)，并且提出使用增廣拉格朗日法求解此類問題。針對相同問題，Xiao等[6]于2009 年提出了一種光滑牛頓法進(jìn)行求解。Lu等[7]在2019 年提出了非凸交替乘子方向法求解一類稀疏的半定逆二次規(guī)劃問題。李麗丹等[8]在2021 年提出了G-ADMM 法對一類二次規(guī)劃逆問題進(jìn)行求解，目標(biāo)函數(shù)是矩陣譜范數(shù)與向量無窮范數(shù)之和的最小化問題。上述的一些算法雖然全局收斂，但在實際迭代過程中，保證算法線性收斂的前提條件太強(qiáng)而難以滿足。除此之外，反問題的目標(biāo)函數(shù)中會出現(xiàn)矩陣范數(shù)與向量范數(shù)之和，這導(dǎo)致其對偶形式不易求出，因此，就有必要考慮直接對原問題進(jìn)行求解。為更好解決這類問題，本文使用交替方向乘子法(ADMM)，該方法是解決變量可分離問題的有效方法之一。交替方向乘子法最早由Gabay等[9]在1976 年提出，并且Boyd等[10]在2011年驗證了此方法可用來求解大規(guī)模的分布式優(yōu)化問題。同年，文獻(xiàn)[11]基于傳統(tǒng)交替方向法，在生成迭代步驟的過程中添加了近似二次項，這種方法被稱為近端交替方向法(PADM)，但這種近端交替方向法在近端參數(shù)的選擇上較為敏感。本文提出了一種基于同倫法的ADMM 方法，這種方法將同倫思想融入迭代的每一子問題中，既可克服近端參數(shù)選取的敏感性這一缺點，又可加快ADMM收斂速度。

1 問題的提出

考慮凸二次規(guī)劃問題QP(G,c,A,b) ：

式中：G∈和c∈Rn分別為矩陣和向量；為對稱半定矩陣集合；且A∈Rm×n和b∈Rm的值已給定。

傳統(tǒng)的正向優(yōu)化過程是從所有可行解中找到一個最優(yōu)解x，前提是其中參數(shù)G∈，c∈Rn的值會精確給定。但是，反過來講，有這樣一類優(yōu)化問題，只知道參數(shù)G和c的估計值，從經(jīng)驗、觀察或者實驗中可以知道此問題的可行解，這種情況下，需要找到使給定解成為最優(yōu)解時的參數(shù)G和c的值，并且求得的參數(shù)值應(yīng)該盡可能靠近之前各自的估計值。該類問題稱為優(yōu)化反問題。

反問題在股票市場應(yīng)用居多，常見的投資組合優(yōu)化問題可以描述如下：

式中：λ′＞0是控制收益和風(fēng)險的權(quán)重參數(shù)；Ax≤b代表投資組合的約束條件。

一般來說，在一個股票市場里，投資者需要根據(jù)目標(biāo)預(yù)期收益來決定每只股票的權(quán)重，這就是最優(yōu)投資組合問題。

而在現(xiàn)實問題中，每只股票的預(yù)期收益以及不同股票之間的協(xié)方差會隨市場的變化而變化。這里用(G0,c0)代表(G,c)的最新估計值，用x0代表問題（2）在(G,c)=(G0,c0)時的最優(yōu)解。在這種股市變動情況下，投資者先前的投資組合x0不再是新股票市場的最優(yōu)組合，因為，此時新市場的期望收益變?yōu)閏0，協(xié)方差變?yōu)镚0，投資者如果繼續(xù)使用此投資組合將會蒙受經(jīng)濟(jì)損失。因此，為了維持經(jīng)濟(jì)效益，并且在不改變投資組合的前提下實現(xiàn)原本投資組合x0的價值，需要找出更適用此種投資組合的投資者，而這樣的投資者所持股票的期望收益率c和 股票之間協(xié)方差G應(yīng)當(dāng)盡可能接近第一個投資者股票的期望收益率和協(xié)方差的估計值，除此之外，要使得現(xiàn)存投資組合x0為新投資者所持股票組合最優(yōu)解。因此，找到合適的G和c值極具實際意義。

問題（2）可寫成如下的優(yōu)化反問題：

式中：‖·‖代表矩陣和向量的范數(shù)；ψ(x0)表示x0為問題（2）的最優(yōu)解時所有(G,c)的集合。

因此，如果(G,c)∈ψ(x0)，即f(G0,c0)=0，那么，此時x0也是問題（3）在參數(shù)(G,c)=(G0,c0)時的最優(yōu)解，這意味著投資者可以繼續(xù)使用投資組合x0。否則，如果f(G0,c0)＞0，要保證交易成本和回報之間的平衡就要保證估計值(G0,c0)和集合ψ(x0)之間的偏差盡可能小。總之，研究二次規(guī)劃反問題具有極大的現(xiàn)實意義。

對于問題（1），為方便表示，令

從觀測和實驗中可以得到參數(shù)G和c估 計值G0∈和c0∈Rn，給定一個可行點x0使之滿足約束條件Ax0≥b。本文用S(Q)表示Q的最優(yōu)解，所以，本文研究二次規(guī)劃反問題的目的即為求出(G,c)∈×Rn的值，使之滿足x0∈S(QP(G,c,A,b))，且(G,c)要盡可能接近(G0,c0)。因此，相應(yīng)的二次規(guī)劃反問題IQP(G,c)可寫為

式中，‖·‖2表示矩陣的譜范數(shù)和向量的歐幾里得范數(shù)，即‖G‖2=max

眾所所知，問題QP(G,c)是嚴(yán)格凸二次規(guī)劃問題，因此，式（4）中的約束，寫成KKT條件為[12]

式中，u∈Rm。

不失一般性，假設(shè)前p個約束在x0處是有效約束，即x0的積極約束集等價于

令A(yù)0:=(a1,a2,···,ap)T,ai∈Rn(i=1,2,···,p)，即A0表示矩陣A的前p行。同時引入向量y，其由向量u的前p個元素構(gòu)成，所以，x0∈S(QP(G,c))可以等同于

其拉格朗日函數(shù)為

交替方向法是求解目標(biāo)函數(shù)可分離優(yōu)化問題的重要工具。本文為求解一類二次規(guī)劃反問題，提出了一種基于同倫法的交替方向乘子法，該方法將同倫思想與經(jīng)典的ADMM 方法相結(jié)合。同倫方法最早于1930 年被提出，是解決非線性問題的有力工具，在凸優(yōu)化和非凸優(yōu)化方面都做出了巨大貢獻(xiàn)。2017 年，Yang等[13]提出了一種基于同倫的交替方向乘子方法來求解線性約束可分離凸極小化問題。本文將同倫方法應(yīng)用到迭代的每一個子問題上，以此避免敏感近端參數(shù)的選取，同時加快了傳統(tǒng)ADMM 的速度。

2 同倫ADMM 算法

現(xiàn)介紹外迭代使用的近端ADMM 算法以及內(nèi)迭代使用的逐次超松弛法。

2.1 外迭代

已知(Gk,ck,yk,λk) 的前提下，由ADMM 產(chǎn)生(Gk+1,ck+1,yk+1,λk+1)的迭代結(jié)構(gòu)如下：

（S1）已知(ck,yk,λk)，則有

（S2）已知Gk+1，yk和 λk，則有

（S3）已知Gk+1，ck+1和 λk，則有

（S4）拉格朗日乘子 λ的更新為

上述步驟等同于

其中，rk，sk和tk為近端算子。因此，上述迭代過程可重新描述為

實際上，迭代式(7)等同于求解下述方程：

為方便表示，引入符號

綜上可知，求解ω*∈W*本質(zhì)上就是求解非線性方程組F(ω)=0。

定義一個廣義同倫映射為[13]

同倫方法是通過選擇合適的矩陣H和向量a，再將 αk的值由0 迭代1，得到T(ω,αk)=0的一系列解的過程，特別是，最終αk→1時即可求得F(ω)=0的近似解?？偟膩碚f，同倫方法的目的是將求解一個給定的較難問題轉(zhuǎn)化為求解簡單問題。原問題F(ω)=0求解起來較為困難，但求解問題(Hωa)=0則相對容易。

現(xiàn)將基于同倫的近端ADMM（HADMM）應(yīng)用于問題(6)，下面介紹算法。

算法1

2.2 內(nèi)迭代

現(xiàn)引入逐次超松弛法對上述外迭代過程中的子問題進(jìn)行內(nèi)迭代求解。

逐次超松弛法是Gauss-Seidel 法的一種演變方法。它最初是Frankel 在1950 年為了在計算機(jī)上求解線性方程而提出的。逐次超松弛迭代法在高斯-賽德爾迭代基礎(chǔ)上加入松弛因子以加快迭代收斂速度。

考慮Gauss-Seidel 迭代法

將式（14）中λk+1的更新公式分別與式（15）和式（16）合并，可得

并且，式（14）可重寫為

為簡單起見，在收斂分析中引入矩陣

其中，Qk=PkMk。令U:=Rn×Rp×Rn，u=(c,y,λ)∈U，已知uk，用uk+1表示由本文算法生成的下一步迭代點。如此便有

定理1由算法1 生成的序列是收斂的，并且序列極限滿足一階最優(yōu)性條件式（9）。

定理1 的證明可參考文獻(xiàn)[13]，其中也證明了最壞情況下的收斂速度為O(1/k)。

3 數(shù)值實驗

現(xiàn)對本文提出的算法進(jìn)行數(shù)值實驗，并與國際知名的優(yōu)化軟件CVX 的子程序SDPT3 和Sedumi求解式（5）的數(shù)值結(jié)果進(jìn)行比較。

實驗中設(shè)置同倫因子初始值，μ及β為

取A，x0和b的值為

并計算出p和A0的值。

參數(shù)(G,c,G0,c0)設(shè)置為

算法的數(shù)值結(jié)果如表1 和表2 所示。

表1 HADMM 數(shù)值結(jié)果Tab.1 Numerical results of HADMM

表1 中，m，n分別表示矩陣或向量的行和列。此處將終止條件設(shè)置為ε=10-4。e，t和r分別代表迭代次數(shù)，CPU時間和精度。表2 中，字母F 代表計算失敗，即迭代次數(shù)超過300 次。下標(biāo)i(i=1,2,3)分別代表HADMM，SDPT3 和Sedumi 這3 個算法。

從表1 和表2 中可以看出，在解決相同維度的問題時，本文的算法無論是在精度還是CPU 時間上，都要優(yōu)于SDPT3 和Sedumi。除此之外，本文算法能夠高效、快速地求解更高維的二次規(guī)劃反問題。

表2 數(shù)值比較Tab.2 Numerical Comparison

4 結(jié)論

采用一種基于同倫的ADMM 方法求解一類二次規(guī)劃反問題。將該問題轉(zhuǎn)化為目標(biāo)函數(shù)可分離的線性約束問題后，將同倫思想應(yīng)用于每一次迭代的子問題中，不僅可以實現(xiàn)對傳統(tǒng)ADMM 方法的加速，而且避免了選取近端參數(shù)時的敏感性。最后給出了算法的數(shù)值實驗結(jié)果。與SDPT3 和Sedumi 的數(shù)值結(jié)果相比，本文的算法無論是在CPU時間還是殘差方面都要優(yōu)于以上兩種方法。最重要的是本文的算法能夠更高效求解更高維的問題。