幾種特殊矩陣的Pareto特征值問(wèn)題

齊亞超, 陳雄達(dá)（同濟(jì)大學(xué)數(shù)學(xué)系，上海 200092）

幾種特殊矩陣的Pareto特征值問(wèn)題

齊亞超, 陳雄達(dá)
（同濟(jì)大學(xué)數(shù)學(xué)系，上海 200092）

Pareto特征值問(wèn)題是定義在正卦限上一類錐約束問(wèn)題，在許多領(lǐng)域有著深厚的背景。將討論P(yáng)areto特征值的一些理論性質(zhì)，包括給定矩陣Pareto特征值范圍及個(gè)數(shù)上界。引進(jìn)了一類新矩陣，討論并給出它的部分理論性質(zhì)，可直接計(jì)算其最大Pareto特征值。

Pareto特征值；錐約束；特征值；非負(fù)矩陣；加邊矩陣；對(duì)偶錐

0 引言

雖然Pareto特征值問(wèn)題的提法簡(jiǎn)單，卻具有全新的理論研究?jī)r(jià)值和廣闊的實(shí)際應(yīng)用性，是傳統(tǒng)的代數(shù)特征值問(wèn)題的推廣和擴(kuò)展，開拓了新的數(shù)學(xué)理論領(lǐng)域。在Seeger已經(jīng)做出的一些重要理論的基礎(chǔ)上[1]，我

們對(duì)Pareto特征值做了進(jìn)一步討論。首先我們規(guī)定一些使用符號(hào)：歐氏空間?的內(nèi)積x,y=，相應(yīng)的歐氏范數(shù)，歐氏空間正交x⊥y 表示x,y=0。同時(shí)，記N={1,2,…,n}，指標(biāo)集I,J?N，我們采用如下記號(hào)：

則稱C 為一個(gè)凸集。一個(gè)錐若是凸集，稱為凸錐。如果凸錐K 又是一個(gè)閉的，那么稱K是一個(gè)閉凸錐。我

則稱錐K 是有指向的。換言之，一個(gè)凸錐K是有指向當(dāng)且僅當(dāng)它不包含任何直線。

定義0.2 假設(shè)錐K∈K(?n)，稱集合

為錐K 的對(duì)偶錐。從集合意義上說(shuō)，若內(nèi)積為歐氏內(nèi)積，則錐K∈K(?n)的對(duì)偶錐就是與K中任意向量夾角為銳角的向量組成的錐。

問(wèn)題1 給定實(shí)矩陣A∈M及錐K∈K(?n)，我們稱如下問(wèn)題為錐約束特征值問(wèn)題，具體形式為

n

求解λ∈?和非零向量x∈?n滿足

其中K+表示錐K∈K(?n)的對(duì)偶錐。特別地，下面兩種情況：

當(dāng)K=?n時(shí)，K+退化為零點(diǎn)，即K+={0}，(0.2)為如下形式

求解λ∈?和非零向量x∈?n滿足

此時(shí)錐約束特征值問(wèn)題稱為Pareto特征值問(wèn)題。如果存在非零向量x∈?n滿足(0.4)，則我們稱實(shí)數(shù)λ是給定實(shí)矩陣A∈Mn的一個(gè)Pareto特征值。相應(yīng)地，x 稱作實(shí)矩陣A對(duì)應(yīng)Pareto特征值λ的Pareto特征向量。實(shí)矩陣A∈Mn的Pareto特征值集合稱作A 的Pareto譜，記做σpareto(A )={λ∈?:(x ,λ)是問(wèn)題(0.4)的解}。

n

公式(0.4)也可以寫作如下形式：

+條件。

問(wèn)題2 給定實(shí)對(duì)稱矩陣A∈Mn，求解如下形式約束最優(yōu)化問(wèn)題：

由以上可知，普通的約束優(yōu)化問(wèn)題可以轉(zhuǎn)化為Pareto特征值問(wèn)題求解。

本文對(duì)如下問(wèn)題進(jìn)行研究：一是Pareto特征值的理論，包括給定實(shí)矩陣Pareto特征值界問(wèn)題和n維實(shí)矩陣Pareto特征值個(gè)數(shù)上界；二是對(duì)正矩陣Pareto特征值進(jìn)行討論，確定其最大最小Pareto特征值；三是引進(jìn)一類新矩陣Q-矩陣，討論它的部分理論性質(zhì)，且它的最大Pareto特征值可被直接計(jì)算。

1 預(yù)備知識(shí)

為方便讀者，在此我們把一些Pareto特征值相關(guān)知識(shí)做簡(jiǎn)單介紹(參見文獻(xiàn)[2～6])。我們對(duì)指標(biāo)集I?N，記I為集合I的勢(shì)，即I中元素個(gè)數(shù)。

若集合S??n，存在r＞0，使得B(x,r)=?S ，則稱x∈?n是S的內(nèi)點(diǎn)，S的所有內(nèi)點(diǎn)的集合成為S的內(nèi)部，記做int(S)。

若集合S??n，如果S∩B(x,r)≠?,?r＞0，則x稱為屬于S 的閉包，記做x∈S ；如果S=S, 則S稱為閉集。

對(duì)于如何求解Pareto特征值問(wèn)題，有如下定理：

定理1.1 (參見[2]) 假設(shè)A∈Mn，則λ∈?的一個(gè)Pareto特征值當(dāng)且僅當(dāng)存在非空指標(biāo)集I?N={1,2,…,n}和一個(gè)向量滿足是實(shí)矩陣A相應(yīng)于Pareto特征值λ的一個(gè)Pareto特征向量。

計(jì)算一個(gè)給定實(shí)矩陣A的Pareto特征值譜比求解其普通特征值譜更困難。我們可以看到(1.2)是求解其

的離散Fenchel共軛，?表示自然數(shù)集。

2 正矩陣Pareto特征值

則稱A 為正矩陣，記做A＞0。

同時(shí)，記

注 在與Pn有關(guān)的矩陣性質(zhì)中，我們可以放松Pn的矩陣類，由正矩陣放松為不可約非負(fù)矩陣。

對(duì)于正矩陣A∈Pn，有如下Perron定理：

定理 2.1 (Perron定理)[8]如果A∈Mn，且A＞0，則

ρ(A)＞0；

ρ(A)是A的一個(gè)特征值；

存在x∈?n且x＞0，Ax=ρ(A)x；

ρ(A)是矩陣A的代數(shù)重?cái)?shù)(和幾何重?cái)?shù))為1的特征值；

對(duì)λ≠ρ(A)，有|λ|＜ρ(A)，即ρ(A)是唯一的絕對(duì)值最大的特征值。

其中λ是正矩陣A 的普通特征值。 Perron定理指出：對(duì)于正矩陣A∈Pn有唯一的一個(gè)絕對(duì)值最大的單重正特征值ρ(A)，且相應(yīng)的特征向量x可以取為分量全部大于0的正向量，即 x＞0，Ax=ρ(A)x，我們稱ρ(A)為正矩陣A 的Perron特征值，并記做ρperron(A)。 由(0.4)可知，ρperron(A)也是矩陣A的一個(gè)Pareto特征值，x＞0是相應(yīng)的Pareto特征向量。接下來(lái)，我們討論給定正矩陣A∈Pn的Pareto特征值，記

3 實(shí)矩陣Pareto特征值界問(wèn)題

對(duì)一般實(shí)矩陣A∈Mn的Pareto特征值界，有如下性質(zhì)：

4 Q-矩陣Pareto特征值

在前面章節(jié)，我們討論了A∈Mn的最小Pareto特征值和最大Pareto特征值ρperron(A)以及一般矩陣的Pareto特征值界。同時(shí)，我們也對(duì)如下加邊矩陣的最大Pareto特征值感興趣。

定義 4.1 假定A,B,C,D是正矩陣，相應(yīng)的維數(shù)是n×n，m×n，n×m，m×m，我們稱正矩陣A的加邊矩陣

為列向量符號(hào)相同矩陣。因?yàn)槿我鈏∈N={1,2,…,n}，列向量Q(:,i)＞0以及i∈M={n+1,n+2,…,n+m}。

特別地，常數(shù)0α＞時(shí)，我們記列向量符號(hào)相同矩陣為

我們采用記號(hào)

首先來(lái)看一個(gè)引理。

相應(yīng)的Pareto特征向量可取為

證明 根據(jù)主子陣的選取，非空指標(biāo)集I可以分為三類：

主子陣普通特征值為-α, 相應(yīng)的全部正普通特征向量為0＜x∈?，又因?yàn)関＞0, 所以

即滿足定理2.2中條件(2.2)的子陣普通特征值和普通特征向量均不滿足中條件(2.3)。因此，此時(shí)不存在矩陣L的Pareto特征值；

其他情形

將其改寫為分塊形式

相應(yīng)的Pareto特征向量可取為

證明 根據(jù)主子陣的選取，非空指標(biāo)集I可以分為三類：

即滿足定理2.2中條件(2.2)的子陣普通特征值和普通特征向量均不滿足中條件(2.3)，因此，此時(shí)不存在矩陣Q的Pareto特征值；

其他情形

其中I'?N，J'?M。由定理4.2知，所有主子陣的λpareto,max(AII)都小于其所包含正矩陣AI'I'的最大普通特征值ρperron(AI'I')，再由單調(diào)性(2.4)知，

5 Pareto特征值個(gè)數(shù)上界問(wèn)題及數(shù)值結(jié)果

表1給出Mn(n∈{2,3,4,5})Pareto特征值個(gè)數(shù)上界(參見[2])，特別地，我們找到4×4和5×5分別有23和57個(gè)Pareto特征值的實(shí)矩陣，數(shù)值結(jié)果在表2中給出。這些矩陣全部都是Q-矩陣，Q-矩陣比其他類型矩陣可以具有更多的Pareto特征值。Pareto特征值個(gè)數(shù)比表2中πn更大的矩陣似乎是存在的，但目前為止，在數(shù)值計(jì)算中還沒有更好的結(jié)果。

表1 空間Mn(n∈{2,3,4,5})的Pareto特征值個(gè)數(shù)上界Tab.1 Bounds (1.6) for the Pareto capacity of spaces Mnforn∈{2,3,4,5}

6 結(jié)論及開放問(wèn)題

本文中，我們研究了Pareto特征值的理論，包括給定正矩陣的最大Pareto特征值和實(shí)矩陣Pareto特征值界問(wèn)題。特別地，我們引進(jìn)了一類新矩陣Q-矩陣，給出它的部分理論性質(zhì)，它的最大Pareto特征值可被直接計(jì)算。

表2 矩陣Q的Pareto特征值Tab.2 The Pareto eigenvalue associated with Q-Matrix

對(duì)正矩陣A∈Pn，有

其中A是矩陣L或Q中所含最大正順序子矩陣。

對(duì)n=4,5，Mn空間Pareto特征值個(gè)數(shù)界πn滿足

最后，我們提出一些開放問(wèn)題討論：

得到πn的精確值相當(dāng)困難。到目前為止，我們知道9≤π3≤10，23≤π4≤27和57≤π5≤71。 但不幸的是，我們并不知道π3，π4和π5的精確值，是否有方法可以改進(jìn)一個(gè)給定的n×n實(shí)矩陣，使其有更多的Pareto特征值？

我們發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象，如果Q-矩陣A的平方矩陣依然是一個(gè)Q-矩陣，則平方矩陣A2經(jīng)常比A 有更多的Pareto特征值，平方矩陣A2的性質(zhì)如何？其是否能夠幫助我們得到π的精確值？

n

[1] IUSEM A, SEEGER A. On convex cones with infinitely many critical angles[J].Optimization, 2007, 56: 115－128.

[2] PINTO D COSTA A, SEEGER A. Cone-constrained eigenvalue problems: theory and algorithms[J]. Computational Optimization and Applications, 2008, 45: 25-57.

[3] SEEGER A. Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions[J]. Linear Algebra and Its Applications,1999, 292: 1－14.

[4] SEEGER A, TORKI M. On eigenvalues induced by a cone constraint [J].Linear Algebra and Its Applications, 2003, 372: 181－206.

[5] SEEGER A, TORKI M. Local minima of quadratic forms on convex cones [J].Journal of Global Optimization, 2009, 44: 1－28.

[6] TAM B. The Perron generalized eigenspace and the spectral cone of a cone-preserving map[J]. Linear Algebra and Its Applications, 2004, 393: 375－429.

[7] LAVILLEDIEU P, SEEGER A. Existence de valeurs propres pour les systèmes multivoques: résultats anciens et nouveaux[J]. Annales des Sciences Mathématiques du Québec, 2000, 25: 47－70.

[8] HORN R A, JOHNSON C R. Matrix Analysis[M].Cambridge: Cambridge University Press, 1985.

[9] ADLY S, SEEGER A. A nonsmooth algorithm for cone-constrained eigenvalue problems, Computational Optimization and Applications[J/OL]. http://www.springerlink.com/content/nw01m1h01gv167v8/, 2009-11-24/2009-11/25.

The Pareto Eigenvalue Problem of Some Matrices

QI Ya-chao, CHEN Xiong-da
(Department of Mathematics, Tongji University, Shanghai 200092, P.R. China)

The Pareto eigenvalue problem(PEP) is an important prototype of cone-constrained problems, which exhibits already many of mathematical difficulties arising in the context of complementarity conditions involving the positive orthant. In this paper, we discuss some theoretical issues such as, the bound of Pareto eigenvalues for given matrices. A new kind of matrix is introduced and analyzed, namely, Q-matrix, whose largest Pareto eigenvalue can be estimated.

Pareto, cone-constrained, eigenvalue, nonnegative matrix, bordered matrix, complementarity

O 212

A

1001-4543(2010)01-0054-011

2009-12-24;

2010-03-01

齊亞超(1984－), 男, 河北人，碩士研究生，主要研究方向?yàn)榉蔷€性最優(yōu)化理論，電子郵件：qiyachao@gmail.com,陳雄達(dá)(1972－)，男，福建人，副教授，博士，主要研究方向?yàn)榉蔷€性最優(yōu)化理論，電子郵件： chenxiongda@yahoo.com。

國(guó)家自然科學(xué)基金(No.10671145)