正弦余弦算法求解线性互补问题的最小范数解

雍龙泉,贾 伟,黎延海

(陕西理工大学 数学与计算机科学学院,陕西 汉中 723001)

线性互补问题是应用数学、计算数学与运筹学相互交叉的一个研究方向，在经济均衡理论、双矩阵对策、接触力学、交通流平衡等领域具有广泛的应用[1-3].线性互补问题就是求一个向量x∈n，使得

x≥0,Mx+q≥0,xT(Mx+q)=0,

其中：M∈n×n,q∈n.

线性互补问题简记为LCP(M,q)或LCP(linear complementary problem).针对存在唯一解的LCP，研究的重点是探寻有效的求解算法.目前已有的方法有：各类内点法[4-9]、矩阵分裂迭代法[10-13]、混合整数线性规划方法[14-15]等，其中智能优化算法、神经网络方法[16-17]被用于求解各类互补问题.近年来，随机线性互补、对称锥互补、参数线性互补、张量互补、垂直线性互补[18-24]等成为研究热点.

针对存在多个解的LCP，在众多解中寻找稀疏解、最小一范数解已成为当前的一个研究热点[25-27].线性互补问题的稀疏解即求解如下零范数优化问题

(1)

其中：‖x‖0表示向量x中非零元素个数.

零范数优化通常的做法是采用凸松弛技巧[28-33]，把稀疏解问题L0(x)转化为如下L1(x)范数优化

(2)

L1(x)问题是一个凸优化，在一定条件下，L1(x)的解恰好就是L0(x)的稀疏解.

问题(2)可以采用约束优化算法、交替方向法[29,34]等.论文采用一种仿物理现象(正弦波与余弦波)的优化算法——正弦余弦算法(sine cosine algorithm,简称SCA)求解线性互补问题尽可能多的解，进而在其中选取范数最小的解.

1 解的存在性与问题的转化

定义[1]矩阵M∈n×n，对∀x∈n，都有xTMx≥0，则称矩阵M∈n×n为半正定矩阵；对∀x∈n,x≠0，都有xTMx>0，则称M为正定矩阵.

在线性互补问题研究中，矩阵的正定性起着重要的作用，这里的半正定矩阵与正定矩阵无对称性要求.当矩阵M是半正定矩阵时，称LCP为单调线性互补问题.矩阵M对称时，特征值全大于零，则矩阵M是正定矩阵.需要注意的是，非对称实矩阵的特征值全大于零时不一定是正定矩阵[35].下面给出线性互补问题解存在的2个充分条件.

定理[1](i)设矩阵M∈n×n是一正定矩阵，则对于任意q∈n，LCP有唯一解.

(ii)设矩阵M∈n×n是一半正定矩阵，对于任意q∈n，若LCP是可行的，则其必有解，且解集为凸集.

利用文献[36]中的结论，任意的LCP都等价于如下绝对值方程

(M+I)x+q=|(M-I)x+q|，

于是，论文定义智能算法的适应值函数

(3)

作为优化目标函数，当且仅当f(x)=0时，则找到LCP的解.通过多次执行算法，就有可能找到LCP尽可能多的解，再从中选取范数最小的解.所以，问题的核心还是求解(3).

2 正弦余弦算法

SCA是一种新型仿物理现象(正弦波与余弦波)的优化算法[37]，具有结构清晰、容易实现等优点.下面给出SCA的步骤:

SCA算法参数初始化: 设定种群规模N，优化问题变量个数D，转换参数a及Tmax；

t=1；在搜索空间中随机生成N个个体作为初始种群，计算个体的适应值并记录当前最优个体位置P(t)；

while(t

fori= 1 toNdo

forj= 1 toDdo

r1=a-at/Tmax；r2∈U[0,2π],r3∈U[0,2],r4∈U[0,1]；

ifr4<0.5

(4)

else

(5)

end

end

end

进行越界处理；

更新种群的最优位置P(t)；

t=t+1；

end.

SCA算法利用正弦波与余弦波的周期震荡实现搜索过程[37-38].图1给出了a=2、Tmax=100与a=2、Tmax=200时，r1sin(r2)与r1cos(r2)的图像.

图1 r1sin(r2)与r1cos(r2)的图像

当r1>1时，r1sin(r2)与r1cos(r2)才有可能大于1或者小于-1；当r1≤1时，r1sin(r2)与r1cos(r2)值必介于-1和1之间.因此当|r1sin(r2)|>1或者|r1cos(r2)|>1时，算法进行全局搜索；当|r1sin(r2)|≤1或者|r1cos(r2)|≤1时，算法进行局部开发.如图2所示.

图2 r1=2、r3=1时，r1sin(r2)和r1cos(r2)的波动性及算法搜索策略

在SCA算法中，参数r1较为关键，控制算法从全局搜索到局部开发的转换.更多的SCA算法见文献[39-41].下面应用SCA算法求解(3).

3 数值算例

该节给出几个LCP，算例(i)～(iii)的共同特点是矩阵M半正定，(iv)的特点是M非半正定,4个LCP解的集合均为非空凸集.通过将LCP转化为问题(3)，采用SCA算法求解.设置参数N=30,a=2,Tmax=1 000.算例(i)搜索空间为0≤xi≤2，(ii)搜索空间为0≤xi≤5，(iii)，(iv)搜索空间为0≤xi≤1,i=1,2,…,n.为消除随机数对算法的影响，算法运行10次.

(i)考虑线性互补问题

其中：对称矩阵M的特征值为λ1=0,λ2=2,λ3=2，因此M是半正定矩阵.

文献[25]中指出该问题具有无穷解x*=(λ+1,0,λ)T,λ≥0.采用SCA算法求解，得到最小范数解为x*=(1,0,0)T.事实上，x*=(1,0,0)T也是其稀疏解.

(ii)考虑线性互补问题

其中：对称矩阵M的特征值为λ1=0,λ2=0,λ3=0,λ3=4，因此M是半正定矩阵.

文献[25]指出该问题具有无穷解x*=(λ,0,0,5-λ,0)T,0≤λ≤5.采用SCA算法求解，可以获得2个最小范数解同时也是稀疏解为x*=(0,0,0,5,0)T,(5,0,0,0,0)T.

(iii)考虑线性互补问题

其中：对称矩阵M的特征值为λ1=0,λ2=0,λ3=3，因此M是半正定矩阵.

下面用定义来判别对称矩阵M的正定性.对于∀x, 这里x=(x1,x2,x3)T，由xTMx=(x1+x1+x3)2≥0，知矩阵M是半正定矩阵.文献[26]中指出该问题具有无穷解

x*=(λ1,λ2,λ3)T,λ1+λ2+λ3=1,λ1≥0,λ2≥0,λ3≥0.

采用SCA算法求解，可以获得3个最小范数解同时也是稀疏解为x*=(1,0,0)T,(0,1,0)T,(0,0,1)T.

(iv)考虑线性互补问题

对于∀x=(x1,x2,x3,x4,x5)T，由于

xTMx=3x1x3+5x1x4+3x1x5+3x2x3+3x2x4+5x2x5，

4 结束语

最小范数解与稀疏解具有一定的内在关系，但是二者是否等价难以判断.目前研究结果证明了在有限等距条件下最小范数解和稀疏解的等价性.因此通过研究最小范数解，可以为研究稀疏解提供一些近似的结果.