广义绝对值方程

龚成，戴培良

（常熟理工学院数学与统计学院，江苏常熟 215500）

广义绝对值方程

龚成，戴培良

（常熟理工学院数学与统计学院，江苏常熟 215500）

广义绝对值方程是绝对值方程的推广，证明了其等价于广义线性互补问题，探讨了广义绝对值方程解唯一存在的条件，这些结果也推广了Mangasarian在文献[1]中的结论，提出了广义绝对值方程解唯一存在的几个充要条件.最后，给出了广义绝对值方程的一个迭代算法，理论分析和数值结果均说明该方法是有效的.

广义绝对值方程；广义线性互补问题；迭代算法；

0 引言

考虑如下形式的广义绝对值方程

其中A,B∈Rn×n，b,c∈Rn，绝对值依分量运算．当B=E（单位矩阵）且c=0，绝对值方程（1）就是

绝对值方程作为有效的优化工具，自Rohn在文献[2]中提出后，学者Mangasarian，Prokopyev等深入研究了绝对值方程的理论和数值求解．文献[1，3，4]证明了绝对值方程等价于线性互补问题且其求解是NP-难的．文献[5]基于绝对值方程和背包问题的联系，提出了求解背包问题的序列线性规划方法．文献[6]提出了一个求解绝对值方程的拟牛顿算法．文献[7]提出求解绝对值方程的区间方法．

本文进一步研究了形如（1）的广义绝对值方程，证明了其等价于广义线性互补问题：给定n×n阶实方阵M，N和n维实向量p，q，求满足如下条件的实向量x：

并且讨论了其解的存在性问题，拓展了文献[2]中的一些结果．最后，给出广义绝对值方程的一个迭代算法．

1 等价问题

先考虑广义绝对值方程与垂直线性互补问题的等价性．

定理1.1 广义绝对值方程（1）等价于垂直线性互补问题0≤(Mx+q)⊥(Nx+p)≥0．

考虑每一个分量，根据|s-t|=s+t⇔s≥0,t≥0,st=0可知广义绝对值方程（1）等价于0≤(Mx+q)⊥(Nx+p)≥0.证毕．

推论若A-B可逆，则广义绝对值方程（1）等价于线性互补问题

证明若A-B可逆，则(A-B)-1存在．令z=(A-B)x-c-b，根据定理1.1，广义绝对值方程（1）等价于0≤z⊥(A+B)(A-B)-1z+q≥0，其中q=(A+B)(A-B)-1(c+b)+c-b，z=(A-B)x-c-b．证毕．

2 可解问题

下面考虑广义绝对值方程（1）的可解性．

记σmin(A)和σmax(A)为矩阵A的最小奇异值和最大奇异值．

定理2.1若σmax(B)＜σmin(A)，则对于任意给定的向量b,c∈Rn，广义绝对值方程（1）有唯一解．

证明先证(A-B)-1存在．假设不存在，则存在向量x≠0，使得(A-B)x=0．故

在霸座视频疯传的同时，一些“如果霸座这事发生在国外”的视频，也引起网友热议。例如今年1月，美国一名18岁的女生乘坐地铁时，把脚放在座位上，警察警告无效后，直接将她强行拉下车并拘捕。据悉，美国地铁规定“若将脚或鞋放在座位上，轻则被警告，重则会被赶下地铁”。哪怕是再微小的违法行为，执法者也必须说不。这，正是法治社会的应有之义。

有唯一解可知定理成立．证毕．

定义2.1如果矩阵Q的第i行是矩阵M的第i行或者矩阵N的第i行，那么称矩阵Q为矩阵集合{M,N}的行表示矩阵，其中i=1,2,…n．

引理[8]对于任意向量p,q∈Rn，垂直线性互补问题0≤(Mx+q)⊥(Nx+p)≥0有唯一解等价于以下任一命题：

（1）矩阵集合{M,N}的所有行表示矩阵有相同的非零行列式符号．

（2）对于任意非负对角矩阵Λ1,Λ2∈Rn×n且Λ1+Λ2的对角元都大于零，那么行列式|Λ1M+Λ2N|不为零．

定理2.2对于任意向量b,c∈Rn，广义绝对值方程（1）有唯一解等价于以下任一命题：

（1）矩阵集合{A+B,A-B}的所有行表示矩阵有相同的非零行列式符号．

（3）A+B可逆，且矩阵集合{E,(A-B)(A+B)-1}的所有行表示矩阵的行列式大于零．

证明由广义绝对值方程与垂直线性互补问题的等价性和引理易知（1）和（2）成立．下面，只需证（1）⇔（3）．

（1）⇒（3）：对任意的b,c∈Rn，广义绝对值方程（1）有唯一解，则{A+B,A-B}的行表示矩阵有相同的非零行列式符号，故A+B行列式不为零从而可逆．现在矩阵集合{E,(A-B)(A+B)-1}的任何行表示矩阵可以表示为K(A+B)-1的形式，其中K是矩阵集合{A+B,A-B}的行表示矩阵．因此矩阵组{E,(A-B)(A+B)-1}的行表示矩阵有相同的行列式符号．从而矩阵集合{E,(A-B)(A+B)-1}的所有行表示矩阵的行列式大于零．

（3）⇒（1）：由于矩阵集合{E,(A-B)(A+B)-1}的任何行表示矩阵可以表示为K(A+B)-1的形式，其中K是矩阵集合{A+B,A-B}的行表示矩阵．因此矩阵K的行列式|K|不为零，且|K|恒正或者恒负．从而矩阵集合{A+B,A-B}的所有行表示矩阵有相同的非零行列式符号．证毕．

当B=E（单位矩阵）且c=0时，得到下面的推论．

推论[8]对于任意向量b∈Rn，绝对值方程（1）有唯一解等价于以下任一命题：

（1）矩阵A+diag(y1,y2,…,yn)的行列式有相同的非零行列式符号，其中|yi|=1，i=1,2,…n．

（2）对于任意非负对角矩阵Λ1,Λ2∈Rn×n且Λ1+Λ2的对角元都大于零，那么行列式|(Λ1+Λ2)A+(Λ1-Λ2)|不为零．

（3）A+E可逆，且矩阵集合{E,(A-E)(A+E)-1}的所有行表示矩阵的行列式大于零．

以上的定理与推论，讨论了绝对值方程有解的情形，这有助于我们更深地理解绝对值方程及其相关的数学模型．

3 迭代算法

若A可逆，Ax-|Bx+c|=b可化为x=A-1|Bx+c|+A-1b=f(x)．

对任意x,y∈Rn，有

若‖A-1‖‖B‖＜1，则对任意b,c∈Rn，广义绝对值方程（1）有唯一解．此时

故f(x)是压缩映射．根据Banach压缩映射原理，f(x)有唯一不动点．所以序列xk+1=f(xk)是收敛到广义绝对值方程的唯一解．

在Matlab7.0上编程计算例题．

例1.（随机测试）Ax-|Bx+c|=b，其中

随机取初始点

记ω：计算精度；T:CPU时间；k:求解迭代次数．得到近似解为

表1 计算结果

数值结果表明了算法是有效的．但算法涉及到求逆，因此一旦规模变大，算法将不适合．如何求解大规模的绝对值方程，也是我们将来的工作之一．

[1]Mangasarian O，Meyer R.Absolute value equations[J].Linear Algebra Appl，2006，419:359-367.

[2]Rohn J.A theorem of the alternatives for the equation Ax+B|x|=b[J].Linear and Multilinear Algebra，2004，52（6）:421-426.

[3]Prokopyev O.On equivalent reformulations f-or absolute value equations[J].Comput Optim Appl，2009，44:363-372.

[4]Mangasarian O.Absolute value programming[J].Comput Optim Appl，2007，36（1）:43-53.

[5]Mangasarian O.Knapsack feasibility as an ab-solute value equation solvable by successive linear programming[J].Optim Lett，2009 （3）:161-170.

[6]Mangasarian O.A generalized Newton metho-d for absolute value equations[J].Optim Lett，2009（3）:101-108.

[7]王爱祥，王海军.绝对值方程的区间算法[J].贵州大学学报，2010，27（2）：7-10．

[8]王爱祥，王海军，龚成.绝对值方程的唯一可解性[J].科学技术与工程，2010，10（34）：8501-8502．

Generalized Absolute Value Equations

GONG Cheng，DAI Pei-liang
（School of Mathematics and Statistics,Changshu Institute of Technology,Changshu 215500,China)

This paper is concerned with the generalized absolute value equations.It shows that the generalized absolute value equations are equivalent to the generalized linear complementarity problem and a bilinear pro⁃gram.Existence results of the generalized absolute value equations solution are obtained and the results of Man⁃gasarian in[2]are improved.Some necessary and sufficient conditions are given.An iterative algorithm is pro⁃posed for the generalized absolute value equations.Theoretic analysis and numerical results show that the meth⁃od is effective.

generalized absolute value equations;generalized linear complementarity problem;iterative algorithm

O242.2

A

1008-2794（2011）08-0027-04

2011-06-01

龚成（1989—），男，江苏兴化人，常熟理工学院数学与统计学院2011届毕业生.

戴培良（1965—），男，江苏常熟人，常熟理工学院数学与统计学院教授，博士，研究方向：计算数学，E-mail: dpl@cslg.edu.cn．