增廣Lagrange方法求解二階錐約束變分不等式問題

劉雨，孫菊賀，王莉，米娜，袁艷紅

（1. 沈陽航空航天大學(xué) 理學(xué)院，沈陽 110136；2. 太原理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，太原 030002）

考慮二階錐約束變分不等式問題［1］：找到x*∈K，滿足不等式

其中

mi≥1，m1+m2+…+mp=m，并且其中κmi，i=1，2，…，p是一個mi維的二階錐。

變分不等式問題被廣泛應(yīng)用于優(yōu)化問題、工程技術(shù)、力學(xué)、計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、運(yùn)輸業(yè)等諸多領(lǐng)域，引發(fā)了許多學(xué)者的特別關(guān)注。關(guān)于變分不等式問題的理論、應(yīng)用和數(shù)值方法的研究一直在持續(xù)的進(jìn)行。在主動配電網(wǎng)無功優(yōu)化模型中， Yang等［2］采用了二階錐松弛方法和區(qū)間優(yōu)化理論進(jìn)行求解，不僅可以極大地提高效率，而且還能使結(jié)果具有一定的穩(wěn)定性。對于一定擾動下的約束軌跡問題的優(yōu)化，Sun等［3］將原問題看作二階錐的優(yōu)化問題，通過使用連續(xù)的迭代算法來驗(yàn)證所提供的軌跡是否可行，同時也可以驗(yàn)證是否是最優(yōu)軌跡。Jin等［4］提出了一種基于分解迭代二階錐規(guī)劃的零展寬魯棒波束的形成方法，解決了非平穩(wěn)狀態(tài)下自適應(yīng)波束形成性能下降的問題，同時也提高了復(fù)雜環(huán)境中自適應(yīng)波束形成的魯棒性。文獻(xiàn)［5］在解決下層問題時，也利用了凸二階錐規(guī)劃問題對魯棒約束進(jìn)行了轉(zhuǎn)化。Wu等［6］應(yīng)用光滑算法來求解變分不等式的問題，并且證明了該算法的穩(wěn)定性。石翔宇［7］研究一類二階偏微分方程及位移障礙變分不等式問題的有限元方法，使用了插值與投影定理相結(jié)合的處理方法，降低了解的正則性的要求，探討出了在不同條件下解的收斂性與超收斂性。Singh等［8］構(gòu)造了求解多時間型變分不等式問題的迭代算法，并證明了其收斂性。Nnakwe等［9］研究了一種慣性效應(yīng)的投影算法，使算法的序列無限逼近變分不等式問題和不動點(diǎn)問題的公共解，以此來解決一些非線性優(yōu)化問題。

基于此，本文利用增廣Lagrange方法［10］來求解一類二階錐約束變分不等式問題。通過投影定理及變分不等式和優(yōu)化問題的內(nèi)在聯(lián)系得到了二階錐約束變分不等式問題不同等價變換形式。利用增廣Lagrange函數(shù)構(gòu)造了一類數(shù)值算法，并證明了數(shù)值算法的全局收斂性。最后將非精確牛頓法作為子算法求解了三個數(shù)值算例，驗(yàn)證了其可行性。同樣增廣Lagrange方法也有諸多應(yīng)用，Han等［11］通過增廣Lagrange法高效求解混合整數(shù)線性規(guī)劃（MILP）公式。Feng等［12］提出了一種在不計(jì)算奇異值的情況下，基于增廣Lagrange乘子的奇異譜分析去噪方法。同樣Wang等［13］建立了增廣Lagrange乘子的存在性，文獻(xiàn)［14］也給出了更加一般結(jié)果。

定義1假設(shè)Rm空間有一向量s，記作s=，其中=(s1，s2，…，sm-1)∈Rm-1。那么二階錐κm?Rm有如下定義：

對于任意的兩個變量x=(x0；)∈R×Rm-1，∈R×Rm-1，則x和y的Jordan積［15］定義如下

對于?x=(x0；)∈R×Rm-1具有以下的譜分解

式中：λ1和λ2是x的譜值，并且

式中：ω∈Rm-1，‖ω‖=1。用記作向量x在κm上的投影，則

其中[λi]+=max{0，λi}，i=1，2。顯然

1 問題轉(zhuǎn)化

對于問題（1）可以將其轉(zhuǎn)化為如下的二階錐優(yōu)化問題［17］：

式中：f(y)=，并且f(y)≥0。則問題（7）得Lagrange函數(shù)為：

式中：y是原始變量；λ是對偶變量。由于x*是f(y)的最小值，因此在正則的條件下，(y，λ)是L(x*，y，λ)的一個鞍點(diǎn)，即?y∈Ω，λ∈κ，有

式（9）通過不等式做差，有如下的等價表達(dá)式

由于Ax-b顯然是可微的，那么系統(tǒng)（10）就意味著(x*，λ*)解決了如下變分不等式問題［18］，

?y∈Ω，λ∈κ。根據(jù)投影算子的性質(zhì)，上述變分不等式系統(tǒng)（11）等價于下列方程組問題

由于Ax-b是凸的，對于?y∈Ω，可以得到（12）的等價形式

容易驗(yàn)證，式（9）～（13），在投影算子性質(zhì)的作用下是相互等價的。

2 增廣Lagrange法

設(shè)x1∈Ω是初始解，λ1∈κ是對應(yīng)的La‐grange乘子，假設(shè)已知第k次迭代xk∈Ω和λk∈κ，那么第k+1步迭代有如下表達(dá)式

式中：α＞0，并且

是式（7）的一個增廣Lagrange函數(shù)［17］。

需要注意的是xk+1同時出現(xiàn)在（14）式的左右兩邊，那么這就意味著式（14）是一個隱式方程。因此，求解隱式方程式是解決問題的關(guān)鍵。

根據(jù)投影算子的性質(zhì)，式（14）可以等價為如下的變分不等式問題：

下面，將證明增廣Lagrange算法（14）的全局收斂性定理［19］。

定理1假設(shè)問題（1）的解集Ω*是非空的，并且F是一個單調(diào)映射。令Ω?Rn是一個閉凸集，且α＞0。那么由增廣Lagrange方法產(chǎn)生的序列xk依范數(shù)收斂于二階錐約束變分不等式問題（1）的解。

證明：令式（16）中y=x*，再將新式子帶入至式（17）中，可以得到

由此

根據(jù)式（19）中等式約束Ax-b是凸的，式（19）中最后一項(xiàng)可以等價為

因此結(jié)合式（19）～（20）有

令y=xk+1帶入到式（13）的第一個不等式中，有

通過對式（21）與（22）的求和，可得

令λ=λ*帶入到（17）式中，通過和=0，可得

由于F(x)是一個單調(diào)算子，通過式（23）與（24）可以推導(dǎo)出

對于任意變量x1，x2和x3，他們之間存在如下關(guān)系式

并且有

通過（27）式，將（25）式變形為

對式（15），從k=0到k=N進(jìn)行累加求和

從不等式（29）可知，點(diǎn)對集{(xi，λi)：i=1，2，…，}的軌跡是有界的，如式（30）所示

并且它的級數(shù)也是收斂的，

因此當(dāng)k→∞，由于序列(xk，λk)是有界的，因此存在一個元素(x'，λ')，當(dāng)i→∞時，使得xki→x'和λki→λ'，同時

令（16）和（17）中k=ki，通過取極限i→∞可以得出

綜合上述，式（33）與式（10）所表示關(guān)系是一致的。當(dāng)x'∈Ω，λ'∈κ，有

因此序列(xk，λk)的任何極限點(diǎn)都是二階錐約束變分不等式問題（1）的解，由此可以看出序列是單調(diào)遞減的，因此其極限點(diǎn)是唯一的。即，當(dāng)k→∞時，xk→和，因此和=λ'：=λ*。

3 數(shù)值模擬

由于增廣Lagrange方法中的方程式是隱式的，當(dāng)Ω=Rn的情況下，增廣Lagrange方法（14）可化簡為

式中：

非精確牛頓法

步驟1：令ξ0=xk，選取非負(fù)參數(shù)列{ηj}，并且j=0；

步驟2：若Gk(ξj)=0，停止；令xk+1=ξj；

步驟3：選取Hj∈?Gk(ξj)，計(jì)算搜索方向dj∈Rn，滿足

步驟4：令ξj+1=ξj+dj，并且j=j+1，轉(zhuǎn)到步驟2。

本節(jié)將用非精確牛頓法作為子算法的增廣Lagrange法求解當(dāng)Ω=Rn情況下的數(shù)值算例。利用擬牛頓法通過令xk+1=ξj去找到第k次迭代的近似解，滿足下述條件

此時ε1=10-7，下面將通過Matlab編程進(jìn)行數(shù)值實(shí)驗(yàn)［22］。

例1 考慮下面變分不等式問題

式中：F(x)=并且b=0，F(xiàn)(x)是一個單調(diào)算子。

在此算例中，令ε0=10-9，ε1=10-7，α=0.4并且ηj=(j=0，1，2，…)，在非精確牛頓法中的第j次廣義雅克比Hj的具體表達(dá)式為

接下來計(jì)算Bj，設(shè)

Bj的第一行元素有如下表達(dá)式

Bj的對角元素(i=2，3，…)有如下表達(dá)式

Bj的第一列元素有如下表達(dá)式

最后計(jì)算Bj中的其余元素，有

數(shù)值計(jì)算結(jié)果匯總見表1，其中k表示測試的迭代次數(shù)，Times表示測試第二次終止的時間。

表1 關(guān)于例1問題的數(shù)值模擬結(jié)果

為驗(yàn)證算法的可行性與有效性，在同等精度下，利用增廣Lagrange法與參考文獻(xiàn)［17］中的算法做比較，文獻(xiàn)［17］中算法結(jié)果如表2所示，不難發(fā)現(xiàn)增廣Lagrange法迭代次數(shù)更少，具有一定的優(yōu)勢。

表2 文獻(xiàn)中的數(shù)值模擬結(jié)果

參考文獻(xiàn)［15］中，對于算例1也使用了增廣Lagrange方法，但廣義雅克比的Hj的表達(dá)式是放到正卦限中研究，而不是在二階錐中研究，對此有表2的模擬結(jié)果。經(jīng)過表2與表1的對比，不難發(fā)現(xiàn)利用改進(jìn)的增廣Lagrange方法，迭代的次數(shù)更少，結(jié)果更穩(wěn)定。

例2 考慮下面變分不等式問題

式中：M是一個正半定矩陣，在此算例中，ε0=10-9；ε1=10-7；α=0.4；且ηj=(j=0，1，2，…)。在非精確牛頓法中的第j次廣義雅克比Hj的具體表達(dá)為

數(shù)值計(jì)算結(jié)果匯總?cè)绫?。

表3 關(guān)于例2問題的數(shù)值模擬結(jié)果

例3 考慮下面變分不等式問題

數(shù)值計(jì)算結(jié)果見表4。

表4 關(guān)于例3問題的數(shù)值模擬結(jié)果

4 結(jié)論

本文是基于Lagrange函數(shù)，將二階錐約束變分不等式問題轉(zhuǎn)化為二階錐優(yōu)化問題。通過討論二階錐錐優(yōu)化問題一系列的等價形式，構(gòu)造了一種求解二階錐約束變分不等式問題的增廣Lagrange方法。本文從實(shí)際的角度出發(fā)，考慮Ω∈Rn的特殊情況，即將Lagrange法迭代公式轉(zhuǎn)化為方程組，并用非精確牛頓法進(jìn)行求解。本文針對三個數(shù)值算例進(jìn)行了數(shù)值模擬，并根據(jù)數(shù)值結(jié)果證明了增廣Lagrange法的可行性與有效性。