求解绝对值线性互补问题的一种广义牛顿法

包丽平，杨丹丹

( 内蒙古民族大学 数学学院，内蒙古 通辽028043)

取n=10 绝对值互补问题(AVLCP(A，b))的矩阵A 如下:

线性互补问题首先是由著名运筹学家、数学规划的创始人Dentzig 和他的学生Cottle 于1963 年提出的．次年，Cottle 在他的博士论文中第一次提出了求解它的数学规划算法．线性互补问题不仅优化问题、二次规划和约束优化问题的最优性条件(KKT 条件)之间有着紧密的联系，并且已经发展成为运筹学的一个重要分支．它们已经广泛应用于力学、交通、经济、金融、控制等领域，因此，线性互补问题的理论与算法研究一直是应用数学和计算数学领域中的一个热点问题［1－4］．随着对线性互补问题这一领域研究的不断深入，线性互补问题已经做出许多推广，例如:广义线性互补问题、垂直线性互补问题、水平线性互补问题、隐互补问题等．近期，作为线性互补问题的一种新的推广，Noor 等人［5］于2012 年定义并研究了绝对值线性互补问题(简记作AVLCP(A，b))，其定义如下:

给定A∈Rn×n，b∈Rn，求x=(x1，x2，…，xn)∈Rn，使得:

其中|x|=(|x1|，|x2|，…，|xn|)∈Rn，K是闭凸锥，K*={x∈Rn|〈x，y〉≥0，y∈K}为K的极锥．

文献［5］构造了如下绝对值互补问题(1)的等价的绝对值变分不等式:

令K是内积空间Rn闭凸锥，求x=(x1，x2，…，xn)∈Rn，使得:

绝对值线性互补问题还与绝对值方程密切相关．当K=Rn时，AVLCP(A，b)等价于如下绝对值方程组:

许多学者对该方程组的求解进行了深入的研究，其中Mangasarian 等人给出了凹函数极小化方法及牛顿法等，并且Mangasarian 还证明了绝对值方程组等价于经典的线性互补问题．自此也有许多学者对绝对值方程组的存在性理论与求解算法进行了探讨，许多实际问题可抽象为绝对值线性互补模型，需要设计高效的算法求解绝对值线性互补问题．目前只有Noor 等人提出绝对值线性互补问题的广义AOR 迭代法，并且算法的收敛速度是线性的．因此，建立绝对值线性互补问题的解存在性理论和设计有效求解绝对值线性互补问题的新型的收敛速度更快的算法具有重要的理论意义和实际价值．基于此，本文建立求解绝对值互补问题的新型有效算法．

1 主要结果

定理1 若A－Dx正定，设，当时，x*是AVLCP(A，b)的解．

其中D'是向量λx+(1－λ)x*∈K，λ∈(0，1］所对应的对角阵，其中D″是向量Z*所对应的对角阵．当λ→0+，D'→D″，整理得:

当λ→0+，有:(x－x*)T［(A－D)x*－b］≥0，∀x∈K，所以x*是AVLCP(A，b)的一个解．

2 广义牛顿算法

设目标函数f(x)梯度为g(x)、Hesse 阵为H(x)，则:

求解二次极小化问题的广义牛顿法的迭代格式如下:

下面给出本文所建立的广义牛顿算法:

step 1:初始点x0，精度要求ε＞0，置k=0;

step 2:计算xk+1=［A－Dxk］;

step 3:若D(xk+1)=D(xk)且‖Axk－Dxkxk－b‖＜ε 停止，得到解x*=xk;否则置k=k+1，转step 2．

3 收敛性分析

由文献［6］的引理6 得到结论对任意的初始点，序列xk

{ }线性收敛到AVLCP(A，b)的唯一解．

4 数值实验

本节中，将通过数值例子来说明本文所建立的算法的有效性．运用Matlab7．5 进行计算，运行环境为:CPU 为Intel(R)Core(TM)2×2．70 GHz，内存为2．0 GB．计算进度为1．0e－6

例1［5］考虑常微分方程:

取n=10 绝对值互补问题(AVLCP(A，b))的矩阵A如下:

令初始矩阵D分别为

通过广义牛顿法分别迭代一次和二次得到相同的近似解:

通过这个例子看到经过简单步就得到精确解的近似值．

5 结语

本文建立了在绝对值互补问题的矩阵奇A－Dx正定的条件下一个绝对值互补问题的在一定条件下转化为求凸二次函数极小值问题，在此转化下提出一个求解绝对值互补问题的广义牛顿法，证明了算法的全局收敛性，本算法具有格式简单，存储量小，迭代次数少和易于在计算机上实现等优点，为此本文给出的迭代法可以作为求解绝对值互补问题的一个有效算法．

［1］ 韩继业，修乃华，戚厚铎．非线性互补理论与算法［M］．上海:上海科学技术出版社，2006．

［2］ 袁亚湘，孙文瑜．最优化理论与方法［M］．北京:科学出版社，1997．

［3］ Mangasarian O L．Absolute value equations［J］．Linear Algebra Appl，2006，419:259－267．

［4］ Sun D F，Womersley R S，Qi H D．A feasible semi－smooth asymptotically Newton method for mixed complementarity problems［J］．Math Program A，2002，94:167－187．

［5］ Noor M A，Iqbal J，Noor K I，et al．Generalized AOR method for solving absolute complementarity problems［J］．Journal of Applied Mathematics，2012，Article ID 743861，14 pages，2012．

［6］ Mangasarian O L．A generalized Newton method for absolute value equations［J］．Optimization Letters，2009，3(1):101－108．