求解二階錐互補(bǔ)問(wèn)題的一種非精確光滑化牛頓算法

薛文娟

( 福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院, 福建 福州 350002 )

0 引言

定義Rn中的二階錐(SOC)為:

Kn={(x1,x2)∈R×Rn-1|x1≥‖x2‖},

不失一般性，本文考慮單個(gè)二階錐上的二階錐規(guī)劃，其原問(wèn)題(PSOCP)為:

min{cTx|Ax=b,x∈Kn},

其中A∈Rm×n,c∈Rn,b∈Rm為給定的已知量，x∈Kn為變量.原問(wèn)題的對(duì)偶問(wèn)題(DSOCP)為:

max{bTy|ATy+t=c,t∈Kn,y∈Rm},

其中t∈Kn為松弛變量，y∈Rm為變量.

二階錐互補(bǔ)規(guī)劃問(wèn)題作為數(shù)學(xué)領(lǐng)域的一個(gè)重要分支，在工程、金融等領(lǐng)域具有廣泛地應(yīng)用[1].2002年，Qi等[2]提出了一種光滑化牛頓法用于求解變分不等式等問(wèn)題，因?yàn)樵摲椒ň哂休^好的收斂性和計(jì)算效果，所以被廣泛地應(yīng)用于二階錐規(guī)劃問(wèn)題的求解中[3-7].但目前為止，該方法大多用于求解線性互補(bǔ)問(wèn)題，而較少應(yīng)用于錐互補(bǔ)問(wèn)題的研究；因此，本文基于一個(gè)向量函數(shù)，給出二階錐規(guī)劃問(wèn)題的一種非精確光滑化牛頓算法，并證明該算法具有全局收斂性.

1 預(yù)備知識(shí)

(1)

用x2表示x°x,x+t表示向量加法，于是(°,+，ε)構(gòu)成一個(gè)若當(dāng)代數(shù)，其中ε=(1,0)∈R×Rn-1.

x=λ1u1+λ2u2;

(2)

λi=x1+(-1)i‖x2‖;

(3)

(4)

g(x)=g(λ1)μ1+g(λ2)μ2，x∈Kn.

(5)

由式(5)可得：

[x]+= [λ1]+u1+[λ2]+u2，x∈Rn;

lnx=lnλ1·u1+lnλ2·u2，x∈Kn.

定義一個(gè)向量值函數(shù)φ∶Rn×Rn×R++→Rn為

(6)

令z∶=(x,t,μ)， 定義函數(shù)H(z)∶Rn×Rm×R++→Rm×Rn×R++為

(7)

以下給出φ(x,t,μ)的一些性質(zhì).

ii) 對(duì)任意z=(x,y,μ)∈Rn×Rm×R++, 函數(shù)φ(x,t,μ)均為連續(xù)可微，且此函數(shù)的雅可比為

iv)φ(x,t,0)=0 ?x∈Kn,t∈Kn,xTt=0.

4)由于Kn={x∈Rn|xTt≥0,?t∈Kn}是一個(gè)閉的自對(duì)偶凸錐，則根據(jù)文獻(xiàn)[8]中的引理2.2可得對(duì)任意兩個(gè)向量x,y∈Rn, 滿足x=[x-t]+?x∈Kn,t∈Kn,xTt=0.

定理1定義函數(shù)H(z)如式(7)，則有如下結(jié)論：

i) 問(wèn)題PSOCP和DSOCP的解與方程組H(z)=0的解一致.

ii) 對(duì)任意z=(x,y,μ)∈Rn×Rm×R++，H(z)連續(xù)可微，其雅可比為

(8)

iii)如果矩陣A的行向量組線性獨(dú)立，則對(duì)任意μ>0,H′(z)為非奇異.

證明1)因求解問(wèn)題PSOCP和DSOCP等價(jià)于求解

Ax=b,ATy+t=c,x°t=0,x∈Kn,t∈Kn,

則由性質(zhì)1的iv)知問(wèn)題PSOCP和DSOCP的解與方程組H(z)=0的解一致，結(jié)論i)得證.

2)由式(7)和性質(zhì)1中的φ′(x,t,μ)表達(dá)式易得結(jié)論ii)成立.

3)為證明結(jié)論iii)，令Δz∶=(Δx,Δy,Δμ)∈Rn×Rm×R.在此只要證明方程H′(z)Δz=0只有零解即可.由式(8)知方程H′(z)Δz=0等價(jià)于

(9)

2 光滑化牛頓算法及其收斂性

ψ(z)∶=‖H(z)‖2,β(z)∶=rmin{1,ψ(z)}.

第1步 若ψ(zk)∶=‖H(zk)‖2≤ξ, 則停止算法；否則計(jì)算

βk∶=β(zk)∶=rmin{1,‖H(zk)‖2}.

(10)

第2步 求解方程(11)得Δzk∶=(Δxk,Δtk,Δμk)∈Rn×Rn×R++.

DH(zk)Δzk=-H(zk)+βk‖H(zk)‖2e0,

(11)

其中DH(zk)為H(z)在點(diǎn)zk處的雅可比表達(dá)式.

第3步αk是1,δ,δ2,…中滿足條件

ψ(zk+αkΔzk)≤[1-σ(1-rμ0)αk]ψ(zk)

(12)

的最大數(shù).

第4步 令Δzk+1∶=zk+αkΔzk,k∶=k+1; 轉(zhuǎn)到第1步.

定理2設(shè)矩陣A行向量線性獨(dú)立,則算法1可產(chǎn)生無(wú)窮序列{zk∶=(xk,tk,μk)}, 且下述結(jié)果成立：

i) {ψ(zk)}、{‖H(zk)‖}和{βk}均是單調(diào)下降的，且{ψ(zk)}、{‖H(zk)‖}收斂于0.

ii) 記Ω∶={z∶=(x,t,μ)∈Rn×Rn×R++,μ≥μ0β(z)‖H(z)‖2}, 則zk∈Ω.

證明1)由于矩陣A行向量線性獨(dú)立,則類似文獻(xiàn)[9]中的定理3.1的證明，可得算法1是可行的.因此，算法1能產(chǎn)生無(wú)窮序列{zk∶=(xk,tk,μk)}.由式(12)可得{ψ(zk)}是單調(diào)下降的，因此{(lán)‖H(zk)‖}和{βk}均是單調(diào)下降的.

2)利用歸納法證明ii).由于β(z0)‖H(z0)‖2=r‖H(z0)‖2min{1,‖H(z0)‖2}≤r‖H(z0)‖2<1, 因此μ0≥μ0β(z0)‖H(z0)‖2, 故z0∈Ω.假設(shè)zk∈Ω， 即μk≥μ0βk‖H(zk)‖2, 則

μk+1-μ0βk+1‖H(zk+1)‖2=μk+αkΔμk-μ0βk+1‖H(zk+1)‖2=

μk+αk[-μk+μ0βk‖H(zk)‖2]-μ0βk+1‖H(zk+1)‖2=(1-αk)μk+

αkμ0βk‖H(zk)‖2-μ0βk+1‖H(zk+1)‖2≥(1-αk)μ0βk‖H(zk)‖2+

αkμ0βk‖H(zk)‖2-μ0βk+1‖H(zk+1)‖2=μ0βk‖H(zk)‖2-μ0βk+1‖H(zk+1)‖2=

μ0[βk‖H(zk)‖2-βk+1‖H(zk+1)‖2]≥0.

(13)

式(13)中的第1個(gè)不等式可由zk∈Ω得到，第2個(gè)等式可由式(10)得到，最后的不等式(≥0)可由結(jié)果i)得到.

假設(shè)1問(wèn)題SCCP的解集S∶={(x,t)∈Rn×Rn:x∈Kn,t∈Kn,xTt=0,Ax=b,ATy+t=c} 為非空有界.

定理3設(shè)矩陣A行向量線性獨(dú)立, {zk∶=(xk,tk,μk)}是由算法1得到的無(wú)限序列,則{zk∶=(xk,tk,μk)}任一聚點(diǎn)z*=(x*,t*,μ*)是H(z)=0的解.

證明因證明類似于文獻(xiàn)[9]中定理3.2的證明，故在此省略證明.

3 數(shù)值試驗(yàn)

表1 算法1的數(shù)值試驗(yàn)結(jié)果