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

高 峰，宇振盛

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

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

1 問(wèn)題的提出

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

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

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

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

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

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

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

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

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

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

對(duì)于問(wèn)題（1），為方便表示，令

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

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

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

式中，u∈Rm。

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

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

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

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

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

為方便表示，引入符號(hào)

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

定義一個(gè)廣義同倫映射為[13]

同倫方法是通過(guò)選擇合適的矩陣H和向量a，再將 αk的值由0 迭代1，得到T(ω,αk)=0的一系列解的過(guò)程，特別是，最終αk→1時(shí)即可求得F(ω)=0的近似解。總的來(lái)說(shuō)，同倫方法的目的是將求解一個(gè)給定的較難問(wèn)題轉(zhuǎn)化為求解簡(jiǎn)單問(wèn)題。原問(wèn)題F(ω)=0求解起來(lái)較為困難，但求解問(wèn)題(Hωa)=0則相對(duì)容易。

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

算法1

2.2 內(nèi)迭代

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

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

考慮Gauss-Seidel 迭代法

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

并且，式（14）可重寫為

為簡(jiǎn)單起見(jiàn)，在收斂分析中引入矩陣

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

取A，x0和b的值為

并計(jì)算出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時(shí)間和精度。表2 中，字母F 代表計(jì)算失敗，即迭代次數(shù)超過(guò)300 次。下標(biāo)i(i=1,2,3)分別代表HADMM，SDPT3 和Sedumi 這3 個(gè)算法。

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

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

4 結(jié)論

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