线性二阶锥互补问题的非单调线搜索光滑算法

赵花丽

(咸阳师范学院数学与信息科学学院，陕西咸阳 712000)

线性二阶锥互补问题:求解一向量x∈Rn，使其满足

s=Mx+q，x ◦s=0，且 x ∈ Kn，s∈ Kn。

这里M∈ Rn×n，q∈ Rn，n维二阶锥定义为:Kn

二阶锥互补问题是近十年来研究的新问题，目前利用光滑算法［1-4］来求解二阶锥互补问题已成为一个研究热点，本文在光滑算法的基础上利用CM光滑函数提出了线性二阶锥互补问题的非单调线搜索光滑算法。算法中利用非单调因子来控制搜索的非单调程度，对初始点的选取没有任何限制，最后，给出算法的全局收敛性和局部超线性收敛性分析，并且给出数值实验，就非单调因子对计算结果的影响进行了比较。

1 预备知识

对任意的向量x=(x1，x2)，y=(y1，y2)∈R ×Rn-1，定义二阶锥Kn上的若当积:x◦y=(x，[]y，y1x2+x1y2)。

设 λ1，λ2，u1，u2分别表示 x 的特征值和相应的特征向量，则向量x=(x1，x2)∈R×Rn-1可以表示为:x= λ1u1+ λ2u2，其中

2 基于非单调线搜索的光滑算法

本文中用CHKS函数

y=x-s=(y1，y2)∈ R × Rn-1，λ1，λ2分别表示 y的最大、最小特征值，则［2］

其中

将线性二阶锥互补问题转化为求解下面的光滑方程组

显然，对任意光滑参数 μ ＞ 0，H(x，s，μ)的雅可比矩阵 H'(x，s，μ)在任意点 (x，s，μ)都存在。

其中Dx=I-g'(y)，Ds=I+g'(y)，

Dμ=g'(y)。

算法步骤:

(1)令 ω =(x，s，μ)∈Rn× Rn× R+，给定初始值 ω0=(x0，s0，μ0)，取常数 δ，σ ∈ (0，1)，W0=‖H(ω0)‖，Q0=1。

p=(0，0，1)∈ Rn× Rn× R，β ＞ 1 满足‖H(ω0)‖ ≤ βμ0，令 k=0。

(2)如果H(ωk)=0，则算法停止。

(3)求解牛顿方向 (Δxk，Δsk，Δμk)，解线性方程组 H(ωk)+H'(ωk)Δωk=(1/β)Wkp。

(4)确定步长rk=δlk，lk是使得关于l的不等式成立的最小非负整数，

‖H(ωk+ δlΔωk)‖ ≤(1- σ(1-1/β)δl)Wk。

(5)令 ωk+1= ωk+rkΔωk，取参数

ηk∈［0，1］，Qk+1= ηkQk+1

Wk+1=(ηkQkWk+ ‖H(ωk+1)‖/Qk+1。令k=k+1，转步骤(2)。

从算法很容易看出参数ηk的值控制着线搜索的非单调程度，当ηk为0时就是一般的单调Armijo线搜索。

3 收敛性分析

引理1 假定M是半正定矩阵，如果所有V∈∂H(ω*)是非奇异的，则有:

(1)算法所产生的序列{Wk}是单调下降的。

(2)序列{μk}是单调下降的，并且对所有k有:μk＞ 0。

证明:(1)由算法可知:

(2)由算法可知

所以序列{μk}是单调下降的，并且对所有 k有:μk＞ 0。

引理2 假定M是半正定矩阵，如果所有V∈∂H(ω*)是非奇异的，则算法产生的序列{ωk}都位于中心路径的邻域内，即 ‖H(xk，sk，μk)‖ ≤ βμk。

证明:由算法知:

因此对所有 k 有:‖H(xk，sk，μk)‖ ≤ βμk。

引理3 假定M是半正定矩阵，如果所有V∈∂H(ω*)是非奇异的，则由算法产生的序列{Wk}是收敛的且极限为W*=0。

证明:由引理1知

由Qk的定义有:

又因为0＜rk=δlk＜1，

定理1 假定M是半正定矩阵，如果所有V∈∂H(ω*)是非奇异的，则由算法产生的序列{ωk}是有界的且序列 {(xk，sk)}的任意聚点是 SOCCP的解。

证明:首先证明序列{ωk}是有界的。

由引理1知:{μk}是有界的，使得 |μk|＜ ε。下证序列{(xk，sk)}是有界的。

假定{(xk，sk)}是无界的，则存在子序列{(xk，sk)}，使得 limk→∞‖(xk，sk)‖ = ∞。

因为M是半正定矩阵，函数φμ是连续可微的，所以函数 H是连续可微的，所以对每个 μk有lim‖(xk，sk)‖→∞‖H(xk，sk，μk)‖ = ∞ 。

又由引理 2 知:‖H(xk，sk，μk)‖ ≤ βμk。

即存在ε＞0，当k充分大时有:

‖H(xk，sk，μk)‖ ≤ βε。

这就产生了矛盾。所以{(xk，sk)}是有界的。因此序列{ωk}有界。

其次我们证明{(xk，sk)}的任意聚点是SOCCP的解。

由引理 1知序列 {Wk}是收敛的，序列{‖H(ωk)‖}是有界的。由于{ωk}是有界的，则序列{ωk}有收敛的子序列，记为{ωk}。令ω*表示子序列的极限，则

由引理3有‖H(ω*)‖ =0，所以得证。

定理3 (局部超线性收敛)假定M是半正定矩阵，如果所有V∈∂H(ω*)是非奇异的，则{ωk}超线性收敛到ω*。即

其证明类似于文献［5］中的定理5，在此省略证明。

4 数值实验

随机产生一个线性二阶锥互补问题进行数据实验。在整个实验中，取参数 σ =1.0e-4，δ=0.5，μ0=1.0e-4，初始点x0，s0的每个分量均为［-1，1］的随机数，参数，算法的终止准则为 ‖H(x，s，μ)‖ ≤1.0e-7。在实验中，对每组r，n分别用上述算法进行20次实验，I表示平均迭代次数，T表示平均CPU时间，NH表示|xTs|的最大值。

我们做了3组实验，第一组实验:对算法的有效性进行测试。在整个实验中固定ηk=0.1，见表1，从数据结果来看，该算法是有效的，并且所用的CPU时间较短，迭代次数也较少。

表1 算法的数值结果

第二组实验:固定n=100，r=95对算法中ηk的不同取值进行结果比较，见表2。ηk值的变化对算法所用的CPU时间和迭代次数产生很大的影响。当ηk值为0时，即算法为一般的光滑算法，采用非单调因子之后，对结果的精确程度有明显的改进，但对速度的改进程度还依赖ηk的取值。

表2 不同ηk的结果比较

第三组实验:固定n=100，r=95，在实验过程中取ηk为(0，1)区间上的随机数，发现对同样的问题，不同次的实验，算法所需要的迭代次数与时间差别很大，也没有一个规律可寻。

5 结语

本文给出了一个非单调线搜索光滑算法，从算法的3组实验中可以看出，采用非单调线搜索的光滑算法，对于求解线性二阶锥互补问题是有效的，并且精确度也很高。非单调因子ηk的值在算法中起着非常重要的作用，因子ηk取适当的数值，非单调线搜索算法比单调线搜索算法的效果要好，那么因子ηk的取值规则，对算法进一步优化起关键性作用，这也是我们下一步要研究的问题。

［1］Fukushima M，Luo Z Q，Tseng P.Smoothing Functions for Second-order Cone Complementarity Problems［J］.SIAM Journal on Optimization，2002，12:436-460.

［2］Xiang Song Zhang，SanYang Liu，ZhenHua Liu.A Smoothing Method for Second Order Cone Complementarity Problem［J］.Jurnal of Computational and Applied Mathematical，2009，228:83-91.

［3］Huali Zhao，Hongwei Liu.Predictor Corrector Smoothing Newton Method for Solving the Second Order Cone Complementarity［J］.ICICTA，2010，3:927-930.

［4］Hua-li Zhao， Hong-wei Liu.A Predictor-corrector smoothing Newton Method for the Second-order Cone Complementarity［J］.CASON，2010，1:259-262.

［5］Qi L，Sun D，Zhou G.A New Look at Smoothing Newton Methods for Nonlinear Complementarity Problems and Box Constrained Variational Inequalities［J］.Mathematical Programming，2000，87:1-35.