一類特殊二階錐絕對值方程問題解的區(qū)間估計(jì)*

趙敬云，苗新河

（天津大學(xué)數(shù)學(xué)學(xué)院，天津 300350）

0 引 言

絕對值方程問題是一類與線性互補(bǔ)問題有著緊密聯(lián)系的優(yōu)化問題.由于互補(bǔ)理論在工程學(xué)、運(yùn)籌學(xué)和博弈論等眾多領(lǐng)域有著廣泛的應(yīng)用背景，絕對值方程問題受到了國內(nèi)外專家學(xué)者們的密切關(guān)注，因此其研究具有一定的理論意義和價(jià)值.二階錐絕對值方程問題是一類在二階錐框架下的絕對值方程問題，與二階錐線性互補(bǔ)問題有著緊密聯(lián)系的優(yōu)化問題.本文考慮二階錐絕對值方程（secondorder-cones absolute value equations，SOCAVE）問題，公式為

式中B∈Rn×n，b∈Rn，|x|表示二階錐意義下x的絕對值.通常意義下，二階錐Kn是若干單個(gè)二階錐的笛卡爾乘積：，其中表示歐式范數(shù).考慮到笛卡爾積的性質(zhì)，所有的分析同樣適用于多個(gè)二階錐乘積的情形.為方便分析，本文只考慮單個(gè)二階錐的情況，即r=1.

在歐氏空間Rn中，一般標(biāo)準(zhǔn)的絕對值方程（absolute value equations，AVE）具有如下形式：Ax-b=B|x|.當(dāng)矩陣A可逆時(shí)，可等價(jià)轉(zhuǎn)化成問題（1）的形式.AVE問題最初是由Rohn［1］引入的概念，隨后被眾多學(xué)者所關(guān)注并相繼投身于此方面的研究中，像線性規(guī)劃、二次規(guī)劃、雙矩陣博弈等問題都可以看成求解絕對值方程問題［2-6］.Mangasarian 和 Meyer［2］給出了絕對值方程解的存在性和唯一性的充分條件；在文獻(xiàn)［3-7］中，也分別探討了絕對值方程問題與線性互補(bǔ)問題之間的關(guān)系.此外，關(guān)于絕對值方程問題的求解，已出現(xiàn)多種求解方法，如：廣義牛頓法［5，8］、光滑牛頓法［9］、符號標(biāo)記法［10］.Hladík［11］利用解的區(qū)間近似估計(jì)了絕對值方程的解，還有多種方法求解絕對值方程，詳細(xì)可見文獻(xiàn)［7，11-12］.另外，在二階錐框架下：Hu等［13］研究了二階錐絕對值方程等價(jià)于一類二階錐線性互補(bǔ)問題，并提出求解二階錐絕對值方程問題的廣義牛頓法；Miao等［14-15］進(jìn)一步探討了求解二階錐絕對值方程問題的光滑牛頓法.在本文中，將推廣 Hladík［11］的思想，在二階錐框架下，采用區(qū)間方法來近似估計(jì)絕對值方程問題（1）的解.同時(shí)，本文也進(jìn)行了數(shù)值實(shí)驗(yàn)來比較這些方法在計(jì)算時(shí)間和估計(jì)質(zhì)量方面的差異，通過具體數(shù)值算例來驗(yàn)證算法的可行有效性.

1 基礎(chǔ)知識

本小節(jié)主要介紹一些有關(guān)二階錐的基本概念和相關(guān)結(jié)論，為后面的分析提供理論基礎(chǔ)，更多相關(guān)內(nèi)容可參見文獻(xiàn)［16-17］.

對于歐氏空間Rn中任意的2個(gè)向量x=(x1，x2)∈R×Rn-1和y=(y1，y2)∈R×Rn-1，x和y的內(nèi)積定義為：=x1y1+=xTy.x和y的若當(dāng)乘積定義為

式中?表示若當(dāng)乘積的運(yùn)算符號.基于此概念，若當(dāng)乘積意義下的單位元素為e=(1，0，…，0)T∈Rn.此外，x2表示x2=x?x；表示x∈Kn的平方根向量，即由此表達(dá)形式，SOCAVE問題（1）中的絕對值||x可定義為

為了進(jìn)一步明確|x|的表達(dá)式，需要用到元素x譜分解的概念.對于任意的向量x=(x1，x2)∈R×Rn-1，關(guān)于二階錐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)*上的投影.因?yàn)槎A錐是自對偶的，即Kn=(Kn)*，基于二階錐的特殊結(jié)構(gòu)，結(jié)合x譜分解形式和投影的性質(zhì)，可得x=x+-x-，并且投影x+，x-的表達(dá)式可分別表示為：

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

式中(α)+=max{0，α}，α∈R.此外，可得到問題（1）中x的絕對值也可定義為|x|=x++x-.事實(shí)上，在二階錐框架下，|x|=x++x-與的定義形式是等價(jià)的.結(jié)合投影表達(dá)形式和譜分解形式，則絕對值|x|具有如下形式

為了方便討論，對于元素x，y∈Rn，本文用符號“x?y”或“y?x”表示為“x-y∈Kn”.由元素的譜分解和二階錐的特性，則有下面的結(jié)論.

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

2 SOCAVE（1）解的區(qū)間估計(jì)

定義2.1設(shè)以及A=[aij]，則區(qū)間矩陣定義為，記為A：=[A1，A2]；區(qū)間向量定義為[b1，b2]={b∈Rn：b1?b?b2}，記為b：=[b1，b2]；向量a≤b表示對任意的i，都有ai≤bi.

定義2.3區(qū)間線性方程組問題為：Ax=b：={Cx=d：C∈A，d∈b}.

2.1 Bauer-Skeel型區(qū)間界

對于SOCAVE問題（1），如果矩陣B滿足，根據(jù)文獻(xiàn)［16］中的定理4.2，可知SOCAVE問題（1）存在唯一解.此外，x，b和B||x會(huì)具有相同的Jordan譜分解基，不妨設(shè)

若記λ：=(λ1，λ2)T，：=(δ1，δ2)T且v：=(v1，v2)T，則譜特征值向量λ，以及v滿足下面的結(jié)論.

由于SOCAVE問題（1）是一類特殊的二階錐絕對值方程問題，并且矩陣B的特殊結(jié)構(gòu)，可知方程的解以及向量b具有相同的Jordan譜分解基{u1，u2}.由引理1.1得知u1⊥u2.又根據(jù)譜分解的表達(dá)式，可知λ1≤λ2，所以對任意的SOCAVE問題（1）的解向量x，可能會(huì)在圖1中①、②、③的區(qū)域，不可能出現(xiàn)在④的區(qū)域.

圖1 譜向量平面

通過定理2.2，可知當(dāng)整個(gè)解區(qū)間xBS分別單獨(dú)位于區(qū)域①或②或③時(shí)，二階錐絕對值方程x-b=B|x|的解可直接計(jì)算求解.若解區(qū)間xBS橫跨不同的區(qū)域時(shí)，則求解是非常困難的.由此，以下部分將考慮解區(qū)間xBS單獨(dú)位于同一區(qū)域的概率和xBS所在區(qū)域個(gè)數(shù)的均值，當(dāng)概率和均值越接近于1時(shí)，則越容易求解x-b=B|x|的解.

設(shè)b=δ1u1+δ2u2，則|b|=|δ1|u1+|δ2|u2.假設(shè)δ1和δ2相互獨(dú)立且δi在[-1，1]上為均勻分布.由式（6）可知，需考慮到mi和δi，即考慮|δi|即可，故只需取|δi|∈[0，1].

2.2 Hansen-Bliek-Rohn型區(qū)間界

3 數(shù)值實(shí)驗(yàn)

矩陣B的非零元素在［-1，1］上隨機(jī)均勻分布，向量b=δ1u1+δ2u2的譜特征值δ（ii=1，2）在［-1，1］上也隨機(jī)均勻分布，且矩陣B滿足σ=2‖B‖∞≤1（σ是已知值）.2種邊界的具體實(shí)驗(yàn)結(jié)果如表1所示.根據(jù)實(shí)驗(yàn)結(jié)果可以得出下面結(jié)論.解的所在區(qū)間位于唯一確定區(qū)域的概率比命題2給出的唯一性概率的下界大得多；只要B的無窮范數(shù)足夠小，解的所在區(qū)間位于區(qū)域個(gè)數(shù)的均值越?。籅auer-Skeel和Hansen-Bliek-Rohn方法得到的結(jié)果相似，前者的運(yùn)行時(shí)間較快，但當(dāng)B的無窮范數(shù)較大時(shí)，后者得到的結(jié)果會(huì)更好.當(dāng)B的無窮范數(shù)較小時(shí)，可選擇Bauer-Skeel型區(qū)間；當(dāng)B的無窮范數(shù)較大時(shí)，選擇Hansen-Bliek-Rohn型區(qū)間.除此之外，無論是理論分析還是數(shù)值實(shí)驗(yàn)，可得出2種方法所求得解的所在區(qū)間位于同一區(qū)域的概率、解的所在區(qū)間位于區(qū)域個(gè)數(shù)的均值以及運(yùn)行時(shí)間均與矩陣的維數(shù)無關(guān).

表1 2種邊界的具體實(shí)驗(yàn)結(jié)果

4 結(jié)束語

對于一類特殊二階錐絕對值方程的求解，本文提出了Bauer-Skeel型區(qū)間法和Hansen-Bliek-Rohn型區(qū)間法.通過理論分析了SOCAVE問題（1）解的所在區(qū)間位于同一區(qū)域的概率值以及解的所在區(qū)間位于區(qū)域個(gè)數(shù)的均值.此外，也通過數(shù)值試驗(yàn)體現(xiàn)了算法具有較好的數(shù)值穩(wěn)定性.