一类特殊二阶锥绝对值方程问题解的区间估计*

赵敬云，苗新河

（天津大学数学学院，天津 300350）

0 引 言

绝对值方程问题是一类与线性互补问题有着紧密联系的优化问题.由于互补理论在工程学、运筹学和博弈论等众多领域有着广泛的应用背景，绝对值方程问题受到了国内外专家学者们的密切关注，因此其研究具有一定的理论意义和价值.二阶锥绝对值方程问题是一类在二阶锥框架下的绝对值方程问题，与二阶锥线性互补问题有着紧密联系的优化问题.本文考虑二阶锥绝对值方程（secondorder-cones absolute value equations，SOCAVE）问题，公式为

式中B∈Rn×n，b∈Rn，|x|表示二阶锥意义下x的绝对值.通常意义下，二阶锥Kn是若干单个二阶锥的笛卡尔乘积：，其中表示欧式范数.考虑到笛卡尔积的性质，所有的分析同样适用于多个二阶锥乘积的情形.为方便分析，本文只考虑单个二阶锥的情况，即r=1.

在欧氏空间Rn中，一般标准的绝对值方程（absolute value equations，AVE）具有如下形式：Ax-b=B|x|.当矩阵A可逆时，可等价转化成问题（1）的形式.AVE问题最初是由Rohn［1］引入的概念，随后被众多学者所关注并相继投身于此方面的研究中，像线性规划、二次规划、双矩阵博弈等问题都可以看成求解绝对值方程问题［2-6］.Mangasarian 和 Meyer［2］给出了绝对值方程解的存在性和唯一性的充分条件；在文献［3-7］中，也分别探讨了绝对值方程问题与线性互补问题之间的关系.此外，关于绝对值方程问题的求解，已出现多种求解方法，如：广义牛顿法［5，8］、光滑牛顿法［9］、符号标记法［10］.Hladík［11］利用解的区间近似估计了绝对值方程的解，还有多种方法求解绝对值方程，详细可见文献［7，11-12］.另外，在二阶锥框架下：Hu等［13］研究了二阶锥绝对值方程等价于一类二阶锥线性互补问题，并提出求解二阶锥绝对值方程问题的广义牛顿法；Miao等［14-15］进一步探讨了求解二阶锥绝对值方程问题的光滑牛顿法.在本文中，将推广 Hladík［11］的思想，在二阶锥框架下，采用区间方法来近似估计绝对值方程问题（1）的解.同时，本文也进行了数值实验来比较这些方法在计算时间和估计质量方面的差异，通过具体数值算例来验证算法的可行有效性.

1 基础知识

本小节主要介绍一些有关二阶锥的基本概念和相关结论，为后面的分析提供理论基础，更多相关内容可参见文献［16-17］.

对于欧氏空间Rn中任意的2个向量x=(x1，x2)∈R×Rn-1和y=(y1，y2)∈R×Rn-1，x和y的内积定义为：=x1y1+=xTy.x和y的若当乘积定义为

式中◦表示若当乘积的运算符号.基于此概念，若当乘积意义下的单位元素为e=(1，0，…，0)T∈Rn.此外，x2表示x2=x◦x；表示x∈Kn的平方根向量，即由此表达形式，SOCAVE问题（1）中的绝对值||x可定义为

为了进一步明确|x|的表达式，需要用到元素x谱分解的概念.对于任意的向量x=(x1，x2)∈R×Rn-1，关于二阶锥Kn，元素x的谱分解为

式中λi=x1+(-1)i‖x2‖(i=1，2)称为x的谱特征值；{u1，u2}称为x的Jordan谱分解基，ui取值为

式中ω∈Rn-1是满足条件‖ω‖=1的任意向量，且易证ui为二阶锥Kn上的向量.

引理1.1［15］对任意的x=(x1，x2)∈R×Rn-1，则其特征向量u1、u2满足：

u1◦u2=0，ui◦ui=ui(i=1，2).

对任意的向量x=(x1，x2)∈R×Rn-1，若令x+表示x到二阶锥Kn上的投影，x-表示-x到二阶锥的对偶锥(Kn)*上的投影.因为二阶锥是自对偶的，即Kn=(Kn)*，基于二阶锥的特殊结构，结合x谱分解形式和投影的性质，可得x=x+-x-，并且投影x+，x-的表达式可分别表示为：

x+=(λ1)+u1+(λ2)+u2，x-=(-λ1)+u1+(-λ2)+u2，

式中(α)+=max{0，α}，α∈R.此外，可得到问题（1）中x的绝对值也可定义为|x|=x++x-.事实上，在二阶锥框架下，|x|=x++x-与的定义形式是等价的.结合投影表达形式和谱分解形式，则绝对值|x|具有如下形式

为了方便讨论，对于元素x，y∈Rn，本文用符号“x≽y”或“y≼x”表示为“x-y∈Kn”.由元素的谱分解和二阶锥的特性，则有下面的结论.

定理1.1若x和y具有相同的Jordan谱分解基

2 SOCAVE（1）解的区间估计

定义2.1设以及A=[aij]，则区间矩阵定义为，记为A：=[A1，A2]；区间向量定义为[b1，b2]={b∈Rn：b1≼b≼b2}，记为b：=[b1，b2]；向量a≤b表示对任意的i，都有ai≤bi.

定义2.3区间线性方程组问题为：Ax=b：={Cx=d：C∈A，d∈b}.

2.1 Bauer-Skeel型区间界

对于SOCAVE问题（1），如果矩阵B满足，根据文献［16］中的定理4.2，可知SOCAVE问题（1）存在唯一解.此外，x，b和B||x会具有相同的Jordan谱分解基，不妨设

若记λ：=(λ1，λ2)T，：=(δ1，δ2)T且v：=(v1，v2)T，则谱特征值向量λ，以及v满足下面的结论.

由于SOCAVE问题（1）是一类特殊的二阶锥绝对值方程问题，并且矩阵B的特殊结构，可知方程的解以及向量b具有相同的Jordan谱分解基{u1，u2}.由引理1.1得知u1⊥u2.又根据谱分解的表达式，可知λ1≤λ2，所以对任意的SOCAVE问题（1）的解向量x，可能会在图1中①、②、③的区域，不可能出现在④的区域.

图1 谱向量平面

通过定理2.2，可知当整个解区间xBS分别单独位于区域①或②或③时，二阶锥绝对值方程x-b=B|x|的解可直接计算求解.若解区间xBS横跨不同的区域时，则求解是非常困难的.由此，以下部分将考虑解区间xBS单独位于同一区域的概率和xBS所在区域个数的均值，当概率和均值越接近于1时，则越容易求解x-b=B|x|的解.

设b=δ1u1+δ2u2，则|b|=|δ1|u1+|δ2|u2.假设δ1和δ2相互独立且δi在[-1，1]上为均匀分布.由式（6）可知，需考虑到mi和δi，即考虑|δi|即可，故只需取|δi|∈[0，1].

2.2 Hansen-Bliek-Rohn型区间界

3 数值实验

矩阵B的非零元素在［-1，1］上随机均匀分布，向量b=δ1u1+δ2u2的谱特征值δ（ii=1，2）在［-1，1］上也随机均匀分布，且矩阵B满足σ=2‖B‖∞≤1（σ是已知值）.2种边界的具体实验结果如表1所示.根据实验结果可以得出下面结论.解的所在区间位于唯一确定区域的概率比命题2给出的唯一性概率的下界大得多；只要B的无穷范数足够小，解的所在区间位于区域个数的均值越小；Bauer-Skeel和Hansen-Bliek-Rohn方法得到的结果相似，前者的运行时间较快，但当B的无穷范数较大时，后者得到的结果会更好.当B的无穷范数较小时，可选择Bauer-Skeel型区间；当B的无穷范数较大时，选择Hansen-Bliek-Rohn型区间.除此之外，无论是理论分析还是数值实验，可得出2种方法所求得解的所在区间位于同一区域的概率、解的所在区间位于区域个数的均值以及运行时间均与矩阵的维数无关.

表1 2种边界的具体实验结果

4 结束语

对于一类特殊二阶锥绝对值方程的求解，本文提出了Bauer-Skeel型区间法和Hansen-Bliek-Rohn型区间法.通过理论分析了SOCAVE问题（1）解的所在区间位于同一区域的概率值以及解的所在区间位于区域个数的均值.此外，也通过数值试验体现了算法具有较好的数值稳定性.