兰州大学机构库 >数学与统计学院
几类绝对值方程和非线性互补问题的迭代求解
Alternative TitleIterative solution of several absolute value equations and nonlinear complementarity problems
张佳霖
Subtype博士
Thesis Advisor张国凤
2023-05-20
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name理学博士
Degree Discipline计算数学
Keyword绝对值方程 Absolute value equation 非线性互补问题 nonlinear complementarity problem 张量绝对值方程 tensor absolute value equation 迭代方法 iterative method 收敛性 convergence
Abstract

科学计算和工程应用领域中的许多实际应用问题, 如生产管理, 交通运输, 金融工程和工农业生产等, 很多可归结为涉及绝对值函数的复杂系统的求解问题. 这类问题大部分都是不可微, 多变量和多参数的复杂优化问题. 由于其复杂的结构特点, 对相应系统的有效数值求解造成了很大困难. 随着社会经济和科学技术的飞速发展, 使得该类问题的变量维数急剧增加致使其结构复杂性增强, 从而如何有效的求解大规模的此类问题显得尤为重要. 总之, 如何根据系统本身的结构特点设计经济, 高效且稳健的数值解法具有非常重要的实际意义.

本文主要针对涉及绝对值函数的三大类重要系统的数值求解问题展开研究,这三类系统分别是绝对值方程组, 非线性互补问题以及张量绝对值方程. 对这些问题构造快速高效的数值求解方法具有非常重要的理论意义和实际应用价值, 全文主要工作包括以下三个部分.

第一部分研究绝对值方程的有效迭代求解. 首先, 针对一般绝对值方程, 通过适当的等价变换将其转化为具有特殊结构的 2×2 分块线性系统. 基于变形后系数矩阵的结构特点, 构造了适用于一般绝对值方程的修正的广义 SOR (MGSOR)迭代方法, 并给出了相应的收敛性分析和最优迭代参数的具体表达形式. 该方法继承了求解 2×2 分块线性系统的广义 SOR (GSOR) 方法与求解一般绝对值方程的 SOR 方法的优点, 推广了此类 SOR 方法并改善了其收敛性. MGSOR 方法用于求解一般绝对值方程时, 其数值表现稳定且优于若干已有的有效算法. 其次,针对广义绝对值方程, 利用其结构特点将方程可微部分的系数矩阵进行分裂, 并结合源于神经网络算法且能够改善矩阵分裂方法性能的动量加速技术, 设计了适用于广义绝对值方程的基于矩阵分裂的动量加速迭代方法并给出其最优动量因子的选择方式. 该方法与求解广义绝对值方程的 Picard 方法, Newton 方法和基于Newton 方法的矩阵分裂 (NMS) 迭代方法相比, 具有灵活且通用的特点. 当系数矩阵为正定矩阵和 H+-矩阵时, 分析了该类加速方法的收敛性, 并通过数值算例验证了所提方法的有效性.

第二部分研究一类非线性互补问题 (NCP(F)) 的有效迭代求解. 首先, 将该互补问题等价转化为隐式不动点方程组, 然后通过引入两个参数矩阵 Ω1和 Ω2并结合求解此类 NCP(F) 的模系矩阵分裂 (MMS) 迭代方法, 给出适用于 NCP(F)的广义 MMS (GMMS) 迭代方法. 其次, 借鉴求解线性互补问题的预处理 MMS(PMMS) 迭代法并通过选择恰当的预处理矩阵 P, 构造了比 GMMS 更高效的预处理 GMMS (PGMMS) 迭代方法. 最后, 为了进一步提高迭代法的计算效率, 在PGMMS 迭代方法的基础上, 结合求解 NCP(F) 的两步 MMS (TMMS) 迭代方法, 设计了一类求解 NCP(F) 的预处理广义两步模系 AOR (PGTMAOR) 迭代方法. 该方法不仅融合了预处理与两步迭代法的技巧以提高算法效率, 还为求解此类 NCP(F) 提供了一个基于模系矩阵分裂迭代方法的通用形式. 进一步, 详细地分析了系数矩阵为正定矩阵和 H+-矩阵时算法的收敛性质, 亦通过数值算例比较了 PGTMAOR 迭代方法与已有迭代方法, 验证了所提算法求解该类 NCP(F) 的可行性和有效性.

第三部分研究一类张量绝对值方程 (TAVE) 的有效迭代求解. 针对此类张量绝对值方程, 根据其具体结构特点, 给出两类有效的迭代求解方法. 第一类方法源于常用的 Anderson 加速 (AA) 技术. 结合求解多重线性系统的张量分裂 (TS) 迭代方法与预处理技术, 构造了求解 TAVE 的预处理张量分裂 (PTS) 迭代方法. 在此基础上, 为了进一步提高迭代法的计算效率, 设计了适用于 TAVE 的基于 AA 的PTS (AAPTS) 迭代方法. 理论上, 根据压缩映射原理, 给出 TS 迭代方法和 PTS迭代方法的新的收敛性分析. 基于此, 结合绝对值函数的强半光滑性理论, 给出了AAPTS 迭代方法的局部收敛性理论, 最后的数值例子也验证了 AAPTS 迭代方法求解 TAVE 时的高效性. 第二类方法源于经典的 Levenberg-Marquardt (LM) 方法. 鉴于张量存储的高内存特性及运算的复杂性, 利用张量的低秩逼近–张量链式(Tensor Train, TT) 分解来解决此问题, 并结合 LM 方法提出了求解具有 TT-格式的 TAVE 的 LMTT 方法. 该方法克服了“维数灾难”现象, 其算法复杂度是线性的, 避免了已有算法存在的高计算复杂度缺陷. 同时, 在局部误差界条件下证明了该方法具有全局收敛性和局部二次收敛性, 且该条件弱于 Jacobian 函数的非奇异和 Lipschitz 连续的假设性条件. 进一步, 基于求解 TAVE 的 TS 方法, 设计了一类结合 TS 方法和 LMTT 方法的混合方法 (H-LMTT). 数值结果表明了这两类LMTT (LMTT-like) 方法的可行性和有效性. 最后的一些数值实验也验证了所提方法的有效性.

Other Abstract

Many practical problems in scientific computing and engineering applications, such as production management, transportation, financial engineering, industrial and agricultural production, can be reduced to solving complex systems involving absolute value functions. Most of these problems are complex optimization problems that are non-differentiable, multi-variable and multi-parameter. Due to their complex structural characteristics, effective numerical solutions for these systems have been difficult to obtain. With the rapid development of social economy and science and technology, the increasing dimensionality of variables in such problems has made their complexity even more challenging to solve, making it crucial to design efficient and robust numerical methods based on the system's structural characteristics. In a word, how to design an economical, efficient and robust numerical solution according to the structural characteristics of the system itself is of great practical significance.

This dissertation focuses on the numerical solution of three important systems involving absolute value functions, namely absolute value equations, nonlinear complementarity problems, and tensor absolute value equations. Developing fast and efficient numerical methods for solving these problems is of great theoretical and practical importance. The dissertation consists of three parts.

The first part investigates the effective iterative methods for solving absolute value equations. Firstly, an effective iterative method called modified generalized SOR (MGSOR) is proposed for solving general absolute value equations by transforming them into structured 2×2 block linear systems. The convergence properties of the MGSOR method are analyzed, and the explicit expression of optimal iterative parameters is given. The MGSOR method inherits the advantages of the generalized SOR (GSOR) method for solving 2×2 block linear systems and the SOR method for solving general absolute value equations, and improves their convergence properties. When the MGSOR method is used to solve general absolute value equations, its numerical performance is stable and superior to some existing effective algorithms. Secondly, a matrix splitting-based momentum accelerated iterative method is designed for solving generalized absolute value equations, which combines the splitting technique with momentum acceleration to improve performance. The method is flexible and applicable to various cases, and its convergence properties are analyzed when the coefficient matrix is positive definite or H+-matrix, and its optimal momentum factor is determined. Numerical experiments demonstrate the effectiveness of the proposed methods in comparison with existing algorithms such as Picard method, Newton-like method and Newton-based matrix splitting (NMS) for solving generalized absolute value equations.

The second part focuses on developing effective iterative methods for solving a class of nonlinear complementarity problems (NCP(\emph{F})). The (NCP(\emph{F})) is first transformed into an equivalent implicit fixed-point equation system, and then a generalized MMS (GMMS) iterative method for (NCP(\emph{F})) is proposed by introducing two parameter matrices Ω1 and Ω2 and combining with the modulus-based matrix splitting (MMS) iterative method for solving this type of problems. A more efficient preconditioned GMMS (PGMMS) iterative method than GMMS is constructed by using the idea of preconditioned MMS (PMMS) iterative method for solving linear complementarity problems and selecting an appropriate preconditioning matrix P. Finally, a preconditioned generalized two-step modulus-based accelerated overrelaxation (PGTMAOR) iterative method is developed by combining PGMMS with a two-step MMS (TMMS) iterative method for further improving computational efficiency. This method not only combines the skills of preconditioning and two-step iterative methods to improve algorithm efficiency but also provides a universal form based on the MMS iterative method for solving this type of (NCP(\emph{F})). The convergence properties of the algorithm are analyzed in detail when the coefficient matrix is positive definite or H+-matrix, and numerical experiments are used to compare PGTMAOR with some existing iterative methods, demonstrating the feasibility and effectiveness of the proposed method.

The third part investigates the effective iterative methods for solving a class of tensor absolute value equations (TAVE). Two effective iterative methods are proposed based on the specific structural characteristics of TAVE. The first method is derived from the commonly used Anderson acceleration (AA) technology. By combining the tensor splitting (TS) iterative method of multilinear systems with the preconditioned technique, a preconditioned tensor splitting (PTS) iterative method is constructed for solving TAVE. To further improve computational efficiency, an Anderson acceleration-based preconditioned tensor splitting (AAPTS) iterative method is designed. The convergence properties of TS and PTS iterative methods are analyzed based on the principle of compressed mappings. Based on the theory of the strong semi-smoothness of absolute value functions, the local convergence properties of AAPTS iterative method are discussed. Numerical experiments demonstrate the effectiveness of AAPTS iterative method. The second method is based on the classical Levenberg-Marquardt (LM) method, which uses the low-rank approximation of tensors-Tensor Train (TT) decomposition to overcome the high memory usage and computational complexity of tensor storage. The LMTT method for solving TAVE with TT-format is proposed by combining LM method with TT decomposition. The algorithm complexity of LMTT method is linear, and it overcomes the "curse of dimensionality" phenomenon. The global convergence and local quadratic convergence of LMTT method are proved under the assumption of local error bound condition, which is weaker than the non-singularity and Lipschitz continuity conditions of Jacobian function. A hybrid method (H-LMTT) is also designed based on the TS method and the LMTT method. Numerical experiments demonstrate the feasibility and effectiveness of these two types of LMTT (LMTT-like) methods. Finally, some numerical experiments are presented to verify the effectiveness of the proposed methods.

Subject Area数值代数
MOST Discipline Catalogue理学 - 数学 - 计算数学
URL查看原文
Language中文
Other Code262010_120180905401
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/534847
Collection数学与统计学院
Affiliation
兰州大学数学与统计学院
Recommended Citation
GB/T 7714
张佳霖. 几类绝对值方程和非线性互补问题的迭代求解[D]. 兰州. 兰州大学,2023.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[张佳霖]'s Articles
Baidu academic
Similar articles in Baidu academic
[张佳霖]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[张佳霖]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.