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

幾種特殊矩陣的Pareto特征值問題

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

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

Pareto特征值；錐約束；特征值；非負矩陣；加邊矩陣；對偶錐

0 引言

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

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

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

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

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

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

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

n

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

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

當K=?n時，K+退化為零點，即K+={0}，(0.2)為如下形式

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

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

n

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

+條件。

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

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

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

1 預(yù)備知識

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

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

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

對于如何求解Pareto特征值問題，有如下定理：

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

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

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

2 正矩陣Pareto特征值

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

同時，記

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

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

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

ρ(A)＞0；

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

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

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

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

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

3 實矩陣Pareto特征值界問題

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

4 Q-矩陣Pareto特征值

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

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

為列向量符號相同矩陣。因為任意i∈N={1,2,…,n}，列向量Q(:,i)＞0以及i∈M={n+1,n+2,…,n+m}。

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

我們采用記號

首先來看一個引理。

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

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

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

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

其他情形

將其改寫為分塊形式

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

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

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

其他情形

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

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

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

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

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

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

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

對正矩陣A∈Pn，有

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

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

最后，我們提出一些開放問題討論：

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

我們發(fā)現(xiàn)一個有趣的現(xiàn)象，如果Q-矩陣A的平方矩陣依然是一個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ōu)化理論，電子郵件：qiyachao@gmail.com,陳雄達(1972－)，男，福建人，副教授，博士，主要研究方向為非線性最優(yōu)化理論，電子郵件： chenxiongda@yahoo.com。

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