求解半定互补问题的一种非内点连续算法

杨晓丽，刘红卫

(西安电子科技大学 理学院，陕西 西安 710071)

求解半定互补问题的一种非内点连续算法

杨晓丽，刘红卫

(西安电子科技大学 理学院，陕西 西安 710071)

基于光滑FB函数理论和中心路径原则，提出求解半定互补问题的一种非内点连续算法，在适当的条件下证得其全局线性收敛性和局部二次收敛性，并通过数值试验验证了算法可行性和有效性。

半定互补;非内点连续算法;光滑FB函数;全局线性收敛;局部二次收敛

0 引言

χ表示n×n对角实阵组成的空间，χ对矩阵加法X+Y，乘法XY，转置XT，求逆X-1运算均封闭。χ的内积和范数：表示χ中的对称矩阵组成的子空间，κ是S半正定阵组成的凸锥。所谓半定互补(SDCP)问题是：F是S→S的函数，寻找X∈S，使

1 光滑FB函数和中心路径知识介绍

已知φμ：κ2→κ表示光滑的FB矩阵函数，μ＞0为光滑参数，I为n×n单位矩阵，

如果μ→0，那么

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

求解半定互补问题(SDCP)(1)思想：将之看成非光滑再生方程组H0(X，Y)=0，用光滑方程组Hμ(X，Y)=0逐步逼近它;在每次迭代中求一次光滑方程组Hμ(X，Y)=0，并通过逐步减小光滑参数μ，使μ→0，来达到‖Hμ(X，Y)‖减小的目地。然而实际中不可能得到方程组Hμ(X，Y)=0在μ＞0时的解。需引入(SDCP)(1)的中心路径：

它的领域为

领域(7)一部分为

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

φμ(X，Y)的性质：

引理1［1］▽φμ是Lipschitz连续的。

再令

2 算法描述

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

Step1：若μk=0，停止;(Xk，Yk)是(SDCP)(1)的一个解。否则，转Step2。

Step2：若Hμk(Xk，Yk)=0，则令(Xk+1，Yk+1)=(Xk，Yk)，θk=1，转Step4;否则，令(△Xk，△Yk)∈S×S为以下方程组的一个解

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

设定

Step4：令

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

(ii)理论上，把μk=0作为终止条件。然而实际中，经常把μk≤ε作为终止条件。

(iii)在算法第k次迭代中，若满足条件‖Hμk(Xk，Yk)‖≠0，则需先解线性方程组(9)，再执行一次线搜索(10)即可;否则，算法不需要解方程组(9)和执行线搜索(10)。也就是说，在算法每次迭代中，至多需解一次线性方程组。

3 算法收敛性分析

假设A1 对任何β＞0和μ0＞0，(8)定义的领域N(β，(0，μ0))有界。

假设A2 对任何k≥0，0＜μk≤μ0，存在一常数ω＞0，使‖▽Hμk(Zk)-1‖≤ω。

假设A3 用Ω表示SDCP(1)的解集，对任何(X*，Y*)∈Ω，满足条件X*+Y*＞0。

定理1 如果F是连续可微单调的，{(Zk，μk)}是算法产生的迭代序列，假设A1和A2均成立，▽F是Lipschitz连续的(k为Lipschitz连续常数)，那么存在一常数ρ∈(0，1)，

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

证明：由(12)知，存在一个θ*∈(0，1］，对所有k，均有θk≥θ*。如果Hμk(Zk)=0，那么θk=1，以上结论显然成立;另一方面，Hμk(Zk)≠0，由(9)和假设A2可知

假设序列{0，1，2，…}存在一子序列K，当k→0时，有{θk}k∈K→0。考虑子序列K中的迭代，由(10)可得

又由(10)可得

由引理1知▽φ1是Lipschitz连续的，设Lipschitz常数λ=2+8n，▽F也是Lipschitz连续的。那么由(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*)∈Ω，假设A3均成立，那么X*-Y*可逆，▽φμ(X，Y)在任一点(X，Y)→(X*，Y*)是Lipschitz连续的。另外，对任何μ＞v≥0，存在一ϖ＞0，

在任一点(X，Y)→(X*，Y*)，使

引理3 如果(i)F是单调连续可微的;(ii)(Z*，0)是算法迭代产生的序列{(Zk，μk)}的一个聚点; (iii)▽F是Lipschitz连续的;(iv)假设A1，A2，A3均成立;(v)存在一整数k0，对所有k＞k0，有Hμk(Zk)≠0。那么，存在一整数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，…。证明：不失一般性，假设{(Zk，μk)}收敛到(Z*，0)，那么存在一k^，对所有k＞k^，都有Zk∈N(Z*，ε)。令k¯=max{k∞，k^}，于是，对任何k≥k¯，考虑两种情况：

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

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

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

么存在一正交矩阵p，使

4 数值试验

在试验中，初始矩阵和参数值分别设为：X=3I，M=3I，Q=6I，Y=MX+Q，δ=0.5，γ=0.5，μ0=1，β=，允许误差值ε=10-10，通过选取不同的σ，对n取不同值(即不同维数矩阵的情况)时，对算法1进行了试验。试验数据如表1所示：

表1 算法1数值结果

以上表1，说明非内点连续算法1是求解半定互补问题的一种有效算法。

(i)从表1的列元素看，在σ取固定值，n取任何值时，数据有两个明显特征：一是算法的迭代次数都是固定的;二是算法运行时间几乎是随矩阵维数增加而变长。于是可以推得对于任何维的矩阵，算法1都是可行的、有效的。

(ii)从表1的行元素看，无论n取何值时，随着参数σ的增长，算法的运行时间几乎逐渐减短，迭代次数逐渐减少。于是可得出结论：参数σ值越大(不超过1)，非内点连续算法1越有效。

5结论

本文基于光滑的FB函数理论和中心路径原则，提出了求解半定互补问题的一种非内点连续算法，数值试验还说明了：参数σ的选取对算法的有效性有一定影响。

［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］ 韩继业，修乃华，戚厚铎.非线性互补理论与算法［M］.上海：上海科学技术出版社，2006.

责任编辑：钟 声

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

中央高校基本科研业务费专项资金资助［JY10000970004］

杨晓丽(1984-)，女，河北石家庄人，硕士研究生，主要从事最优化方法、半定规划及其应用方面研究。