線性圓錐互補(bǔ)問題的非單調(diào)非精確光滑牛頓法

汪 洋, 張所濱, 遲曉妮, 李 坤

(1. 桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004;2. 桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院, 廣西 桂林 541004; 3. 桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 廣西高校數(shù)據(jù)分析與計(jì)算重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004; 4. 桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004)

1 引言及預(yù)備知識

考慮線性圓錐互補(bǔ)問題(LCCCP):尋找(x,y)∈Rn×Rn,使得

(1)

(2)

其中n=n1+n2+…+nN.ni-維圓錐定義[1]為

cosθi‖xi‖≤xi0},

(3)

Kni={xi=(xi0,xi1)∈R×Rni-1:

‖xi1‖≤xi0}.

(4)

圓錐與二階錐之間的代數(shù)關(guān)系[2]:對任意xi=(xi0,xi1)∈R×Rni-1和yi=(yi0,yi1)∈R×Rni-1有

?Hixi∈Kni,

(5)

其中

圓錐互補(bǔ)問題(CCCP)在金融、圖像處理和工程等領(lǐng)域有廣泛的應(yīng)用,如多指機(jī)器人的最優(yōu)抓取操作、四足機(jī)器人動力優(yōu)化等實(shí)際問題[3-5].由于圓錐是非對稱錐,一些經(jīng)典的算法一般不能直接應(yīng)用到CCCP,因此CCCP的研究有重要的理論意義和實(shí)際應(yīng)用價(jià)值.近年來,國內(nèi)外學(xué)者在圓錐的性質(zhì)、譜分解[2]和凸二次圓錐優(yōu)化的原-對偶內(nèi)點(diǎn)算法[6]等方面做了一些研究.但目前關(guān)于圓錐互補(bǔ)問題的算法尚不多見.本文基于文獻(xiàn)[7]給出了一個圓錐互補(bǔ)函數(shù)的光滑函數(shù),運(yùn)用一個新的非單調(diào)線搜索技術(shù)[8],給出求解LCCCP的非單調(diào)光滑非精確牛頓方法.該算法采用一個凸組合型非單調(diào)技巧,且在每步迭代只需求解一個線性方程組和進(jìn)行一次線搜索.在適當(dāng)假設(shè)下證明算法具有全局收斂性和局部二階收斂速度.數(shù)值結(jié)果表明算法的有效性.

下面給出與二階錐相伴的歐幾里得約當(dāng)代數(shù)[9].對任意x=(x0,x1)∈R×Rn-1和y=(y0,y1)∈R×Rn-1,定義約當(dāng)積為

x°y=(xTy,x0y1+y0x1),

其單位元e=(1,0,…,0)∈Rn.對任意x=(x0,x1)∈R×Rn-1,定義箭形矩陣

其中I是n-1階單位矩陣.對任意x,y∈Rn有L(x)y=x°y.

下給出向量的譜分解[9].對任意x=(x0,x1)∈R×Rn-1,其譜分解為

x=λ1u(1)+λ2u(2),

(6)

其特征值和特征向量分別為

λi=x0+(-1)i‖x1‖,

其中,ω∈Rn-1是滿足‖ω‖=1的任意向量,u(1)和u(2)分別是屬于特征值λ1和λ2的特征向量.

定義1.1[10]如果對任意(x,y)∈Rn×Rn有

〈x-y,F(x)-F(y)〉≥0,

則稱函數(shù)F:Rn→Rn是單調(diào)的.

定義1.2設(shè)函數(shù)G:Rn→Rm在x∈Rn是局部Lipschitz連續(xù)的.若G在x處方向可導(dǎo),且對任意V∈?G(x+Δx)有

G(x+Δx)-G(x)-V(Δx)=o(‖Δx‖),

其中?G表示G的廣義雅可比矩陣[11],則稱G是半光滑的.

若G在x處半光滑,且

G(x+Δx)-G(x)-V(Δx)=O(‖Δx‖1+p),

其中0

若函數(shù)G:Rn→Rm在任意x∈Rn處是半光滑的(強(qiáng)光滑的),則它是半光滑(強(qiáng)光滑)函數(shù).

2 光滑函數(shù)及其性質(zhì)

對任意(x,y)∈Rn×Rn和μ∈R++,Chen-Harker-Kanzow-Smale(CHKS)光滑函數(shù)[12]

是二階錐互補(bǔ)函數(shù)

的一個光滑函數(shù).

本文考慮函數(shù)φ:R++×Rn×Rn→Rn有

φ(μ,x,y)=

(7)

當(dāng)μ=0時

可得(7)式定義的φ(μ,x,y)是圓錐互補(bǔ)函數(shù)

的一個光滑函數(shù).

令z=(μ,x,y)∈R++×Rn×Rn,定義函數(shù)Φ(μ,x,y):R1+2n→R1+2n為

(8)

基于圓錐互補(bǔ)函數(shù)的一個光滑函數(shù)(7)式,在每步迭代中應(yīng)用光滑牛頓方法求解方程組Φ(z)=0.令μ↓0時,可得LCCCP(1)的解.記z*:=(μ*,x*,y*).顯然Φ(z*)=0?(x*,y*)是LCCCP(4)的解.

定理2.1設(shè)Φ(z)由(8)式定義,則下列結(jié)論成立.

(i)Φ(z)在任意z=(μ,x,y)∈R++×Rn×Rn處連續(xù)可微,其雅可比矩陣為

Φ′(z)=

(9)

其中

H-L-1(w)L(w1)H,

(10)

H-1+L-1(w)L(w1)H-1,

(11)

w1:=Hx-H-1y,

(ii) 設(shè)M是半正定矩陣,則對任意z=(μ,x,y)∈R++×Rn×Rn,Φ′(z)可逆.

證明類似于文獻(xiàn)[13]的定理2.4的證明,知(i)成立.

(ii) 令Δz:=(Δμ,Δx,Δy)∈R×Rn×Rn是Φ′(z)零空間中任一向量,只需證Δz=0即可.由(9)式知

Δμ=0,

(12)

-MΔx+Δy=0,

(13)

C(μ,x,y)Δμ+D(μ,x,y)Δx+

E(μ,x,y)Δy=0.

(14)

由(12)和(14)式得

D(μ,x,y)Δx+E(μ,x,y)Δy=0.

(15)

在(15)式的左右兩邊同時左乘L(w)得

L(w)D(μ,x,s)Δx+

L(w)E(μ,x,y)Δy=0.

(16)

由D(μ,x,y)和E(μ,x,y)的定義及H是對角陣有

L(w)D(μ,x,y)=L(w)H-L(w1)H=

L(w)E(μ,x,y)=L(w)H-1+L(w1)H-1=

又因?yàn)?/p>

?Kn0.

由文獻(xiàn)[14]的引理3.1得L(w)D(μ,x,y)和L(w)E(μ,x,y)都是正定矩陣必可逆,且

[L(w)D(μ,x,y)][L(w)E(μ,x,y)]

的對稱部分正定.在(16)式兩邊同時左乘ΔxT[L(w)E(μ,x,y)]-1有

ΔxT[L(w)E(μ,x,y)]-1[L(w)D(μ,x,y)]×

Δx+ΔxTΔy=0.

由(13)式和M半正定得ΔxTΔy≥0,從而有

ΔxT[L(w)E(μ,x,y)]-1×

[L(w)D(μ,x,y)]Δx≤0.

(17)

又[L(w)D(μ,x,y)][L(w)(E(μ,x,y)]對稱部分正定,從而

ΔxT[L(w)E(μ,x,y)]-1[L(w)D(μ,x,y)]Δx=

(18)

其中

故由(17)和(18)式得Δx=0.由于L(w)E(μ,x,y)可逆,故由(16)式得Δy=0.證畢.

3 LCCCP的非單調(diào)非精確光滑牛頓法

定義函數(shù)f:R++×Rn×Rn→R++為

f(z):=‖Φ(z)‖2=μ2+

‖y-(Mx+q)‖2+‖φ(μ,x,y)‖2.

(19)

算法3.1LCCCP的非單調(diào)非精確光滑牛頓法.

步1若‖Φ(zk)‖=0,停止,否則,令

ρ(zk):=γmin{1,f(z0),…,f(zk)}.

(20)

步2解方程組

(21)

其中,hk=(0,?k)∈R×R2n,‖hk‖≥εμ0min{1,f(z0),…,f(zk)}.求得搜索方向Δzk:=(Δμk,Δxk,Δyk)∈R×Rn×Rn.

步3確定步長λk=δlk.這里lk是滿足下列不等式的最小非負(fù)整數(shù)

f(zk+δlΔzk)≤

Ck-2σ(1-γμ0-εμ0)μlCk.

(22)

步4令zk+1:=zk+λkΔzk,且

Ck+1=f(zk+1)+ηk(Ck-f(zk+1)).

(23)

置k:=k+1.轉(zhuǎn)步1.

注3.1(i) 算法3.1運(yùn)用了非單調(diào)線搜索技術(shù)[8];

(ii)Ck是Ck-1和f(zk)的凸組合;

(iii) 當(dāng)ηk=0時為單調(diào)線搜索;

(iv) 參數(shù)ηk的選取對線搜索的非單調(diào)程度有影響.

定義集合

Γ={z=(μ,x,y)∈R++×Rn×Rn:

μ≥ρ(z)μ0},

其中ρ(z)由(20)式定義.

引理3.1設(shè)M是半正定矩陣且{zk=(μk,xk,yk)}是算法3.1生成的迭代序列,則對任意k≥0有

(i) {ρ(zk)}和{μk}都是單調(diào)遞減序列;

(ii) 對任意k≥0有μk>0和zk∈Γ;

(iii) {Ck}是單調(diào)遞減的,且對任意k≥0有

f(zk+1)≤Ck+1≤Ck.

證明由文獻(xiàn)[15]的引理4.5易證(i)和(ii).下證(iii).對任意k≥0,由(22)式有

f(zk+1)-Ck≤Ck-2σ(1-γμ0-εμ0)=

δlkCk-Ck=

-2σ(1-γμ0-εμ0)δlkCk≤0.

(24)

由(23)式有

Ck+1-Ck=f(zk+1)+ηk(Ck-f(zk+1))-Ck=

(1-ηk)f(zk+1)+(ηk-1)Ck=

(1-ηk)(f(zk+1)-Ck)≤0.

(25)

又由(23)和(24)式得

f(zk+1)-Ck+1=ηk(f(zk+1)-Ck)≤0,

所以{Ck}單調(diào)遞減,且f(zk+1)≤Ck+1≤Ck成立.

定理3.2設(shè)M是半正定矩陣,則算法3.1具有適定性.

證明由定理2.1知對任意μ>0有Φ′(zk)可逆,從而步2是適定的.下證步3是適定的.根據(jù)ρ(zk)的定義(20)式,當(dāng)f(zk)<1時有

當(dāng)f(zk)≥1時,有

因此對任意k≥0有

(26)

同理可得

‖Φ(zk)‖·‖hk‖≤εμ0f(zk).

(27)

對任意λ∈(0,1],定義

rk(λ):=f(zk+λΔzk)-

f(zk)-λf′(zk)Δzk.

(28)

由于f(·)在zk∈R++×Rn×Rn處連續(xù)可微,故

|rk(λ)|=o(λ).

(29)

由(19)、(21)、(26)～(29)式和引理3.1得

f(zk+λΔzk)=f(zk)+λf′(zk)Δzk+rk(λ)=

f(zk)+2λΦT(zk)Φ′(zk)Δzk+o(λ)=

2λΦT(zk)hk+o(λ)≤

f(zk)+2λγμ0f(zk)-2λf(zk)+

2λ‖Φ(zk)‖·‖hk‖+o(λ)≤

f(zk)-2λ(1-γμ0-εμ0)f(zk)+o(λ)≤

Ck-2λ(1-γμ0-εμ0)Ck+o(λ).

f(zk+λΔzk)≤Ck-2σ(1-γμ0-εμ0)λCk.

所以步3在第k次迭代是適定的,從而算法3.1適定.

4 收斂性分析

下面分析算法3.1的全局收斂性和局部二階收斂性.

定理4.1設(shè)M是半正定矩陣,{zk=(μk,xk,yk)}是算法3.1生成的序列,則{zk}的任一聚點(diǎn)z*:=(μ*,x*,y*)都是Φ(z)=0的解,從而(x*,y*)是LCCCP(1)的解.

證明由引理3.1知{ρ(zk)}單調(diào)遞減必收斂,因此存在常數(shù)ρ(z*)≥0,使得

設(shè)ρ(z*)>0,由引理3.1(ii)有

0<μ0ρ(z*)≤μ*.

故由引理3.1得

(30)

不失一般性,令

(31)

f(zk+λΔzk)≤Ck-2σ(1-γμ0-εμ0)λCk.

(32)

f(zk+1)=f(zk+λkΔzk)≤

Ck-2σ(1-γμ0-εμ0)λkCk≤

(33)

由(25)式得

Ck+1-Ck=(1-ηk)(f(zk+1)-Ck)≤0.

又由引理3.1知{Ck}單調(diào)遞減且有下界,且1-ηk≥1-ηmax>0,故當(dāng)k→∞時

從而

對(33)式兩邊取極限得

f(z*)≤C*-

(34)

定理4.2(局部二階收斂) 設(shè)M是半正定矩陣,z*是算法3.1產(chǎn)生序列{zk}的任意聚點(diǎn),且任意V∈?Φ(z*)非奇異,則{zk}局部二階收斂到{z*},即

‖zk+1-z*‖=O(‖zk-z*‖2),

證明類似于文獻(xiàn)[16]中定理8的證明,略去.

5 數(shù)值算例

運(yùn)用Matlab(R2012a)編程,在Intel(R) Core(TM) i5 6200U CPU @ 2.30GHz 2.40 GHz 8 GB內(nèi)存,Windows 10 操作系統(tǒng)的計(jì)算機(jī)上做數(shù)值算例,測試算法3.1的數(shù)值效果.

算法3.1中參數(shù)取值為:μ0=0.1,δ=0.75,ηk=0.7,σ=0.225,γ=0.2,ε=0.1.當(dāng)‖Φ(z)‖≤10-6時,算法3.1停止.Iter指平均迭代次數(shù),ACPU指平均CPU時間.LCCCP(4)中矩陣M是通過M=NTN所得到的,N是方陣,N和q中元素是隨機(jī)產(chǎn)生的位于區(qū)間[0,1]的數(shù).令x0=e∈Rn,y0=0∈Rn為初始點(diǎn).針對每種情形均隨機(jī)產(chǎn)生10個問題進(jìn)行求解,數(shù)值結(jié)果見表1～4.

表 1 運(yùn)用算法3.1求解不同規(guī)模和旋轉(zhuǎn)角的CCCP的數(shù)值結(jié)果

表 2 當(dāng)時,算法3.1單調(diào)線搜索與非單調(diào)線搜索性能比較

表2～4給出運(yùn)用算法3.1求解不同旋轉(zhuǎn)角度和不同規(guī)模的LCCCP時單調(diào)線搜索和非單調(diào)線搜索所需的CPU時間和迭代次數(shù).數(shù)值結(jié)果表明非單調(diào)線搜索要比單調(diào)線搜索所需的CPU時間和迭代次數(shù)要少.從表1～4的數(shù)值結(jié)果看出,運(yùn)用算法3.1求解LCCCP所需的CPU時間和迭代次數(shù)較少,且相對穩(wěn)定,從而表明算法3.1的有效性.

表 3 當(dāng)時,算法3.1單調(diào)線搜索與非單調(diào)線搜索性能比較

表 4 當(dāng)時,算法3.1單調(diào)線搜索與非單調(diào)線搜索性能比較