数学物理学报, 2026, 46(3): 1246-1254

一类垂直线性互补问题的模系矩阵分裂迭代法

温淑鸿,1, 柯艺芬,2,*, 肖丽芬,2, 陈熙文,2

1 福州大学至诚学院数据科学与统计系 福州 350002

2 福建师范大学数学与统计学院 福州 350117

A Modulus-Based Matrix Splitting Iterative Method for a Class of Vertical Linear Complementarity Problems

Wen Shuhong,1, Ke Yifen,2,*, Xiao Lifen,2, Chen Xiwen,2

1 Department of Data Science and Statistics, Fuzhou University Zhicheng College, Fuzhou 350002

2 School of Mathematics and Statistics, Fujian Normal University, Fuzhou 35011

通讯作者: 柯艺芬, E-mail:keyifen@fjnu.edu.cn

收稿日期: 2025-01-4   修回日期: 2025-10-21  

基金资助: 国家自然科学基金(12371378)

Received: 2025-01-4   Revised: 2025-10-21  

Fund supported: NSFC(12371378)

作者简介 About authors

温淑鸿,E-mail:32642217@qq.com;

肖丽芬,E-mail:1943488318@qq.com;

陈熙文,E-mail:2513758118@qq.com

摘要

借助模技巧, 将一类垂直线性互补问题转化为一个等价的非线性方程组. 在此基础上, 建立了一种新的基于模的矩阵分裂迭代法, 并对算法的收敛性进行了分析. 最后, 提供了一个数值算例, 并将所得数值结果与其它方法进行比较.

关键词： 垂直线性互补问题; 矩阵分裂; 迭代算法; 收敛性.

Abstract

By means of the modulus technique, a class of vertical linear complementarity problems is transformed into an equivalent nonlinear equation system. On this basis, a new modulus-based matrix splitting iterative method is established, and the convergence of the proposed algorithm is analyzed. Finally, one numerical example is provided for numerical experiment and the numerical result is compared with other methods.

Keywords： Lvertical linear complementarity problem; matrix splitting; iterative method; convergence.

PDF (577KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

温淑鸿, 柯艺芬, 肖丽芬, 陈熙文. 一类垂直线性互补问题的模系矩阵分裂迭代法[J]. 数学物理学报, 2026, 46(3): 1246-1254

Wen Shuhong, Ke Yifen, Xiao Lifen, Chen Xiwen. A Modulus-Based Matrix Splitting Iterative Method for a Class of Vertical Linear Complementarity Problems[J]. Acta Mathematica Scientia, 2026, 46(3): 1246-1254

1 引言

垂直线性互补问题 (Vertical Linear Complementarity Problem, 简称 VLCP): 寻找向量 $z,w_{1},w_{2},\cdots,w_{l} \in \mathbb{R}^n$ 使得

$w_{i}=A_{i}z+q_{i}\ (i=1,2\cdots, l)~~ \text{且}~~\min \left\{ z,w_{1},w_{2},\cdots, w_{l}\right\} =0,$

其中 $A_{i}\in\mathbb{R}^{n\times n}$ 和 $q_{i} \in\mathbb{R}^n$ 为已知的矩阵和向量. 这里 $\min\left\{ z,w_{1},w_{2},\cdots, w_{l} \right\} =0$ 被称为互补约束, 其表示按分量取最小值.

当 $l=1$ 时, VLCP (1.1) 退化为经典的线性互补问题 (Linear Complementarity Problem, 简称 LCP): 寻求向量 $z,w \in\mathbb{R}^n$ 使得

$ w=Az+q \geq 0,~~z\geq 0,~~w^{T}z = 0. $

VLCP 由 Cottle 和 Dantzig 在文献 [1] 中率先提出. 随后, Sznajder 建立了该问题解存在唯一性的充要条件[2]. VLCP 在非线性网络[3]、双矩阵博弈问题[4]、经济学分析[5]以及控制理论[6]等领域具有重要应用价值. 针对其求解, 学界已发展出多种数值算法, 典型代表算法包括: 光滑牛顿法[7]、延拓法[8]以及基于 VLCP 向 LCP 等价转化的求解框架[9].

模系矩阵分裂迭代法 (Modulus-based Matrix Splitting, 简记为 MMS) 由 Van Bokhoven 首创[10], 其核心思想是将线性互补问题重构为隐式不动点方程以设计迭代格式. Bai[11] 在此基础上引入矩阵分裂技术, 推动了该方法的理论发展. 此后, MMS 迭代法在多类互补问题中迅速扩展并应用[12-14], 包括非线性互补问题[15-16]、隐式互补问题[17-18]、拟互补问题[19]、水平线性互补问题[20]、二阶锥互补问题[21-22]以及旋转锥非线性互补问题[23].

Mezzadri 在文献 [24] 中首次将 MMS 迭代法应用于 VLCP 求解, 其数值实验表明该方法相较于牛顿类算法具有更显著的收敛速度优势. 这一突破性进展催生了 VLCP 求解算法的后续研究浪潮，相关理论拓展与算法改进可参见文献 [25-26].

本文主要研究 VLCP (1.1) 中 $l=3$ 的特殊情形, 即: 寻找向量 $ z \in \mathbb{R}^n $ 使得

$w_{1}=A_{1}z + q_1,\quad w_{2} = A_{2}z + q_{2},\quad w_{3} = A_{3}z + q_{3},\quad\min \left\{ z, w_{1}, w_{2}, w_{3} \right\} = 0,$

其中 $A_{i} \in \mathbb{R}^{n \times n} $ 和 $ q_{i} \in \mathbb{R}^n ( i=1,2,3 )$为给定的矩阵和向量.

本文致力于研究 VLCP (1.2) 的模系矩阵分裂迭代法, 从理论上分析该算法的收敛条件, 并进行系统性数值实验以验证其有效性. 本研究的关键创新在于针对 VLCP (1.2) 构建了一种新型模系矩阵分裂求解框架. 相较于文献 [24,26] 所提方法, 本方案具有三重显著优势

$\bullet $ 避免引入辅助变量, 显著降低了存储空间的复杂度;

$\bullet $ 仅需设置单一初始变量, 简化了算法初始化过程;

$\bullet $ 将每次迭代的线性方程组求解维度降至 3 阶.

而文献 [24,26] 要求双初始向量及 4 阶方程组求解, 计算复杂度更高.

本文用 $\mathbb{R}$ 表示实数域, $\mathbb{R}^n$ 表示 $n$ 维实向量空间, $\mathbb{R}^{n \times n}$ 表示 $n \times n$ 阶实矩阵的集合. 符号 $I$ 表示适当维数的单位矩阵, $|x|$ 表示向量的绝对值.设 $A = (a_{ij}) \in \mathbb{R}^{n \times n}$, 记 $|A| = (|a_{ij}|)$ 为矩阵 $A$ 的绝对值矩阵. 记 $\|\cdot\| $ 为 $\mathbb{R}^n$ 上的向量范数, $\|A\|$ 为由 $\|\cdot\|$ 诱导的矩阵范数, 即: $\|A\| = \max\{\|Ax\| : \|x\| = 1\}.$ 特别地, $\|\cdot\|_2$ 表示 2-范数. 用 $\|x\|$ 和 $\rho(A)$ 分别表示向量 $x$ 的 2-范数和矩阵 $A$ 的谱半径, 其定义为 $\rho(A)=\max\limits_{1\leqslant i \leqslant n} |\lambda_{i}(A)|$, 这里 $\lambda_i(A)$ 是矩阵 $A$ 的特征值.

2 模系矩阵分裂迭代法

下面给出两个重要的引理.

引理 2.1[27] 设 $a, b \in \mathbb{R}^n,$ 则 $a \geq 0,$b \geq 0,$\min\{a, b\} = 0$ 成立当且仅当 $a, b$ 满足 $a + b=|a-b|$.

引理 2.2 设 $a, b, c, d \in \mathbb{R}^n$, 则 $a \geq 0$,$b \geq 0$,$c \geq 0$,$d \geq 0$,$\min\{a, b, c, d\} = 0$ 成立当且仅当 $u, v$ 满足 $u + v = |u - v|,$ 其中

$u = \frac{a + b - |a - b|}{2},\quad v = \dfrac{c + d - |c - d|}{2}.$}

证 令

$u = \min\{a, b\} = \frac{a + b - |a - b|}{2} \geq 0,\quad v = \min\{c, d\} = \frac{c + d - |c - d|}{2} \geq 0.$

根据引理 2.1, $\min\{u, v\} = 0$ 成立当且仅当 $u + v = |u-v|$.

由于 $\min\{a, b, c, d\} = 0$ 等价于 $\min\{\min\{a, b\}, \min\{c, d\}\} = 0$, 即 $\min\{u, v\} = 0$. 从而, 引理得证.

基于引理 2.1 和引理 2.2, 可得以下重要定理.

定理 2.1 设 $A_{1}, A_{2}, A_{3} \in \mathbb{R}^{n \times n},$ 则 (1.2) 等价于如下方程

$(I + A_{1} + A_{2} + A_{3})z = |z - A_{1}z - q_{1}| + |(A_{2} - A_{3})z + (q_{2} - q_{3})| + |x - y| - (q_{1} + q_{2} + q_{3}),$

其中

$\begin{array}{ll} x = (I + A_{1})z + q_{1} - |(I - A_{1})z - q_{1}|, \\ y = (A_{2} + A_{3})z + (q_{2} + q_{3}) - |(A_{2} - A_{3})z + (q_{2} - q_{3})|. \end{array}$

证 根据引理 2.2, 可得

$\left\{\begin{array}{l}\frac{z+w_{1}-\left|z-w_{1}\right|}{2}+\frac{w_{2}+w_{3}-\left|w_{2}-w_{3}\right|}{2}=|u-v| \\u=\frac{z+w_{1}-\left|z-w_{1}\right|}{2} \\v=\frac{w_{2}+w_{3}-\left|w_{2}-w_{3}\right|}{2}\end{array}\right.$

令 $x=2u$, $y=2v$, 上述方程等价于

$\left\{\begin{array}{l}z+w_{1}+w_{2}+w_{3}=\left|z-w_{1}\right|+\left|w_{2}-w_{3}\right|+|x-y| \\x=z+w_{1}-\left|z-w_{1}\right| \\y=w_{2}+w_{3}-\left|w_{2}-w_{3}\right|\end{array}\right.$

将 $w_{1} = A_{1}z + q_{1}$, $w_{2} = A_{2}z + q_{2}$ 和 $w_{3} = A_{3}z + q_{3}$ 代入上述方程, 可得

$\left\{\begin{array}{l}\quad z+\left(A_{1} z+q_{1}\right)+\left(A_{2} z+q_{2}\right)+\left(A_{3} z+q_{3}\right) \\=\left|z-A_{1} z-q_{1}\right|+\left|\left(A_{2}-A_{3}\right) z+\left(q_{2}-q_{3}\right)\right|+|x-y|, \\x=z+A_{1} z+q_{1}-\left|z-\left(A_{1} z+q_{1}\right)\right|, \\y=A_{2} z+q_{2}+A_{3} z+q_{3}-\left|\left(A_{2}-A_{3}\right) z+\left(q_{2}-q_{3}\right)\right|.\end{array}\right.$

进一步, 化简得

$\left\{\begin{array}{l}\quad\left(I+A_{1}+A_{2}+A_{3}\right) z \\=\left|z-A_{1} z-q_{1}\right|+\left|\left(A_{2}-A_{3}\right) z+\left(q_{2}-q_{3}\right)\right|+|x-y|-\left(q_{1}+q_{2}+q_{3}\right), \\x=\left(I+A_{1}\right) z+q_{1}-\left|\left(I-A_{1}\right) z-q_{1}\right|, \\y=\left(A_{2}+A_{3}\right) z+\left(q_{2}+q_{3}\right)-\left|\left(A_{2}-A_{3}\right) z+\left(q_{2}-q_{3}\right)\right|.\end{array}\right.$

根据定理 2.1, 隐式不动点方程 (2.1) 可用于求解 VLCP (1.2) 的解. 通过对矩阵 $I + A_{1} + A_{2} + A_{3}$ 进行分裂, 可以构造出一种矩阵分裂迭代方法, 以求解隐式不动点方程 (2.1), 从而获得该方程的解. 具体算法构造如下.

  

新窗口打开| 下载CSV


算法 1 建立了求解 VLCP (1.2) 的模系矩阵分裂迭代法的一般框架. 通过选取适当的矩阵分裂, 可以得到一系列矩阵分裂迭代法. 记 $F = I + A_{1} + A_{2} + A_{3}$, 用 $D_{F}$, $-L_{F}$ 和 $-U_{F}$ 分别表示 $F$ 的对角部分, 严格下三角部分和严格上三角部分. 设

$M = \frac{1}{\alpha}(D_{F} - \beta L_{F}), \quad N = \frac{1}{\alpha}[(1-\alpha) D_{F} + (\alpha-\beta) L_{F} + \alpha U_{F}].$

(1) 当 $\alpha = 1, \beta = 0$ 时, 称为基于模的 Jacobi 方法 (MODJ);

(2) 当 $\alpha = \beta = 1$ 时, 称为基于模的 Gauss-Seidel 方法 (MODGS);

(3) 当 $\alpha = \beta$ 时, 称为基于模的 SOR 方法 (MODSOR).

3 收敛性分析

本节将探讨算法 1 收敛的充分性条件.

定理 3.1 设 $I+A_{1}+A_{2}+A_{3}=(\omega I+M)-(\omega I+N)(\omega>0)$ 是矩阵 $I+A_{1}+A_{2}+A_{3}$ 的一个分裂且 $\omega I+M$ 是非奇异矩阵. 记

$T=|(\omega I+M)^{-1}|[|\omega I+N|+2|I-A_{1}|+|I+A_{1}|+2|A_{2}-A_{3}|+|A_{2}+A_{3}|].$

.

若 $\rho(T)<1,$ 则对任意 $z^{(0)}\in \mathbb{R}^{n},$ 由算法 $1$ 产生的序列 ${\{z^{(k)}\}}_{k=0}^{\infty}$ 收敛于 VLCP (1.2) 的解.

证 设向量对 $(x^{*},y^{*},z^{*})$ 是方程 (2.1) 的精确解, 即

$\left\{\begin{array}{l}x^{*}=\left(I+A_{1}\right) z^{*}+q_{1}-\left|\left(I-A_{1}\right) z^{*}-q_{1}\right| \\y^{*}=\left(A_{2}+A_{3}\right) z^{*}+\left(q_{2}+q_{3}\right)-\left|\left(A_{2}-A_{3}\right) z^{*}+\left(q_{2}-q_{3}\right)\right| \\(\omega I+M) z^{*}=(\omega I+N) z^{*}+\left|z^{*}-A_{1} z^{*}-q_{1}\right| \\\quad+\left|\left(A_{2}-A_{3}\right) z^{*}+\left(q_{2}-q_{3}\right)\right|+\left|x^{*}-y^{*}\right|-\left(q_{1}+q_{2}+q_{3}\right)\end{array}\right.$

根据 (2.2) 式和 (3.1) 式, 可得

$\left\{\begin{array}{rl}x^{(k)}-x^{*}= & \left(I+A_{1}\right)\left(z^{(k)}-z^{*}\right)-\left|\left(I-A_{1}\right) z^{(k)}-q_{1}\right|+\left|\left(I-A_{1}\right) z^{*}-q_{1}\right| \\y^{(k)}-y^{*}= & \left(A_{2}+A_{3}\right)\left(z^{(k)}-z^{*}\right)-\left|\left(A_{2}-A_{3}\right) z^{(k)}+\left(q_{2}-q_{3}\right)\right| \\& +\left|\left(A_{2}-A_{3}\right) z^{*}+\left(q_{2}-q_{3}\right)\right| \\(\omega I+M)\left(z^{(k+1)}-z^{*}\right)= & (\omega I+N)\left(z^{(k)}-z^{*}\right)+\left|z^{(k)}-A_{1} z^{(k)}-q_{1}\right| \\& -\left|z^{*}-A_{1} z^{*}-q_{1}\right|+\left|\left(A_{2}-A_{3}\right) z^{(k)}+\left(q_{2}-q_{3}\right)\right| \\& -\left|\left(A_{2}-A_{3}\right) z^{*}+\left(q_{2}-q_{3}\right)\right|+\left|x^{(k)}-y^{(k)}\right|-\left|x^{*}-y^{*}\right|\end{array}.\right.$

由 (3.2) 式, 可得

$\begin{align*} |x^{(k)}-x^{*}|&=|(I+A_{1})(z^{(k)}-z^{*})-(|(I-A_{1})z^{(k)}-q_{1}|-|(I-A_{1})z^{*}-q_{1}|)| \\ & \leq|(I+A_{1})(z^{(k)}-z^{*})|+||(I-A_{1})z^{(k)}-q_{1}|-|(I-A_{1})z^{*}-q_{1}|| & \\ & \leq|(I+A_{1})(z^{(k)}-z^{*})|+|(I-A_{1})(z^{(k)}-z^{*})|\\ &\leq(|I+A_{1}|+|I-A_{1}|)|z^{(k)}-z^{*}|, \end{align*}$

上式第二个不等号成立是因为对任意的 $u,v\in \mathbb{R}^{n}$, 有 $||u|-|v||\leq|u-v|$.

同理, 可得 $|y^{(k)}-y^{*}|\leq(|A_{2}+A_{3}|+|A_{2}-A_{3}|)|z^{(k)}-z^{*}|$.

根据 (3.2) 式, 有

$\begin{align*} |z^{(k+1)}-z^{*}| & =|(\omega I+M)^{-1}\big[(\omega I+N)(z^{(k)}-z^{*})+|z^{(k)}-A_{1}z^{(k)}-q_{1}| \\ & \quad -|z^{*}-A_{1}z^{*}-q_{1}|+|(A_{2}-A_{3})z^{(k)}+(q_{2}-q_{3})|\\ & \quad -|(A_{2}-A_{3})z^{*}+(q_{2}-q_{3})|+|x^{(k)}-y^{(k)}|-|x^{*}-y^{*}|\big]|\\ & \leq|(\omega I+M)^{-1}|\big[|\omega I+N||z^{(k)}-z^{*}|+||z^{(k)}-A_{1}z^{(k)}-q_{1}|\\ & \quad -|z^{*}-A_{1}z^{*}-q_{1}||+||(A_{2}-A_{3})z^{(k)}+(q_{2}-q_{3})|\\ & \quad -|(A_{2}-A_{3})z^{*}+(q_{2}-q_{3})||+||x^{(k)}-y^{(k)}|-|x^{*}-y^{*}||\big]\\ & \leq|(\omega I+M)^{-1}|\big[|\omega I+N||z^{(k)}-z^{*}|+|z^{(k)}-A_{1}z^{(k)}-q_{1}-(z^{*}-A_{1}z^{*}-q_{1})|\\ & \quad +|(A_{2}-A_{3})z^{(k)}-(A_{2}-A_{3})z^{*}|+|x^{(k)}-y^{(k)}-(x^{*}-y^{*})|\big]\\ & \leq|(\omega I+M)^{-1}|\big[|\omega I+N||z^{(k)}-z^{*}|+|I-A_{1}||z^{(k)}-z^{*}|\\ & \quad +|A_{2}-A_{3}||z^{(k)}-z^{*}|+|x^{(k)}-x^{*}|+|y^{(k)}-y^{*}|\big]\\ & \leq|(\omega I+M)^{-1}|\big[|\omega I+N|+|I-A_{1}|+|A_{2}-A_{3}|+|I+A_{1}|\\ & \quad +|I-A_{1}|+|A_{2}+A_{3}|+|A_{2}-A_{3}|\big]\,|z^{(k)}-z^{*}|\\ & =|(\omega I+M)^{-1}|\big[|\omega I+N|+2|I-A_{1}|+|I+A_{1}|\\ & \quad +2|A_{2}-A_{3}|+|A_{2}+A_{3}|\big]\,|z^{(k)}-z^{*}|\\ & :=T|z^{(k)}-z^{*}|. \end{align*}$

因此, 如果 $\rho(T)<1$, 得到 $|z^{(k+1)}-z^{*}|<|z^{(k)}-z^{*}|$.

推论 3.1 设 $I+A_{1}+A_{2}+A_{3}=(\omega I+M)-(\omega I+N) (\omega>0)$ 是矩阵 $I+A_{1}+A_{2}+A_{3}$ 的一个分裂且 $\omega I+M$ 是非奇异矩阵. 记

$ \eta = \|(\omega I + M)^{-1}\| \left[ \|\omega I + N\| + 2\|I - A_{1}\| + \|I + A_{1}\| + 2\|A_{2} - A_{3}\| + \|A_{2} + A_{3}\| \right]. $

如果 $\eta<1,$ 则对任意 $z^{(0)}\in \mathbb{R}^{n},$ 由算法 $1$ 产生的序列 ${\{z^{(k)}\}}_{k=0}^{\infty}$ 收敛于 VLCP (1.2) 的解.

证 根据定理 3.1 以及范数的相容性, 可得 $\rho(T)\leq\|T\|\leq \eta <1$.

推论 3.2 设 $I+A_{1}+A_{2}+A_{3}=(\omega I+M)-(\omega I+N) (\omega>0)$ 是矩阵 $I+A_{1}+A_{2}+A_{3}$ 的一个分裂. 假设 $M$ 和 $N$ 均是对称正定矩阵$,$ 用 $\lambda_{\max}$ 和 $\lambda_{\min}$ 分别表示 $M$ 的最大特征值和最小特征值$,$\mu_{\max}$ 和 $\mu_{\min}$ 分别表示 $N$ 的最大特征值和最小特征值. 记

$s=2\| I-A_{1}\|+\| I+A_{1}\|+2\| A_{2}-A_{3}\|+\| A_{2}+A_{3}\|.$

若 $\lambda_{\min}>\mu_{\max}$ 且 $s<\lambda_{\min}-\mu_{\max},$ 则对任意 $z^{(0)}\in\mathbb{R} ^{n},$ 由算法 $1$ 产生的序列 ${\{z^{(k)}\}}_{k=0}^{\infty}$ 收敛于 VLCP (1.2) 的解.

证 由定理 3.1 的证明过程, 可得

$\begin{align*} |z^{(k+1)}-z^{*}| & \leq|(\omega I+M)^{-1}|\big[|\omega I+N|+|I-A_{1}|+|A_{2}-A_{3}|+|I+A_{1}|\\ & \quad+|I-A_{1}|+|A_{2}+A_{3}|+|A_{2}-A_{3}|\big]\,|z^{(k)}-z^{*}|\\ & =|(\omega I+M)^{-1}|\big[|\omega I+N|+2|I-A_{1}|+|I+A_{1}|\\ & \quad+2|A_{2}-A_{3}|+|A_{2}+A_{3}|\big]\,|z^{(k)}-z^{*}|. \end{align*}$

记 $S:=2|I-A_{1}|+|I+A_{1}|+2|A_{2}-A_{3}|+|A_{2}+A_{3}|$, 于是有

$\| S\|\leq2\| I-A_{1}\|+\| I+A_{1}\|+2\| A_{2}-A_{3}\|+\| A_{2}+A_{3}\|:=s.$

从而, 有 $\| z^{(k+1)}-z^{*}\|\leq\|(\omega I+M)^{-1}\|(\|\omega I+N||+\|S\|)\,\| z^{(k)}-z^{*}\|$. 由假设知, 当 $M$ 和 $N$ 是对称正定矩阵, 有

$\|(\omega I+M)^{-1}\|\leq\frac{1}{\omega+\lambda_{\min}},\quad \| \omega I+N\|\leq \omega+\mu_{\max}.$

因此, 可得

$ \|(\omega I+M)^{-1}\|(\| \omega I+N\|+ \| S\|) \leq\frac{1}{\omega+\lambda_{\min}}(\omega+\mu_{\max}+s). $

若 $\lambda_{\min}>\mu_{\max}$ 且 $s<\lambda_{\min}-\mu_{\max},$ 有 $\| z^{(k+1)}-z^{*}\|<\| z^{(k)}-z^{*}\|$.

4 数值实验

本节将给出数值例子来验证算法 1 的有效性. 数值实验将本文提出的 MODJ、MODGS 和 MODSOR 算法与文献 [26] 中的算法 5.1 (简称 RMMS) 的 RMJ、 RMGS、RMSOR 和算法 5.2 (简称 TRMMS) 的 TRMJ、TRMGS、TRMSOR 算法从迭代步数 (IT)、迭代时间 (CPU) 和残差范数 (ERR) 三个方面进行对比. 当迭代次数大于 1000 或残差向量范数满足

${\rm ERR}(k):=\|\min \{z^{(k)},~A_{1}z^{(k)}+q_{1},~A_{2}z^{(k)}+q_{2},~A_{3}z^{(k)}+q_{3}\}\|\leq 10^{-6}$

时, 测试方法停止. 数值实验在 Intel(R) Core(TM) 上运行, 其中 CPU 主频为 2.30 GHZ, 内存为 16.00 GB, 编程语言环境采用 MATLAB R2019B.

例 4.1 设 $h$ 为给定的正整数且 $n=h^{2}$. 考虑 VLCP (1.2)$,$ 其中 $A_{1},A_{2},A_{3}\in \mathbb{R}^{ n \times n}$ 为如下块对角矩阵和块三对角矩阵

$\begin{align*} & S={\rm Tridiag}(-1.5,4,-1.5)\in \mathbb{R}^{h\times h},\\ & A_{1}={\rm Diag}(S) +\theta I_n\in \mathbb{R}^{n\times n},\\ & A_{2}={\rm Tridiag}(-0.5I_n,S,-1.5I_n) +\theta I_n\in \mathbb{R}^{n\times n},\\ & A_{3}={\rm Tridiag}(-I_n,S,-0.5I_n) +\theta I_n\in \mathbb{R}^{n\times n}. \end{align*}$

令

$z_{i}^{*}=\left\{\begin{array}{l}0, \quad i \bmod 3=0 \text { 且 } i \leq \frac{3}{4} n, \\1, \quad \text { 否则, }\end{array} \quad w_{1}^{*}=e-z^{*}, \quad w_{2}^{*}=e, \quad w_{3}^{*}=e+z^{*}.\right.$

这里 $e=(1,1,\cdots,1)^T\in \mathbb{R}^n$. 置 $q_{1}=w_{1}^{*}-A_{1}z^*,$q_{2}=w_{2}^{*}-A_{2}z^*,$q_{3}=w_{3}^{*}-A_{3}z^*$.

图 1 展示了算法 1 中参数 $\omega$ 与迭代步数 (IT) 及残差向量范数 (ERR) 之间的相关性. 实验数据表明, 增大 $\omega$ 值可显著降低算法的迭代次数, 但 ERR 的收敛特性未呈现明确规律性. 为获得最优数值结果, 在例 1 中算法 1 选取初始向量 $z^{( 0 )}=(1,1,\cdots,1)^T\in \mathbb{R}^n$、$\omega=3$ 和 $\theta=1$ 进行实验. 对于文献 [26] 中的算法 5.1 和算法 5.2, 取初始向量 $x_{1}^{( 0 )}=x_{2}^{( 0 )}=(0,0,\cdots,0)^T\in \mathbb{R}^n$、 $\theta=1$、$\gamma=1$ 和 $\omega=1.1$. 进一步, 根据文献 [26] 的理论约束条件, 当 $l=3$ 时, 需满足 $\Omega\geq\dfrac{\omega}{4}(2D_{A}+D_{B}+D_{C})$. 因此, 文献 [26] 中的算法 5.1 和算法 5.2, 均取 $\Omega=1.1D_{A}+1.65D_{B}+1.1D_{C}$, 且对于 SOR 方法, 选取 $\alpha=\beta=1.2$.

图 1

新窗口打开| 下载原图ZIP| 生成PPT

图 1   例 4.1 中 MGS 算法中参数 $\omega$ 的影响 ($h$=40)


针对例 4.1, 分别取 $h=20,40,80$ 进行数值测试, 表 1 详细记录了九种算法的性能对比结果. 实验数据显示, MODJ、MODGS 和 MODSOR 三种改进算法在迭代次数 (IT) 和 CPU 耗时上均优于文献 [26] 中以算法 5.1 为基准的 RMJ、RMGS、RMSOR 算法. 相较于文献 [26] 算法 5.2 的 TRM 系列算法, MODJ 在两项指标上全面超越 TRMJ, 尽管 TRMGS 和 TRMSOR 算法的迭代步数略低于 MODGS、MODSOR 算法, 但其 CPU 耗时显著超出改进算法, 这一差异随着维数 $h$ 的增大呈指数级放大. 在全部的九种算法中, MODJ 算法以最小迭代步数 (IT) 和最低计算成本 (CPU 耗时最少) 确定了其综合性能最优地位. 这证实了 MODJ、MODGS、MODSOR 算法在处理高维稀疏矩阵问题时具有显著计算优势.

表1   例 4.1 的数值结果

新窗口打开| 下载CSV


图 2 分别展示了算法 1 与文献 [26] 中的算法 5.1 (RMMS) 和算法 5.2 (TRMMS) 在算例 4.1 中的迭代次数与残差向量范数 (ERR) 之间的关系对比图. 从残差向量范数 (ERR) 的演变规律可见, 算法 1 中的 MODJ、MODGS 和 MODSOR 算法与文献 [26] 中的算法 5.1 (RMMS) 的 RMJ、RMGS、RMSOR 和算法 5.2 (TRMMS) 的 TRMJ、TRMGS、TRMSOR 算法的残差向量范数均保持严格的单调递减特性, 这验证了所有算法的收敛性与有效性. 特别地, 在改进算法的组内比较中, MODJ 算法展现出双重优势, 其不仅残差范数最低, 其收敛速率也更快.

图 2

新窗口打开| 下载原图ZIP| 生成PPT

图 2   例 1 的残差下降图 ($h$=40)


5 结论

本文提出了一种基于模系矩阵分裂的新型迭代理论框架, 致力于求解特定类型的垂直线性互补问题 (1.2). 该方法是对水平线性互补问题中模系矩阵分裂技术的扩展, 适用于解决垂直线性互补问题. 文中不仅提供了算法收敛性的充分条件和迭代方程, 还通过数值实例说明所提算法在迭代次数和 CPU 时间上优于文献 [26] 中的算法 5.1 (RMMS) 的 RMJ、RMGS、RMSOR 和算法 5.2 (TRMMS) 的 TRMJ、TRMGS、TRMSOR 算法. 未来的研究将进一步探讨此方法在更广泛类型的垂直线性互补问题中的应用潜力.

参考文献

Cottle R W, Pang J S., Stone R E. The Linear Complementarity Problem. San Diego: Academic, 1992

[本文引用: 1]

Sznajder R, Gowda M S.

Generalizations of $P_0$-and $P$-properties; extended vertical and horizontal linear complementarity problems

Linear Algebra and its Applications, 1995, 223/224 : 695-715

DOI:10.1016/0024-3795(93)00184-2      URL     [本文引用: 1]

Gowda M S, Sznajder R.

A generalization of the Nash equilibrium theorem on bimatrix games

International Journal of Game Theory, 1996, 25 : 1-12

DOI:10.1007/BF01254380      URL     [本文引用: 1]

Zhang L P, Gao Z Y.

Global linear and quadratic one-step smoothing Newton method for vertical linear complementarity problems

Applied Mathematics and Mechanics, 2003, 24 : 738-746

DOI:10.1007/BF02437876      URL     [本文引用: 1]

Nagae T, Akamatsu T.

A generalized complementarity approach to solving real option problems

Journal of Economic Dynamics and Control, 2008, 32 (6): 1754-1779

DOI:10.1016/j.jedc.2007.04.010      URL     [本文引用: 1]

Sun M.

Monotonicity of Mangasarian's iterative algorithm for generalized linear complementarity problems

Journal of Mathematical Analysis and Applications, 1989, 144 (2): 474-485

DOI:10.1016/0022-247X(89)90347-8      URL     [本文引用: 1]

Qi H D, Liao L Z.

A smoothing Newton method for extended vertical linear complementarity problems

SIAM Journal on Matrix Analysis and Applications, 1999, 21 (1): 45-66

DOI:10.1137/S0895479897329837      URL     [本文引用: 1]

Peng J M, Lin Z.

A non-interior continuation method for generalized linear complementarity problems

Mathematical Programming, 1999, 86 (3): 533-563

DOI:10.1007/s101070050104      URL     [本文引用: 1]

Mohan S R, Neogy S K, Sridhar R.

The generalized linear complementarity problem revisited

Mathematica Program, 1996, 74 (2): 197-218

[本文引用: 1]

Van Bokhoven W M G. Piecewise-Linear Modelling and Analysis.Eindhoven: Proefschrift, 1981

[本文引用: 1]

Bai Z Z.

Modulus-based matrix splitting iteration methods for linear complementarity problems

Numerical Linear Algebra with Applications, 2010, 17 (6): 917-933

DOI:10.1002/nla.v17.6      URL     [本文引用: 1]

Bai Z Z, Zhang L L.

Modulus-based synchronous multisplitting iteration methods for linear complementarity problems

Numerical Linear Algebra with Applications, 2013, 20 (3): 425-439

DOI:10.1002/nla.v20.3      URL     [本文引用: 1]

Bai Z Z, Zhang L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numerical Algorithms, 2013, 62 (1): 59-77

Wu S L, Li C X.

Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems

Journal of Computational Mathematics, 2016, 302 : 327-339

[本文引用: 1]

Ma C F, Huang N.

Modifed modulus-based matrix splitting algorithms for a class of weakly nondiferentiable nonlinear complementarity problems

Applied Numerical Mathematics, 2016, 108 : 116-124

DOI:10.1016/j.apnum.2016.05.004      URL     [本文引用: 1]

Huang N, Ma C F.

The modulus-based matrix splitting algorithms for a class of weakly nondifferentiable nonlinear complementarity problems

Numerical Linear Algebra with Applications, 2016, 23 (3): 558-569

DOI:10.1002/nla.v23.3      URL     [本文引用: 1]

Wu S L, Li L.

New modulus-based matrix splitting methods for implicit complementarity problem

Numerical Algorithms, 2022, 90 (4): 1735-1754

DOI:10.1007/s11075-021-01249-9      [本文引用: 1]

黎科良, 柯艺芬, 马昌凤.

求解一类隐式互补问题的加速模系矩阵分裂迭代方法

应用数学, 2023, 36 (4): 1025-1033

[本文引用: 1]

Li K L, Ke Y F, Ma C F.

Accelerated modulus-based matrix splitting iteration method for solving a class of implicit complementarity problems

Mathematica Applicata, 2023, 36 (4): 1025-1033

[本文引用: 1]

Wu S L, Guo P.

Modulus-based matrix splitting algorithms for the quasi-complementarity problems

Applied Numerical Mathematics, 2018, 132 : 127-137

DOI:10.1016/j.apnum.2018.05.017      URL     [本文引用: 1]

Mezzadri F, Galligani E.

Modulus-based matrix splitting methods for horizontal linear complementarity problems

Numerical Algorithms, 2020, 83 : 201-219

DOI:10.1007/s11075-019-00677-y      [本文引用: 1]

Ke Y F, Ma C F, Zhang H.

The modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems

Numerical Algorithms, 2018, 79 (4): 1283-1303

DOI:10.1007/s11075-018-0484-4      [本文引用: 1]

李枝枝, 柯艺芬, 储日升, 等.

二阶锥线性互补问题的广义模系矩阵分裂迭代算法

计算数学, 2019, 41 (4): 395-405

DOI:10.12286/jssx.2019.4.395      [本文引用: 1]

通过将二阶锥线性互补问题转化为等价的不动点方程，介绍了一种广义模系矩阵分裂迭代算法，并研究了该算法的收敛性.进一步，数值结果表明广义模系矩阵分裂迭代算法能够有效地求解二阶锥线性互补问题.

Li Z Z, Ke Y F, Chu R S, et al.

Generalized modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems

Mathematica Numerica Sinica, 2019, 41 (4): 395-405

DOI:10.12286/jssx.2019.4.395      [本文引用: 1]

For the second-order cone linear complementarity problem, we reformulate it as an implicit fixed-point equation and propose a generalized modulus-based matrix splitting iteration method to solve it. The convergence of the proposed method is studied. Moreover, numerical results have shown its effectiveness.

Ke Y F, Ma C F, Zhang H.

The relaxation modulus-based matrix splitting iteration methods for circular cone nonlinear complementarity problems

Computational and Applied Mathematics, 2018, 37 (5): 6795-6820

DOI:10.1007/s40314-018-0687-2      [本文引用: 1]

Mezzadri F.

A modulus-based formulation for the vertical linear complementarity problem

Numerical Algorithms, 2022, 90 (4): 1547-1568

DOI:10.1007/s11075-021-01240-4      [本文引用: 3]

Guo W X, Zheng H, Peng X F.

New convergence results of the modulus-based methods for vertical linear complementarity problems

Applied Mathematics Letters, 2023, 135 : Art 108444

[本文引用: 1]

Wang D, Li J C.

Relaxation modulus-based matrix splitting iteration method for vertical linear complementarity problem

Journal of Computational and Applied Mathematics, 2024, 437 : Art 115430

[本文引用: 12]

Li C X, Wu S L.

A class of new modulus-based matrix splitting methods for linear complementarity problem

Optimization Letters, 2022, 5 : 1-17

DOI:10.1007/s11590-010-0228-4      URL     [本文引用: 1]

/

〈 〉

版权所有 © 《数学物理学报》杂志社
地址：武汉市71010号信箱(430071)　电话: 027-87199206(中文版)　027-87199087(英文版)
E-mail: actams@wipm.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发