节点文献

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

Algorithms and Convergence Analysis for Absolute Value Equations

【作者】 王炳囡

【导师】 屈彪;

【作者基本信息】 曲阜师范大学 , 运筹学与控制论, 2012, 硕士

【摘要】 绝对值方程(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]是正则的条件下,证明该算法全局超线性收敛到绝对值方程的唯一解.通过数值实验可知本章中的算法是可行的,并且有较快的收敛速度.第四章,首先将绝对值方程转化成一个求解函数最小值的无约束优化问题,然后提出一种负梯度下降算法,并且证明了算法的可行性和收敛性.由数值实验的结果可知该算法是可行的.

【Abstract】 The study of the absolute value equations(AVE)Ax|x|=b, A∈n×n, bn∈is inspired from the linear complementary problem(LCP). The AVE is a spe-cial class of nonlinear equations. The absolute value equations is equivalent tolinear complementary problem and bilinear programming problem, therefore, lin-ear programming, quadratic programming, linear complementary and so on canbe transformed equivalently to absolute value equations. So the absolute valueequations have strong application background.We mainly give a research on solving absolute value equations in this paper.According to the nonsmoothing of the absolute value, we propose a smoothingNewton method and a negative gradient descent algorithm for solving the absolutevalue equations. And we prove the feasibility and the convergence of algorithms.Preliminary numerical results show that the two algorithms are promising. Thefull thesis is divided into four chapters.The first chapter is the introduction. We describe the application back-grounds, the research situations and achievements of the absolute value equationsproblem. Several efective algorithms and the research ideas are analyzed in thischapter.In the second chapter,we directly give a smoothing function of the absolutevalue equations. And then,under the condition that the interval matrix [A I, A+I] is regular, we propose a smoothing Newton method for solving AVE.The convergence of the algorithm is proved.In the third chapter, we transform the AVE into a semismooth functionequations Φ(x)=0based on Fischer-Burmeister function and generalized lin-ear complementary problem. And then, we give a smoothing function Φ (x) ofΦ(x), and also discuss the basic properties of it. Then we propose an imporved smoothing Newton method for solving AVE. Under the condition that the inter-val matrix [A—I, A+I] is regular, the imporved algorithm is global superlinear convergence to the unique solution of the absolute value equations. Numerical results of this chapter show that the algorithm is feasible.In Chapter4, in order to avoid the non-differentiability of the absolute value function, we transform the absolute value equations into a unconstrained opti-mization problem. Then we propose a negative gradient descent algorithm. The feasibility and convergence of the algorithm are also proved. Numerical results show that the algorithm is feasible.

节点文献中: 

本文链接的文献网络图示:

本文的引文网络