求解一类绝对值方程组的光滑牛顿算法

摘要

流行的绝对值方程组是指A?||=。一方面，很多实际问题可以模型化为一个绝对值方程组，另一方面，线性规划、二次规划、线性互补问题等很多优化及相关问题可以等价地转化为一个绝对值方程组，因此，绝对值方程组具有广泛的实际应用背景。已经证明绝对值方程组是一个NP-难问题。所以对绝对值方程组的研究具有重要的理论意义和实际应用价值。绝对值方程组近年来已经得到了广泛的关注，取得了很快的研究进展。
　　本文考虑一类广义的绝对值方程组，即，它是方程组A?|=的推广，主要讨论求解这类绝对值方程组的理论与算法。主要工作如下：
　　（1）本文首先将该问题等价转换成为一个线性互补问题,之后设计一个光滑牛顿算法求解该互补问题。当矩阵?和矩阵?可逆，矩阵和对乘法满足交换律，以及矩阵的主对角线上的元素的绝对值严格大于矩阵主对角线上的绝对值时，证明了该算法是适定的。另外，当矩阵=0时，证明了该算法的全局收敛性。
　　（2）本文在Matlab软件中分别对800维，和1000维等的情况进行了数值试验。每种情况分别随机产生了50个可解的绝对值方程组，数值实验结果精度达到了610?。800维的用时在10秒左右，1000维的用时在20秒左右。数值结果表明本文的算法是有效的。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 问题的介绍

1.1 研究背景与选题意义

1.2 国内外文章综述

1.2.1目前国内外理论有进展

1.2.2目前国内外算法研究的状况

1.3 本文主要内容以及安排

第二章 算法设计

2.1 绝对值方程组等价转化为线性互补问题

2.2 NCP函数

2.3 光滑牛顿法

2.4 算法的性质

第三章 算法的收敛性

第四章 数值计算

第五章 总结与展望

参考文献

发表论文和参加科研情况说明

致谢