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

2021-09-01曾荣

大学数学 2021年4期

关键词：内点易知二阶

曾荣

(广东东软学院基础教学院，广东佛山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中参数取值为