求解绝对值方程的梯度型算法

发布时间：2018-05-22 18:13

本文选题：绝对值方程 + 无约束最优化　；参考：《南京理工大学》2017年硕士论文

【摘要】：绝对值方程(AVE)Ax-|x|=b,是一类特殊的非线性方程,也是一个NP-hard问题。绝对值方程来源于区间问题且目前应用于许多实际问题中,如:背包可行性问题、选址问题以及无监督和半监督分类问题。另一方面,绝对值方程又与线性互补问题具有等价性,而传统的线性规划、二次规划和对偶矩阵对策等优化问题都可以转化为线性互补问题。因此,绝对值方程的研究为许多数学规划问题提供了一新的求解途径。综上,绝对值方程的研究具有重要的意义。本论文在AVE有解的条件下,重点研究了绝对值方程的求解方法。第一,在系数矩阵A为对称正定的条件下,我们给出了求解绝对值方程的PRP共轭梯度法,并分析了其收敛性,数值实验也表明了该算法的有效性。第二,在矩阵A为正定非对称的条件下,我们将绝对值方程转化为系数矩阵为对称正定的线性方程组,进而采用预处理共轭梯度法来对得到的方程组进行求解,从而得出原问题的解。数值实验结果都表明了新方法的有效性。
[Abstract]:The absolute value equation is a special nonlinear equation and a NP-hard problem. The absolute value equation is derived from interval problem and is applied to many practical problems, such as knapsack feasibility problem, location problem and unsupervised and semi-supervised classification problem. On the other hand, the absolute value equation is equivalent to the linear complementarity problem, and the traditional optimization problems such as linear programming, quadratic programming and dual matrix games can be transformed into linear complementarity problems. Therefore, the study of absolute value equations provides a new way to solve many mathematical programming problems. In summary, the study of absolute value equation is of great significance. In this paper, we focus on the solution of absolute value equation under the condition that AVE has solutions. First, under the condition that the coefficient matrix A is symmetric positive definite, we give the PRP conjugate gradient method for solving the absolute value equation, and analyze its convergence. Numerical experiments also show the effectiveness of the algorithm. Secondly, under the condition that the matrix A is positive definite and asymmetric, we transform the absolute value equation into a system of linear equations whose coefficient matrix is symmetric positive definite, and then use the preconditioned conjugate gradient method to solve the obtained equations. Thus the solution of the original problem is obtained. Numerical results show the effectiveness of the new method.
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O151.1

【参考文献】