楊曉麗，劉紅衛(wèi)

(西安電子科技大學(xué) 理學(xué)院，陜西 西安 710071)

求解半定互補(bǔ)問題的一種非內(nèi)點(diǎn)連續(xù)算法

楊曉麗，劉紅衛(wèi)

(西安電子科技大學(xué) 理學(xué)院，陜西 西安 710071)

基于光滑F(xiàn)B函數(shù)理論和中心路徑原則，提出求解半定互補(bǔ)問題的一種非內(nèi)點(diǎn)連續(xù)算法，在適當(dāng)?shù)臈l件下證得其全局線性收斂性和局部二次收斂性，并通過數(shù)值試驗(yàn)驗(yàn)證了算法可行性和有效性。

半定互補(bǔ);非內(nèi)點(diǎn)連續(xù)算法;光滑F(xiàn)B函數(shù);全局線性收斂;局部二次收斂

0 引言

χ表示n×n對角實(shí)陣組成的空間，χ對矩陣加法X+Y，乘法XY，轉(zhuǎn)置XT，求逆X-1運(yùn)算均封閉。χ的內(nèi)積和范數(shù)：表示χ中的對稱矩陣組成的子空間，κ是S半正定陣組成的凸錐。所謂半定互補(bǔ)(SDCP)問題是：F是S→S的函數(shù)，尋找X∈S，使

1 光滑F(xiàn)B函數(shù)和中心路徑知識介紹

已知φμ：κ2→κ表示光滑的FB矩陣函數(shù)，μ＞0為光滑參數(shù)，I為n×n單位矩陣，

如果μ→0，那么

［X*-Y*］+是［X*-Y*］在κ上正交投影，H0(X*，Y*)=0?(X*，Y*)為(SDCP)(1)的解。

求解半定互補(bǔ)問題(SDCP)(1)思想：將之看成非光滑再生方程組H0(X，Y)=0，用光滑方程組Hμ(X，Y)=0逐步逼近它;在每次迭代中求一次光滑方程組Hμ(X，Y)=0，并通過逐步減小光滑參數(shù)μ，使μ→0，來達(dá)到‖Hμ(X，Y)‖減小的目地。然而實(shí)際中不可能得到方程組Hμ(X，Y)=0在μ＞0時(shí)的解。需引入(SDCP)(1)的中心路徑：

它的領(lǐng)域?yàn)?/p>

領(lǐng)域(7)一部分為

可求出Hμ(X，Y)=0一些近似解{X(μ)，Y(μ)}∈N(β，(0，μ0))。

φμ(X，Y)的性質(zhì)：

引理1［1］▽φμ是Lipschitz連續(xù)的。

再令

2 算法描述

算法1：Step0：選取δ，γ，σ∈(0，1)，任取(X0，Y0)∈S×S，μ0＞0，選β使

Step1：若μk=0，停止;(Xk，Yk)是(SDCP)(1)的一個(gè)解。否則，轉(zhuǎn)Step2。

Step2：若Hμk(Xk，Yk)=0，則令(Xk+1，Yk+1)=(Xk，Yk)，θk=1，轉(zhuǎn)Step4;否則，令(△Xk，△Yk)∈S×S為以下方程組的一個(gè)解

Step3：令θk=max{1，δ，δ}，并使

設(shè)定

Step4：令

且ηk=max{1，γ，γ2，…}，使

(ii)理論上，把μk=0作為終止條件。然而實(shí)際中，經(jīng)常把μk≤ε作為終止條件。

(iii)在算法第k次迭代中，若滿足條件‖Hμk(Xk，Yk)‖≠0，則需先解線性方程組(9)，再執(zhí)行一次線搜索(10)即可;否則，算法不需要解方程組(9)和執(zhí)行線搜索(10)。也就是說，在算法每次迭代中，至多需解一次線性方程組。

3 算法收斂性分析

假設(shè)A1 對任何β＞0和μ0＞0，(8)定義的領(lǐng)域N(β，(0，μ0))有界。

假設(shè)A2 對任何k≥0，0＜μk≤μ0，存在一常數(shù)ω＞0，使‖▽Hμk(Zk)-1‖≤ω。

假設(shè)A3 用Ω表示SDCP(1)的解集，對任何(X*，Y*)∈Ω，滿足條件X*+Y*＞0。

定理1 如果F是連續(xù)可微單調(diào)的，{(Zk，μk)}是算法產(chǎn)生的迭代序列，假設(shè)A1和A2均成立，▽F是Lipschitz連續(xù)的(k為Lipschitz連續(xù)常數(shù))，那么存在一常數(shù)ρ∈(0，1)，

對所有的k，有μk+1≤ρμk。

證明：由(12)知，存在一個(gè)θ*∈(0，1］，對所有k，均有θk≥θ*。如果Hμk(Zk)=0，那么θk=1，以上結(jié)論顯然成立;另一方面，Hμk(Zk)≠0，由(9)和假設(shè)A2可知

假設(shè)序列{0，1，2，…}存在一子序列K，當(dāng)k→0時(shí)，有{θk}k∈K→0?？紤]子序列K中的迭代，由(10)可得

又由(10)可得

由引理1知▽φ1是Lipschitz連續(xù)的，設(shè)Lipschitz常數(shù)λ=2+8n，▽F也是Lipschitz連續(xù)的。那么由(3)，(14)和(18)，得到

由(17)，(18)，(19)，得到

令(20)中k∈K，k→∞，已知θk→0，得到σ≥1，這與σ∈(0，1)矛盾。對所有k，有θk∈(0，1］，那么存在θ*∈(0，1］，對所有k，有θk≥θ*。由(12)知，對所有k，均有μk+1≤(1-σθk)μk≤(1-σθ*)μk，最后，令ρ= 1-σθ*，于是μk+1≤ρμk。定理得證。

以上定理1說明了算法的全局線性收斂性。下面定理2將說明其局部二次收斂性。

引理2 如果對任何(X*，Y*)∈Ω，假設(shè)A3均成立，那么X*-Y*可逆，▽φμ(X，Y)在任一點(diǎn)(X，Y)→(X*，Y*)是Lipschitz連續(xù)的。另外，對任何μ＞v≥0，存在一?＞0，

在任一點(diǎn)(X，Y)→(X*，Y*)，使

引理3 如果(i)F是單調(diào)連續(xù)可微的;(ii)(Z*，0)是算法迭代產(chǎn)生的序列{(Zk，μk)}的一個(gè)聚點(diǎn); (iii)▽F是Lipschitz連續(xù)的;(iv)假設(shè)A1，A2，A3均成立;(v)存在一整數(shù)k0，對所有k＞k0，有Hμk(Zk)≠0。那么，存在一整數(shù)k∞＞k0，對所有的k＞k∞，有Zk+1=Zk+△Zk和μk=O(‖Zk-Z*‖)均成立［1］。

定理2 若引理3的(i)(ii)(iii)(iv)均滿足，則存在一kˉ，使μk+1=O()，?K=kˉ，kˉ+1，…。證明：不失一般性，假設(shè){(Zk，μk)}收斂到(Z*，0)，那么存在一k^，對所有k＞k^，都有Zk∈N(Z*，ε)。令kˉ=max{k∞，k^}，于是，對任何k≥kˉ，考慮兩種情況：

如果Hμk(Zk)=0，那么根據(jù)引理2和算法定義，有=(1-σ)μk和

另一方面，如果Hμk(Zk)≠0，由假設(shè)A2，引理2和引理3，得

由A3，知道(X*-Y*)2＞0，因此它的特征值λ*i＞0，i=1，2，…，n。令Λ*=maxiλ*i，那

么存在一正交矩陣p，使

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

在試驗(yàn)中，初始矩陣和參數(shù)值分別設(shè)為：X=3I，M=3I，Q=6I，Y=MX+Q，δ=0.5，γ=0.5，μ0=1，β=，允許誤差值ε=10-10，通過選取不同的σ，對n取不同值(即不同維數(shù)矩陣的情況)時(shí)，對算法1進(jìn)行了試驗(yàn)。試驗(yàn)數(shù)據(jù)如表1所示：

表1 算法1數(shù)值結(jié)果

以上表1，說明非內(nèi)點(diǎn)連續(xù)算法1是求解半定互補(bǔ)問題的一種有效算法。

(i)從表1的列元素看，在σ取固定值，n取任何值時(shí)，數(shù)據(jù)有兩個(gè)明顯特征：一是算法的迭代次數(shù)都是固定的;二是算法運(yùn)行時(shí)間幾乎是隨矩陣維數(shù)增加而變長。于是可以推得對于任何維的矩陣，算法1都是可行的、有效的。

(ii)從表1的行元素看，無論n取何值時(shí)，隨著參數(shù)σ的增長，算法的運(yùn)行時(shí)間幾乎逐漸減短，迭代次數(shù)逐漸減少。于是可得出結(jié)論：參數(shù)σ值越大(不超過1)，非內(nèi)點(diǎn)連續(xù)算法1越有效。

5結(jié)論

本文基于光滑的FB函數(shù)理論和中心路徑原則，提出了求解半定互補(bǔ)問題的一種非內(nèi)點(diǎn)連續(xù)算法，數(shù)值試驗(yàn)還說明了：參數(shù)σ的選取對算法的有效性有一定影響。

［1］ Chen，X.，Tseng P.Non-interior continuation methods for solving semidefinite complementarity problems［J］.Mathematical Programming，2003，95：431-474.

［2］ Burke，J.Xu，S.A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem［J］.Math program，2000，87：113-130.

［3］ Chen，B，Xiu，N.Superlinear noninterior one-step continuation method for monotone LCP in the absence of strict complementarity［J］.J.Optim. Theory Appl，2001，108：317-332.

［4］ 韓繼業(yè)，修乃華，戚厚鐸.非線性互補(bǔ)理論與算法［M］.上海：上?？茖W(xué)技術(shù)出版社，2006.

責(zé)任編輯：鐘 聲

A non-interior point continuation algorithm for solving semidefinite complementarity problem

YANG Xiao-li，LIU Hong-wei
(College of Science，Xidian University，Xi＇an 710071，China)

Based on the smoothing FB function theory and centre path principle，this paper gives a non-interior continuation algorithm for solving semidefinite complementarity problem and proves the global linear convergence and local quadratic convergence under some proper assumptions.Numerical experiments are made to show the feasibility and efficiency of the algorithm.

semidefinite complementarity;non-interior continuation algorithm;smoothing FB function;global linear convergence;local quadratic convergence

O224

A

1009-3907(2010)08-0006-04

2010-06-12

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助［JY10000970004］

楊曉麗(1984-)，女，河北石家莊人，碩士研究生，主要從事最優(yōu)化方法、半定規(guī)劃及其應(yīng)用方面研究。