绝对值方程的算法及其收敛性分析

作     者：王炳囡 

作者单位：曲阜师范大学 

学位级别：硕士

导师姓名：屈彪

授予年度：2012年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：绝对值方程 光滑Newton算法 区间矩阵 FB-函数 下降算法 全局超线性收敛性 

摘      要：绝对值方程（AVE）Ax-??的研究来源于线性互补问题,是非线性方程的一种特例.由于绝对值方程与线性互补问题,双线性规划问题的等价性,对于一些重要的问题,如线性规划、二次规划、线性互补等都可以等价的转化为绝对值方程,因此绝对值方程问题有着极强的应用背景. 本文主要是在Mangasarian等人的工作基础上,对求解绝对值方程问题做了进一步研究.根据绝对值的非光滑性,分别提出了求解绝对值方程的光滑Newton方法和一种负梯度下降算法,分析了函数的特殊性质,在理论上证明了算法的可行性和收敛性,并且通过数值实验表明这两种算法是可行的. 本文共分四章,主要结构如下： 第一章绪论,主要是对绝对值方程问题的来源及研究背景做了简要的阐述,介绍了绝对值方程的研究现状及研究成果,具体分析了现有的几个有效算法和研究思想. 第二章,基于区间矩阵[A—I,A+I]是正则的条件下,由光滑函数的思想,直接给出绝对值方程的一个光滑函数,建立解决绝对值方程的光滑牛顿算法,并证明了算法的收敛性.本章中所给出的条件要比A的奇异值大于1这个条件要弱.在区间矩阵[A—I,A+I]是正则的条件下,建立了算法的全局收敛性. 第三章,根据绝对值方程等价于广义线性互补问题,借助FB-函数的性质,先将绝对值方程转化为求解方程组φ（x）=0的解.然后通过光滑Jacobian函数的思想,将函数φ（x）光滑化,并在区间矩阵[A—I,A+I]是正则的条件下,讨论了φ（x）的光滑函数中。（x）的基本性质.而后给出一种光滑Newton方法,在区间矩阵[A—I,A+I]是正则的条件下,证明该算法全局超线性收敛到绝对值方程的唯一解.通过数值实验可知本章中的算法是可行的,并且有较快的收敛速度. 第四章,首先将绝对值方程转化成一个求解函数最小值的无约束优化问题,然后提出一种负梯度下降算法,并且证明了算法的可行性和收敛性.由数值实验的结果可知该算法是可行的.