一種廣義擴展型増廣拉格朗日方法

于奧林， 孔玉倩， 申遠

(1.南京財經(jīng)大學 紅山學院， 南京 210023； 2.南京財經(jīng)大學 應(yīng)用數(shù)學學院， 南京 210023)

0 引言

増廣拉格朗日方法(ALM)是求解線性約束凸優(yōu)化問題的經(jīng)典算法.線性等式約束的凸優(yōu)化模型為：

min{θ(x)|Ax=b,x∈χ},

(1)

其中θ(x):Rn→R是一個閉凸函數(shù)(不一定是強凸或光滑的),χ?Rn是一個閉凸集,A∈Rm ×n,b∈Rm.由于x的子問題不易求解，因此通常將問題(1)迭代為：

(2)

其中：β>0是罰參數(shù)，λ∈Rm是拉格朗日乘子，x和λ分別為原始變量和對偶變量.

優(yōu)化問題(1)的拉格朗日方程為L(x,λ)=θ(x)-λT(Ax-b), 其中(x,λ)∈χ×Rm.令拉格朗日方程的鞍點為(x*,λ*)， 則有：

Lλ∈Rm(x*,λ)≤L(x*,λ*)≤Lx∈χ(x,λ*).

上式等價于以下變分不等式：

(3)

式(3)的緊湊形式為如下單調(diào)變分不等式(VI):

ω*∈Ω,θ(x)-θ(x*)+(ω-ω*)TF(ω*)≥0,?u∈Ω,

(4)

(5)

(6)

(7)

由文獻[1]可知，式(7)是對偶 -原始迭代順序的定制鄰近點算法(C -PPA)[1].為了更好地求解優(yōu)化問題(1)，文獻[2]的作者在平衡増廣拉格朗日方法(B -ALM)的基礎(chǔ)上增加了Ax≥b這一條件，進而可較為容易地計算出經(jīng)典ALM(2)中的兩個子問題.

(8)

(9)

1 廣義擴展型增廣拉格朗日算法

本文考慮更一般的凸規(guī)劃模型，該模型包括線性不等式約束和不等式約束：

min{θ(x)|Ax=b(或≥b),x∈χ}.

(10)

GEALM算法s(s>0)、γ(γ>0)、β(β>0)和r(r>0)是任意常數(shù)， (xk,λk)為給定的迭代點，新的迭代點(xk +1,λk +1)由以下步驟產(chǎn)生：

(11)

GEALM算法的收斂性取決于以下矩陣的正定性：

(12)

引理2GEALM算法產(chǎn)生的序列{ωk=(xk,λk)}可使下式成立：

ωk +1∈Ω,θ(x)-θ(xk +1)+(ω-ωk +1)TF(ωk +1)≥(ω-ωk +1)TH(ωk-ωk +1),?ω∈Ω.

(13)

證明在式(11)中，關(guān)于x的子問題的解可描述為：

在上式中，對于任何未知的λk +1均有：

xk +1∈χ,θ(x)-θ(xk +1)+(x-xk +1)T(-ATλk +1)≥

(14)

同理，式(14)中關(guān)于λk +1的子問題的解可由下式描述：

由以上可得：

λk +1∈Λ, (λ-λk +1)T(Axk +1-b)≥

(15)

聯(lián)立式(14)和式(15)，由此再根據(jù)式(4)中的符號即可得式(13).證畢.

引理3GEALM算法產(chǎn)生的序列{ωk=(xk,λk)}可使下式成立：

θ(x)-θ(xk +1)+(ω-ωk +1)TF(ω)≥

(16)

證明由于式(4)定義的算子F是帶有斜對稱矩陣的仿射算子，因此有：

(17)

由式(17)可知(ω-ωk +1)TF(ωk +1)=(ω-ωk +1)TF(ω)， 由此進一步可知式(13)的左端等價于θ(x)-θ(xk +1)+(ω-ωk +1)TF(ω).綜合上述可知：

ωk +1∈Ω,θ(x)-θ(xk +1)+(ω-ωk +1)TF(ω)≥(ω-ωk +1)TH(ωk-ωk +1),?ω∈Ω.

(18)

(19)

將式(19)代入式(18)的不等號右邊即可得證引理3.

定理1因在GEALM算法生成的序列{ωk=(xk,λk)}中含有矩陣H， 且在式(12)中定義了該矩陣，因此序列{ωk}滿足：

(20)

證明將式(16)中的ω設(shè)為任意固定的ω*∈Ω*， 則由此可得：

2{θ(xk +1)-θ(x*)+(ωk +1-ω*)TF(ω*)},?ω*∈Ω*.

由于ω*∈Ω*，ωk +1∈Ω， 所以根據(jù)式(4)可知上述不等式的不等號右端為非負，定理1得證.

定理2因在GEALM算法生成的序列{ωk=(xk,λk)}中含有矩陣H， 且在式(12)中定義了該矩陣，因此序列{ωk}可收斂到某個ω∞∈Ω*.

ωkj∈Ω,θ(x)-θ(xkj)+(ω-ωkj)TF(ωkj)≥(ω-ωkj)TH(ωkj-1-ωkj),?ω∈Ω.

ω∞∈Ω,θ(x)-θ(x∞)+(ω-ω∞)TF(ω∞)≥0,?ω∈Ω.

2 數(shù)值實驗

實驗環(huán)境為：筆記本電腦，處理器為Intel Core i5 -8250U CPU@1.60 GHz 1.80 GHz，內(nèi)存為4 GB，系統(tǒng)為Windows10，軟件為MATLAB R2016b.實驗中給定矩陣C為對稱矩陣.在F-模下求與C距離最近的相關(guān)性矩陣為：

(21)

由表1和表2及圖1—圖4可知，在矩陣取不同維度和tol取不同數(shù)值時， GEALM算法在迭代次數(shù)、CPU運行時間、收斂速度等方面顯著優(yōu)于C -PPA算法，由此表明GEALM算法優(yōu)于C -PPA算法.

表1 tol=le-10時2種算法的迭代次數(shù)和CPU運行時間

圖1 n=150時2種算法的迭代變化 圖2 n=300時2種算法的迭代變化

表2 tol=le-12時2種算法的迭代次數(shù)和CPU運行時間

圖3 n=100時2種算法的迭代變化 圖4 n=200時2種算法的迭代變化