线性权互补问题的一种改进全牛顿步可行内点算法

宁小玲， 王博妲， 迟晓妮,2,3

(1.桂林电子科技大学 数学与计算科学学院，广西 桂林 541004；2. 桂林电子科技大学 广西自动检测技术与仪器重点实验室,广西 桂林 541004；3. 桂林电子科技大学 广西密码学与信息安全重点实验室, 广西 桂林 541004)

权互补问题是一类相对较新的优化问题，它是标准互补问题的推广。2012年，Potra[1]提出权互补模型可以更高效求解经济学中的一些均衡问题。例如，经济领域的Fisher市场均衡问题可以转化为线性权互补模型求解，比通过建立非线性互补模型求解更有效。2008年，Ye[2]提出了一种求解线性权互补问题特定实例的数值方法。随后，Anstreicher[3]改进了Ye求解Fisher问题的计算复杂度。Potra[1]提出的二次规划与权中心问题可以退化为单调线性权互补问题。2016年，Potra[4]又给出了充分线性权互补问题的一些基本理论。Zhang[5]运用光滑牛顿算法求解了线性权互补问题。2019年，Chi等[6]给出了欧几里德约当代数上线性权互补问题的一些解的存在性和唯一性结果。由于非零权向量的存在，使得权互补问题的理论和算法都比互补问题复杂，因而目前关于权互补问题的研究尚不多见。

内点算法是求解线性优化问题的有效算法。2003年，Darvay[7]设计了线性规划的一种全牛顿步原对偶路径跟踪内点算法。2006年，Roos[8]提出线性优化的原对偶不可行内点算法，并证明了算法的收敛性及多项式时间复杂度。2011年，Zhang等[9]提出一种修正牛顿步可行内点算法来求解线性优化问题。2015年，Achache等[10]给出了单调线性互补问题的全牛顿步加权原对偶内点算法。2015年，Mansouri等[11]提出求解线性优化的改进不可行内点算法。

基于线性优化的内点算法，给出求解线性权互补问题的改进全牛顿步可行内点算法。通过扰动线性权互补问题，构造新的等价变换，分析算法的可行性和复杂度，并给出数值算例验证算法的有效性。

1 权互补问题

权互补问题是找到一向量对(x,y,s)∈Rn×Rm×Rn，满足

f(x,y,s)=0，x≥0，s≥0，xs=ω,

其中：f:Rn×Rm×Rn→Rn×Rm为连续可微函数；xs为向量x和s的Hadamard积(即对应分量乘积)；ω≥0为给定的非负权向量。

考虑如下线性权互补问题，找到一向量对(x,y,s)∈Rn×Rm×Rn，使得

(1)

扰动线性权互补问题(1)得中心路径

(2)

若式(1)有可行解(x,y,s)，且x>0，s>0，则称式(1)满足内点条件(IPC)[13]，∀t∈[0,1],记式(2)的解为(x(t),y(t),s(t))，称为原问题(1)的t-中心解。这些解的集合称为原问题(1)的中心路径。当t→0时，(x(t),y(t),s(t))收敛到一个极限点(x*,y*,s*)，即线性权互补问题(1)的解。

设(x,y,s)为当前可行点，则新的迭代点

(3)

满足

(4)

由式(2)、(4)知，可求解如下方程组得搜索方向(Δx,Δy,Δs)，

(5)

因为矩阵A行满秩，且x>0，s>0，易证上述方程组中的系数矩阵非奇异。因此，式(5)可定义唯一的搜索方向(Δx,Δy,Δs)，且

(Δx)TΔs=0。

(6)

令

(7)

由式(6)和dx、ds的定义得

dxTds=0。

定义邻近测度

2 改进全牛顿步可行内点算法

算法1线性权互补问题的全牛顿步可行内点算法。

1)若‖xs-ω‖<ε，则算法终止；否则，转步骤2。

3 可行性分析

引理1对任意k≥1，有

其中e=(1，1，…，1)。

ω(tk)=(1-(1-θ)kt0)ω+

(1-θ)kt0κ≥min(ω,κ)e,

所以

引理2[13]若(x,y,s)是可行点，则

引理3若(x,y,s)是可行点，x>0,s>0，且

则新迭代点(x+,y+,s+)严格可行。

证明令α∈[0,1]，定义

xα=x+αΔx，sα=s+αΔs。

由dx,ds的定义和式(7)得

xαsα=xs+α(sΔx+xΔs)+α2ΔxΔs=

t[v2+αv(dx+ds)+α2dxds]=

α2[min(ω,κ)-‖dxds‖∞]≥

α2[min(ω,κ)-δ(v,t)2]>0。

此时，则对任意α∈[0,1]有xαsα>0。

由于xα,sα是关于α的线性函数，∀α∈[0,1]有xαsα>0，且x>0，s>0，则xα>0，sα>0。因此x+=x1>0，s+=s1>0。

(8)

故

根据引理1和引理2可得

下述引理将给出t更新之后迭代点的邻近测度的上界。

证明由δ(v+,t+)的定义及式(8)得

则由引理1、引理2和引理4得

只需证

4 复杂度分析

定理1若线性权互补问题(1)的可行初始点为(x0,y0,s0)，θ≤(1-3η/2)/(1-η)，其中η∈(0,2/3)，则算法至少经过

次迭代后生成的点(x,y,s)满足‖xs-ω‖<ε，其中κ=x0s0。

证明根据式(5)、引理2和引理5得

‖x+s+-ω‖=‖ω(t+)+ΔxΔs-ω‖≤

‖ω(t+)-ω‖+‖ΔxΔs‖=

t+‖ω-κ‖+t‖dxds‖≤

因为t0=1，所以在第k次迭代当

时，有‖xksk-ω‖<ε。即需满足不等式

(k-1)log(1-θ)

次迭代后，可得到线性权互补问题(1)的ε-近似最优解。

5 数值算例

为了检验算法1的有效性，运用MATLAB(R2016b)编程，在Intel(R) Core(TM)i5-8250U CPU @1.60 GHz 1.80 GHz 8 GiB内存，64位Windows 10操作系统的计算机上进行数值实验。

首先，生成行满秩矩阵A∈Rm×n和向量b、c、ω以及可行初始点x0、y0、s0，记β=maxω/minω，取

其中η∈(0,2/3)。因此，θ可取(0,1)区间任意实数，算例中精度参数取ε=10-5，算法的迭代次数(Iter)和运行时间(time)均选取200个同规模不同问题运行结果的平均值。

表1、表2表明算法1所需要的迭代次数基本不受问题规模的影响，但运行时间随着问题规模的增大而增大。对比表2和表3可知，β值对算法运行的时间和迭代次数影响都不大，且随着θ的增大，β值对算法运行的时间和迭代次数影响越来越小。

表1 β<20时算法求解不同规模线性权互补问题的数值结果

表2 β<2时算法求解不同规模线性权互补问题的数值结果

表3 算法1选取不同θ值求解m=n=300线性权互补问题和线性互补问题的数值结果

6 结束语

基于全牛顿步搜索方向，设计改进可行内点算法求解线性权互补问题(1)，在适当的条件下对算法的可行性进行分析，该算法只需多项式时间迭代复杂度即可得到原问题的近似最优解，并给出随机生成的权互补问题的数值算例。数值实验结果表明，算法是有效的。