二阶锥权互补问题的非精确非内点连续化算法

曾 荣

(广东东软学院 基础教学院， 广东 佛山528000)

1 引 言

考虑二阶锥权互补问题(wSOCCP)：给定权向量w∈，求向量x∈n使得

x∈，s=F(x)∈，x∘s=w，

(1)

近年来，权互补问题的理论和算法研究已取得了一些成果[1-2].权互补问题可以被应用于经济学中，如Fisher市场均衡问题，二次规划和权中心问题等都可以被转化为权互补问题进行求解.基于这些研究工作，二阶锥上的权互补问题的求解方法也陆续受到关注[3-4].

目前，许多算法已被用于求解各类优化问题，如：共轭梯度法[5]，内点算法[1]，非内点连续化算法[6-7]等.其中，内点算法最早被用于权互补问题的求解[1]，但该算法要求初始点严格可行，因此在求解问题时要找到这样的初始点较为困难.非内点连续化算法由于具有较好的收敛性和数值结果，近年来发展迅速[6-7].非内点连续化算法不同于内点算法，它能选择任意点为初始点，且迭代过程中不要求中间迭代点为可行内点，这些特点使得非内点连续化算法比内点算法更加便于进行数值计算.本文运用非内点连续化算法求解二阶锥权互补问题，并引入了非精确牛顿法.在适当假设下，证明了该算法是全局收敛与局部二阶收敛的.最后通过数值实验表明了算法的有效性.

2 预备知识

对任意x=(x0，x1)，s=(s0，s1)∈×n-1，与二阶锥相伴的欧几里得约当代数定义为

x∘s=(xTs，x0s1+s0x1)，

易知Lxs=x∘s.若x∈int，则Lx可逆.

对任意x=(x0，x1)∈×n-1，令λi和u(i)(i=1，2)分别为x的谱值和对应的谱向量，则称x=λ1u(1)+λ2u(2)为x的谱分解，其中

ω∈n-1是‖ω‖=1的任意非零向量.由谱分解定义易知

(ii)x∈⟺ 0≤λ1≤λ2，x∈int⟺ 0<λ1≤λ2；

3 算法设计

本文考虑含参数τ∈(0，4)的wSOCCP函数φτ，μ(x，s)∶n×n→n：

(2)

其中w∈为权向量.类似文献[2]中命题1易得φτ，0(x，s)=0⟺x∈，s∈，x∘s=w.

定理1令φτ，μ(x，s)由(2)定义，则有

(i) 对任意μ∈，φτ，μ(x，s)在任意(x，s)∈n×n处全局Lipschitz连续且强半光滑，若μ>0，令则φτ，μ(x，s)连续可微，且对x和s的偏导数为

(3)

(ii)对任意(x，s)∈n×n有则φτ，μ(x，s)为φτ，0(x，s)的一个光滑函数.

证因为

由(2)和文献[8]中定理3.2易得到(i)和(ii)成立.

对任意x=(x0，x1)，s=(s0，s1)∈×n-1和w=(w0，w1)∈，由谱分解定义有

λ(x，s)=min(λ1，λ2).

(4)

引理2令φτ，μ(x，s)由(2)定义，则对任意μ1，μ2>0和(x，s)∈n×n，有

当λ(x，s)>0时

‖φτ，μ1(x，s)-φτ，μ2(x，s)‖

令z∶=(x，s)∈n×n，结合(2)定义

(5)

易知Hτ，0(z)=0⟺ (x，s)为(1)的解.

定理3令w∈，Hτ，μ(z)由(5)定义，则结合(3)有以下结论成立：

(i)Hτ，μ(z)全局Lipschitz连续且强半光滑，若μ>0，对任意z∶=(x，s)∈n×n，Hτ，μ(z)连续可微其雅可比为

(6)

(ii) 若F(x)连续可微且单调，则当μ>0时，H′τ，μ(z)可逆.

证由定理1易知(i)成立.下面证明(ii)成立.对任意μ>0，令Δz=(Δx，Δs)∈n×n为H′τ，μ(z)零空间中任意向量，则只需证明Δz=0.由(6)有

F′(x)Δx-Δs=0，

(7)

Bτ，μΔx+Dτ，μΔs=0.

(8)

因为F(x)单调，结合(7)知

〈Δx，Δs〉=〈Δx，F′(x)Δx〉≥0.

(9)

将(8)两边同时乘Lc有

(10)

而由c定义知

则根据文献[9]中命题3.4知LcBτ，μ和LcDτ，μ可逆，将(10)两侧同乘ΔxT[LcDτ，μ]-1有

ΔxT[LcDτ，μ]-1[LcBτ，μ]Δx+ΔxTΔs=0.

结合(9)得到

ΔxT[LcDτ，μ]-1[LcBτ，μ]Δx≤0.

(11)

又因为

算法1(非精确非内点连续化算法)

步0 选取δ，σ，η∈(0，1)，γ∈(0.5，1)和μ0>0，令z0=(x0，s0)∈n×n为任意初始点，选取β使得且‖Hτ，μ0(z0)‖≤βμ0.置k∶=0.

步1 若μk=0，停止.

步2 若‖Hτ，μk(zk)‖=0，则zk+1∶=zk且θk∶=1，转步4；否则，令Δzk∶=(Δxk，Δsk)∈n×n为下列方程的解

H′τ，μk(zk)Δzk=-Hτ，μk(zk)+rk，

(12)

其中‖rk‖≤η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}.

步3 令θk=max{1，δ，δ2，…}使得

‖Hτ，μk(zk+θkΔzk)‖≤[1-σ(1-η)θk]‖Hτ，μk(zk)‖.

(13)

置zk+1∶=zk+θkΔzk.

步4 置

(14)

令tk=min{1，γ，γ2，…}使得

(15)

注 算法可以取任意(μ0，x0，s0)∈++×n×n为初始点，且

定理4若函数F(x)是连续可微且单调的，则算法1适定.

证由算法1知μk>0，而F(x)连续可微且单调，则由定理3(ii)知H′τ，μk(zk)可逆.故步2适定.

接着证步3适定.对任意θ∈(0，1]，令

g(θ)∶=Hτ，μk(zk+θΔzk)-Hτ，μk(zk)-θH′τ，μk(zk)Δzk.

(16)

因为μk>0，由定理3(i)知Hτ，μk(zk)在zk处连续可微，故由(16)有‖g(θ)‖=o(θ).结合(12)，(16)和

‖rk‖≤η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}≤η‖Hτ，μk(zk)‖，

对任意θ∈(0，1]有

‖Hτ，μk(zk+θΔzk)‖≤‖Hτ，μk(zk)+θH′τ，μk(zk)Δzk‖+‖g(θ)‖

≤‖(1-θ)Hτ，μk(zk)+θrk‖+‖g(θ)‖

≤(1-θ)‖Hτ，μk(zk)‖+θη‖Hτ，μk(zk)‖+o(θ)

=[1-(1-η)θ]‖Hτ，μk(zk)‖+o(θ).

最后证步4适定.当Hτ，μk(zk)≠0时，由(13)-(15)和引理2知

(17)

当Hτ，μk(zk)=0时，zk+1=zk，故Hτ，μk(zk+1)=Hτ，μk(zk)=0.由(17)和[1-σ(1-η)θk]βμk≥0知

由算法1易得到下面的引理成立.此处省略不证.

引理5设函数F(x)是连续可微且单调的，则

(i) 对任意k≥0，序列{μk}单调递减且μk>0；

(ii) 对任意k≥0有‖Hτ，μk(zk)‖≤βμk.

4 收敛性分析

本节给出算法1的全局收敛性和局部二阶收敛性分析.

‖Hτ，μk(zk+kΔzk)‖>[1-σ(1-η)k]‖Hτ，μk(zk)‖.

又根据(12)可得

‖Hτ，μk(zk+kΔzk)‖=‖Hτ，μk(zk)+kH′τ，μk(zk)Δzk+g(k)‖=‖(1-k)Hτ，μk(zk)+krk+g(k)‖

≤(1-k)‖Hτ，μk(zk)‖+kη‖Hτ，μk(zk)‖+o(k)

=[1-(1-η)k]‖Hτ，μk(zk)‖+o(k).

(18)

因此

[1-σ(1-η)k]‖Hτ，μk(zk)‖≤[1-(1-η)k]‖Hτ，μk(zk)‖+o(k).

(19)

‖Hτ，μ*(z*)‖=0.

(20)

另一方面，根据步4知‖Hτ，γμk+1(zk+1)‖>βγμk+1.令k→∞有

‖Hτ，γμ*(z*)‖≥βγμ*.

(21)

这与(20)矛盾.因此得到μ*=0.

最后证z*为Hτ，0(z)=0的解.由引理5(ii)知‖Hτ，μk(zk)‖≤βμk，当k→∞则有‖Hτ，0(z*)‖=‖Hτ，μ*(z*)‖≤βμ*，而μ*=0，故Hτ，0(z*)=0.定理得证.

证对充分大的k，考虑下面两种情形：

故存在一个较小的ε>0，使得对充分大的k有λ(xk+1，sk+1)≥λ(x*，s*)-ε>0.由引理2得

结合步4知

(ii) 若Hτ，μk(zk)≠0，类似(i)可以得到

(22)

下面证明对充分大的k有zk+1=zk+Δzk成立.由于对任意V∈∂Hτ，μ*(z*)非奇异，则由文献[10]中命题3.1，对充分大的k有‖H′τ，μk(zk)-1‖=O(1).因此结合步2易知

‖Δzk‖=‖H′τ，μk(zk)-1(-Hτ，μk(zk)+rk)‖≤(1+η)‖H′τ，μk(zk)-1‖‖Hτ，μk(zk)‖

=O(‖Hτ，μk(zk)‖).

(23)

另外，根据定理3(i)得到Hτ，μk(·)在点zk+Δzk处强半光滑，即对充分大的k，

‖Hτ，μk(zk+Δzk)-Hτ，μk(zk)-H′τ，μk(zk)Δzk‖=O(‖Δzk‖2).

(24)

故由(12)，(23)和(24)，对充分大的k有

‖Hτ，μk(zk+Δzk)‖≤‖Hτ，μk(zk+Δzk)-Hτ，μk(zk)-H′τ，μk(zk)Δzk‖+‖rk‖

≤O(‖Δzk‖2)+η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}

≤O(‖Hτ，μk(zk)‖2)+η‖Hτ，μk(zk)‖2=O(‖Hτ，μk(zk)‖2).

(25)

5 数值实验

本节给出一些数值实验验证算法1的有效性.所有测试用Matlab(2018a)编程在Intel(R) Core(TM) i5-7300U CPU @2.60GHz 2.71 GHz 8GB内存，Windows10专业版操作系统上实现.测试中随机生成向量q∈n和矩阵D∈n×n，令M=DTD.给定权向量w=(1，0，…，0)T∈，求解线性wSOCCP：

x∈，s=Mx+q∈，x∘s=w.

选择x0=s0=(1，1，…，1)T∈n作为初始点.算法1中参数取值为

另外，当μ≤10-6时算法1停止迭代.表1给出了取不同参数τ时，算法1求解线性wSOCCP所需的迭代次数和所占的CPU时间.其中Iter和cpu分别表示针对每个n运行10次的平均迭代次数和平均CPU时间.

表1 运用算法1求解不同规模的wSOCCP的数值结果

表1表明算法1求解规模较大的wSOCCP只需较少的迭代次数和CPU时间.取不同参数τ=3.8，τ=3.3和τ=2.6时，对迭代次数的影响较小.

6 结 论

运用非精确非内点连续化算法求解二阶锥权互补问题.算法在每次迭代过程中最多求解一个方程组.基于单调假设，证明了算法是全局与局部二阶收敛的.从数值实验结果可知，算法求解不同规模的二阶锥权互补问题时，只需要较少的迭代次数，这表明了算法的良好性能.

致谢作者非常感谢相关文献对本文的启发以及审稿专家提出的宝贵意见.