论文部分内容阅读
绝对值方程是一个NP-hard问题.它来源于区间问题且在许多实际问题中有着广泛的应用,如:选址问题,半监督和无监督分类问题以及背包可行性问题等.在求解线性规划,双矩阵对策,二次规划等问题时需要转化成线性互补问题进行处理,而线性互补问题又可以归纳为绝对值方程.因此,绝对值方程的研究为许多数学规划问题提供了一种新的求解途径,从而对绝对值方程理论及算法的研究具有重要的意义. 本论文在绝对值方程有解的条件下,研究了绝对值方程的数值解法.第一,对绝对值函数,我们构造了一个新的光滑逼近函数,利用该函数将绝对值方程问题转化为光滑方程组,进而用光滑牛顿算法求解该方程组,在适当条件下证明了算法二次收敛性,数值结果表明,我们的算法是有效的.第二,对绝对值方程构造了一个新的价值函数,说明了该函数的梯度的Lipschitz连续性,并得到了水平集有界性,进而利用FR共轭梯度算法求解绝对值方程,证明了算法全局收敛性.数值结果表明了算法的有效性.