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

2022-08-18迟晓妮刘三阳王博妲

工程数学学报 2022年3期

迟晓妮，刘三阳，王博妲

(1. 桂林电子科技大学数学与计算科学学院广西自动检测技术与仪器重点实验室，桂林 541004;2. 西安电子科技大学数学与统计学院，西安 710071)

0 引言

权互补问题的概念最早由Potra[1]在2012 年提出，是指找到一对属于一个流形与一个锥的交集的向量，使得这对向量的某个代数积等于一个给定的权向量。当权向量为零时，权互补问题退化为互补问题[2]。非零权向量的存在，使得权互补问题的理论和算法都比互补问题复杂。权互补问题在科学、工程和经济等领域中有着广泛的应用，可以建模比互补问题更广泛的一大类均衡问题。Potra[1]指出经济领域的Fisher 市场均衡问题可建模为线性权互补问题，可以用内点方法更有效地求解。由Anstreicher[3]引入的线性规划权中心问题同样也可以转化为斜对称线性权互补问题。Potra[4]给出了充分线性权互补问题的概念，讨论其性质，并提出求解该问题的一种预估校正内点算法。随后，Zhang[5]提出用光滑牛顿算法来求解线性权互补问题，并证明了在适当的条件下算法的局部二次收敛性。Chi 等[6]给出了欧几里得约当代数上线性权互补问题一些解的存在性和唯一性结果。

内点算法是求解权互补问题的有效算法[7—8]之一。Roos[9]提出用全牛顿步不可行内点算法求解线性规划，并证明了算法的收敛性及复杂度。Zhang 和Xu[10]提出了一个无需进行线搜索的可行内点算法来解决线性优化问题，并重新构造了中心路径，算法中采用了修正全牛顿步，且具有多项式复杂度。Mansouri 等人[11]设计了一种求解线性互补问题的改进不可行内点算法。内点算法不仅可以求解线性互补问题[12—13]和线性规划问题[14—16]，还可应用于二阶锥互补问题[17]和二阶锥规划问题[18—20]。Chi 和Liu[21]利用Alizadeh-Haeberly-Overton(AHO)搜索方向，给出了二阶锥规划全局收敛的预估-校正不可行内点算法，并给出了适当假设下的复杂度。Zangiabadi 等[22]提出了求解对称锥线性互补问题的一种新的基于参数核函数的大步校正内点算法。Bai[23]给出求解锥优化的基于核函数的内点算法。Liu 等人[24]提出了求解对称锥规划的一种基于宽邻域的新不可行内点算法，并给出该宽邻域不可行内点方法的迭代复杂度界，与现有的短步路径跟踪算法的最好复杂度界一致。随后，基于核函数[25—28]或者宽邻域[29—30]的相关内点算法被提出并应用于求解优化问题。这些线性规划和锥优化的内点算法及相关理论[31]的研究成果，将有助于进一步研究权互补问题的内点算法。

1 线性权互补问题

引理1 原问题(1)可行当且仅当对任意0＜ν ≤1，其扰动问题(2)满足IPC。

假设原问题(1)存在可行点，由引理1 知，对任意0＜ν ≤1， 0＜t ≤1，扰动问题(2)存在严格可行点。把该点记作(x(ν，t)，y(ν，t)，s(ν，t))，定义为扰动问题(2)的t-中心，所有t-中心的集合称为扰动问题(2)的中心路径。当ν，t →0 时，(x(ν，t)，y(ν，t)，s(ν，t))收敛到线性权互补问题(1)的解(x*，y*，s*)。

通过求解以下方程组可得牛顿搜索方向(Δfx，Δfy，Δfs)：

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

本节给出线性权互补问题(1)的改进不可行内点算法的基本思想和具体步骤。本算法通过对参数τ、θ的选取，使得每步主迭代都满足δ(x，s;t)≤τ，从而算法可行。算法的每步主迭代分为一个可行步和几个中心步。可行步搜索方向可通过求解方程组(3)得到，中心步的搜索方向可通过求解以下方程组得出

则转步骤6，否则转步骤2；

步骤2 解方程组(3)得可行步之后迭代点(x，y，s):=(x，y，s)+(Δfx，Δfy，Δfs)；

步骤3 更新参数t:=(1－θ)t，ν:=(1－θ)ν；

步骤4 如果δ(x，s;t)＞τ，则转到步骤5，否则转步骤1；

步骤5 解方程组(4)，可得中心步之后迭代点(x，y，s):=(x，y，s)+(Δx，Δy，Δs)，转步骤4；

步骤6 如果δ(x，s;t)≤ε，则算法停止，否则转步骤7；

步骤7 解方程组(4)，可得中心步之后迭代点(x，y，s):=(x，y，s)+(Δx，Δy，Δs)，转步骤6。

3 收敛性分析

4 复杂度分析

5 数值算例

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

首先，考虑形如问题(1)的线性权互补问题算例如下

为算法1 的终止条件。图1 至图4 分别表示m=n= 50，100，150，200 的‖rb‖(记为残差一)，‖rc‖(记为残差二)，‖xs－w‖(记为残差三)和邻近测度δ(v)随着t →0 的变化，其中参数t ∈(0，1]。容易看出，‖rb‖、‖rc‖、‖w(t)－w‖和δ(v)的值都随着t减小而有不同程度的减小，且最终都趋向于0。