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

2022-01-25雍龙泉黎延海

安徽大学学报（自然科学版） 2022年1期

关键词：范数余弦算例

雍龙泉,贾伟,黎延海

(陕西理工大学数学与计算机科学学院,陕西汉中 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

进行越界处理；

更新种群的最优位置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)的图像

图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)考虑线性互补问题