线性权互补问题基于核函数的全牛顿步可行内点算法

张睿婕， 迟晓妮，2，3， 刘文丽

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

权互补问题最先由Potra[1]提出，是一类新的优化问题，且互补问题[2]是该类问题的一种特殊形式。互补问题与不动点问题、变分不等式及数学规划等有着密切联系[3]，在经济学和工程中有着广泛应用。科学和工程领域一大类问题可以转化为权互补问题[4]，甚至相比于建立互补模型求解问题，利用权互补模型求解在某些情况下会得到一个更高效的数值解。Roos等[5]首次提出求解线性规划的对数障碍核函数内点算法和全牛顿步内点算法。随后，Peng等[6]和Bai等[7]相继设计了新的核函数，并基于新核函数提出求解线性规划的内点算法。Potra等[8]设计了一种预估-校正内点算法用于求解充分权互补问题。宁小玲等[9]提出了求解线性权互补问题的一种改进全牛顿步可行内点算法。

鉴于此，将线性互补问题的可行内点算法推广到权互补问题，运用文献[10]中核函数，得到新的牛顿搜索方向，并基于全牛顿步给出求解非负象限上线性权互补问题的可行内点算法。定义了迭代点到中心路径的邻近测度，证明了该算法的可行性及迭代复杂度。数值算例结果表明了算法的有效性。

1 算法

考虑Rn上的线性权互补问题(WCP)[1]：寻找向量对(x,y,s)∈Rn×Rm×Rn，使得

(1)

其中A∈Rm×n,b∈Rm,c∈Rn,ω≥0。定义方程组(1)的严格可行域：

F0=

(2)

其中，

ω(t)=tx0s0+(1-t)ω,t∈[0,1]。

初始点(x0,y0,s0)∈F0。假定A为行满秩矩阵，即R(A)=m。若内点条件(IPC)[5]成立，即(x,y,s)∈F0,则对任意参数00}称为方程组(1)的中心路径。当t→0时，ω(t)→ω,可得方程组(1)的最优解。

求解如下方程组，得牛顿搜索方向(Δx,Δy,Δs)：

(3)

定义

(4)

由式(4)，方程组(3)可化为

(5)

方程组(5)中υ-1-υ为对数障碍函数

考虑Zhang等[10]提出的局部核函数φ(t)：=(1-t)2,用dx+ds=2(e-υ)替换方程组(5)中第3式，得

(6)

定义邻近测度：

(7)

引理1[5]若u与v正交，则

‖e-υ‖2=δ(υ)2。

(8)

同理，可得

(9)

引理2[7]对任意υ∈Rn,有

1-δ(υ)≤υi≤1+δ(υ),i=1,2,…,n。

选取适当参数θ及任意初始点x0,s0>0,y0=0。令ω(t0)=x0s0,其中t0=1。显然δ(x0,s0,ω(t0))=0。求解方程组(6)，并结合式(4)可得牛顿搜索方向(Δx,Δy,Δs),其中t+=(1-θ)t,θ∈(0,1)。令新迭代点

x+：=x+Δx,y+：=y+Δy,s+：=s+Δs

(10)

满足内点条件，且

当‖xs-ω‖≤ε时，算法迭代终止。

算法1求解线性WCP基于核函数的全牛顿步可行内点算法。

1)选择参数t0=1,ε>0,初始点(x0,y0,s0)∈F0，y0=0，且ω(t0)=x0s0。置k：=0。

2)当‖xs-ω‖≤ε算法终止，否则转步骤3)。

3)求解方程组(6)，并结合式(4)，得搜索方向(Δx,Δy,Δs)。令

x：=x+Δx，y:=y+Δy,s:=s+Δs，

t：=(1-θ)t，ω(t)=tx0s0+(1-t)ω，θ∈(0,1)。

置k：=k+1，转步骤2)。

2 算法分析

证明令α∈[0,1],记

x(α)=x+αΔx,y(α)=y+αΔy,s(α)=s+αΔs。

由式(4)和方程组(6)得

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

ω(t)[υ2+2α(υ-υ2)+α2dxds]=

ω(t)[(1-α)υ2+α(2υ-υ2)+α2dxds]。

(11)

又由式(8)和引理2得,

min{2υ-υ2+αdxds}≥min(2υ-υ2)-

‖dxds‖∞≥2(1+δ(υ))-

(1+δ(υ))2-‖dxds‖∞≥1-2δ(υ)2。

(12)

因为ω(t)>0,(1-α)υ2>0,所以由式(11)、(12)知,若

(13)

则x(α)s(α)>0。

由于x(0)=x>0,s(0)=s>0,且x(α),s(α)与α呈线性关系，对α∈[0,1]，有x(α)>0，s(α)>0，相应地，x(1)>0，s(1)>0。证毕。

引理4令

证明由式(7)、(9)、(11)得,

‖e-(2υ-υ2)-dxds‖≤

(14)

引理5令

证明由式(9)，(11)和引理2得

‖(υ+)2‖=‖2υ-υ2+dxds‖≤‖e‖+

引理6令

则

‖e-(υ+)2‖≤‖e-(υ+)2‖+

证明因为ω(t+)=ω(t)+θt(ω-x0s0)，所以

(15)

由式(15)和引理5得,

‖e-(υ+)2‖≤‖e-(υ+)2‖+

引理7令δ(υ+)：=‖e-υ+‖，则

证明由引理4、6得,

(16)

引理8令

证明由引理7得

(17)

(18)

设

(19)

其中t+=(1-θ)t,θ∈(0,1)。化简式(19)得

因此，令

3 复杂度分析

由于初始迭代点满足

选取

(20)

‖x+s+-ω‖≤

证明由式(11)和引理4得，

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

‖ω(t)((υ+)2-e)‖+t‖x0s0-ω‖≤

‖x+s+-ω‖≤

引理10若线性WCP(1)存在最优解，则算法1至多经过

次迭代得到WCP(1)的ε近似解。

证明因为

‖ω(t)‖∞≤max{max(x0s0),max(ω)},

所以由引理9可得,

由式(20)可知，

故迭代次数的上界为

4 数值算例

运用MATLAB R2016b编程检验算法1的有效性，在Intel(R) Core i5 CPU 2.3 GHz 8.0 GiB内存，IOS操作系统的计算机上进行数值实验。随机生成5个不同规模的WCP，对每种规模产生10个问题进行求解。

首先选取任意初始点(x0,y0,s0),权向量ω>0,按照式(20)选择参数θ，K。在算法1中令t0=1,ε=10-5。随机生成行满秩矩阵A∈Rm×n。令b=Ax0,c=ATy0+s0,即初始点满足内点条件。算法的终止条件为‖xs-ω‖≤ε,记Gap=‖xs-ω‖。表1～3为K值上界的选取影响算法1求解不同规模WCP的数值结果，表中数据均为求解不同规模的WCP10次结果的平均值，其中Iter为平均迭代次数，Time为平均运行时间。从表1～3可看出，在K值上界确定的情况下，运行时间和迭代次数受m和n的影响。

表1 K≤4时求解不同规模WCP的数值结果

表2 K≤2时求解不同规模WCP的数值结果

表3 K≤0.5时求解不同规模WCP的数值结果

例1考虑R4上的线性WCP方程组(1)，其中：

取初始点

x0=(1,1,3,2)T,y0=(0,0,0)T,

s0=(2,1,2,1)T,t0=1。

用算法1进行求解该问题，迭代95次后得到最优解

x*=(1.063,0.619,2.619,1.873)T,
y*=(0.242,-0.855,-0.894)T,
s*=(2.821,1.613,1.145,2.135)T。

图1为迭代过程中邻近测度及Gap的值。由图1可知，随着t从1减小至0，Gap逐渐减小并趋于0，且每步迭代邻近测度都小于2t/5，保障了每一步迭代点的可行性。

图1 迭代过程中邻近测度及Gap的值

5 结束语

基于核函数，将线性优化的全牛顿步可行内点算法推广至线性权互补问题。分析了算法的可行性，并证明了该算法具有目前线性优化最好的多项式时间迭代复杂度。数值实验表明了该算法的有效性。设计基于核函数的全牛顿不可行内点算法求解线性权互补问题是进一步的研究方向。