数理解析研究所講究録 1241 巻 2001 年 109-117

109

Optimizing the largest eigenvalue of positive matrices having
their rows belonging to polytopes
関谷 和之 (Kazuyuki Sekitani )静岡大学工学部

Department of Systems Engineering, Shizuoka University
静岡大学工学部 岡崎 充高 (Mitsutaka Okazaki )Department of Systems Engineering, Shizuoka University

1

Introduction

Problem of minimizing the maximum real part of the eigenvalue of amatrix arises in avariety ofreal world, for example, stability analysis of control systems[ll], economic structure models[6]and so 0n[l0, 12].
Previous studies discuss an eigenvalue optimization problem whose optimal value is thelargest real eigenvalue, that is , the maximum real part of the eigenvalue is attained by areal
eigenvalue not acomplex one. Hence, the eigenvalue optimization problems impose proper
restrictions on amatrix, for example, symmetry and irreducibility. In other words, eigenvalue
optimization problem is to find amatrix among aclass of symmetric matrices or aclass of
positive matrices under an additional real constraints.
This study considers aclass of positive matrices whose row vectors are defined by several linear inequalities. The main aim of this study is to develop an algorithm for minimiz$\mathrm{i}\mathrm{n}\mathrm{g}/\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{i}\mathrm{n}\mathrm{g}$the largest eigenvalue of apositive matrix whose row vector belongs to aeach

polytope.
We omit the almost all proofs of lemmas and theorems in the sequel. The details can befound in [5]2Frobenius’s Theorems and multiffactional problems. Let $I=$
For every positive matrix $X$ , the largest eigenvalue of $X$ is denoted by
$X$
$i\in
I$
$\{1,2, \ldots, n\}$ .
all. We canbyfordenotedisof orderTherow vector of
$i\in
I$
$X$
, where C’ is somefor allrow vector of assider aperturbation of thefor all $i\in I$ .
matrix and is some row vector. The polyhedron $\{x|xC^{i}\leq b^{i}\}$ is denoted by$X$
We put the following assumption in order to keep the matrix consisting of rows
positive.
$\Lambda(X)$$i^{th}$$n$$x_{i}$$x{}_{i}C^{i}\leq b^{i}$$i^{th}$$x_{i}$$S^{i}$$b^{i}$$\{x_{1}, \ldots, x_{n}\}$Assumption 1Assume that the polyhedronorthant offor all i .
$R^{n}$$S^{i}$

is a nonempty bounded set in the positive$\in I$is apolytope. For every positive
Since is apolytope for all $i\in I$ , the product set. From Frobenius’ theorem [6],matrix $X$ , the largest eigenvalue of $X$ is denoted by .
for all $i\in I$ . We consider apair of the. By $X\in\Pi S^{i}$ ,is areal function on$S^{i}$$\square _{i\in I}S^{i}$$\Lambda(X)$$\Lambda(X)$$x_{i}\in S^{1}$$\Pi_{i\in I}S^{i}$following two problems:and$\min_{X\in\Pi S}.\cdot\Lambda(X)$(1)$x \in\Pi\max_{S^{j}}\Lambda(X)$

(2)

110
as the problem of finding the bounds for the largest eigenvalue of $X$ with perturbed rows. Then
we have the existence of optimal solutions of Problem (1) and Problem (2) as follows:

Theorem 2.1 Each of Problem (1) and Problem (2) has a real optimal solution.

From Frobenius’ theorem [6], we have$\Lambda(X)=\max_{w>0}\min\{\frac{x_{1}w}{w_{1}}$, ...,$\frac{x_{n}w}{w_{n}}\}=\min_{w>0}\max\{$$\frac{x_{1}w}{w_{1}}$, ...,$\frac{x_{n}w}{w_{n}}\}$

for all.Therefore, we can transform Problem (1) and Problem (2) into the following
two multifractional problems:$X\in\Pi_{\dot{|}\in I}S|.$$\min$$\max$s.t.

w $>0$ and X$\max$$\min$(3)$\{\begin{array}{lll}-\underline{x}w arrow x\underline{w}w_{1} \cdots x_{\mathrm{L}}\end{array}\}$$\in\Pi S^{i}$

and

s.t.

(4)

$\{\begin{array}{llll}-\underline{x}w -x_{\mathrm{A}}\underline{w}w_{1} \cdots ’ x_{\hslash}\end{array}\}$w $>0$ and X $\in\Pi S$ :respectively.
th Problem (3) and Problem (4) have homogeneous ratios of asingle variable
to abilinear term $x:w$ .
Let
be the vertex set of for all $:\in I$ , then the polytope
is the convex hull of .
We consider two following problem for any positive vector :$\mathrm{B}.0$$\mathrm{n}$$w.\cdot$$S^{:}$$V^{\dot{1}}$$S^{\dot{1}}$$V^{\dot{1}}$$w$$\min_{X\in \mathrm{n}s}.\max\{\frac{x_{1}w}{w_{1}}$and$\max\{\min_{x_{1}\in V^{1}}\frac{x_{1}w}{w_{1}}$Lemma 2.1 For any positive vector
the following pmblem:$w$,$\frac{x_{n}w}{w_{n}}\}$(5)$x \min_{\in nV^{n}}\frac{x_{n}w}{w_{n}}\}$(6)\ldots ,, ...,, the optimal value of Problem (5) is equal to that of$\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$,$\ldots,x\min_{n\epsilon S^{n}}\frac{x_{n}w}{w_{n}}\}$

Proof.
Choose $w>0$ arbitrarily. Assume that$\min_{X\in\Pi S}.\cdot\max\{\frac{x_{1}w}{w_{1}}$, . ..,$\frac{x_{n}w}{w_{n}}\}\neq\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$, ... ’

$x \min_{\in nS^{n}}\frac{x_{n}w}{w_{n}}\}$.

Let :be an optimal solution of $\min_{X\in\Pi S}:(x_{1}.w)/w$:for all $i\in I$ , then it follows from$\tilde{x}$$\Pi S^{}$that$\min_{X\in\Pi S^{j}}\max\{\frac{x_{1}w}{w_{1}}$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}$,,$\leq$$\max\{\frac{\tilde{x}_{1}w}{w_{1}}$$=$$\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$$\ldots$$\frac{\tilde{x}_{n}w}{w_{n}}\}$, ...,$x \min_{\in nS^{n}}\frac{x_{n}w}{w_{n}}\}$$\{\begin{array}{l}\tilde{x}_{1}\vdots\tilde{x}_{n}\end{array}\}$

$\in$

111
ana nence,$\min_{X\in\Pi S^{i}}\max\{\frac{x_{1}w}{w_{1}}$Let$\hat{X}$,,$\ldots$

be an optimal solution of$\frac{x_{n}w}{w_{n}}\}<\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$$\min_{X\in\Pi S}:\max\{^{\underline{x}}w_{1}\mapsto w$$\min_{X\in\Pi S^{i}}\max\{\frac{x_{1}w}{w_{1}}$for all $i\in I$ . Since$\hat{x}_{i}\in S^{i}$,$\ldots$,,$\ldots$

,

,

(7)

$\ldots,\min_{x_{n}\in S^{n}}\frac{x_{n}w}{w_{n}}\}$$\frac{xw}{w_{n}}\}$, then,(8)$\frac{x_{n}w}{w_{n}}\}\geq\frac{\hat{x}_{i}w}{w_{i}}$for all $i\in I$ , it follows from (8) that$\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$, . ..,$x \min_{\in nS^{n}}\frac{x_{n}w}{w_{n}}\}$,,$\frac{\hat{x}_{n}w}{w_{n}}\}$$\leq$$\max\{\frac{\hat{x}_{1}w}{w_{1}}$$\leq$$\min_{X\in\Pi S’}\max\{\frac{x_{1}w}{w_{1}}$$\ldots$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}$and hence$\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$, ...,$x \min_{\in nS^{n}}\frac{x_{n}w}{w_{n}}\}<\min_{X\in\square S^{i}}\max\{\frac{x_{1}w}{w_{1}}$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}$.

(9)

From (7) and (9), it is acontradiction.

$\square$

Then we have the following theorem:
Theorem 2.2 The optimal value of Problem (1) is equal to that of the following problem:$\min_{w>0}\max\{\min_{x_{1}\in V^{1}}\frac{x_{1}w}{w_{1}}$Proof.
It follows from Lemma 2.1 and$\min_{X\in\Pi s:}\max\{\frac{x_{1}w}{w_{1}}$, . .. ’term
Since thefeasible region is the polytope. Therefore, we have$i^{th}$$V^{i}\subseteq S^{i}$$\frac{x_{n}w}{w_{n}}\}$,.

$\min_{x_{1}\in V^{n}}\frac{x_{n}w}{w_{n}}\}$\ldots ,(10)that for problem (6)and (5)$=$$\max\{\min_{x_{1}\in S^{1}}\frac{x_{1}w}{w_{1}}$$\leq$$\max\{\min_{x_{1}\in V^{1}}\frac{x_{1}w}{w_{1}}$,$\ldots$,$\ldots$,$\min_{x_{n}\in S^{n}}\frac{x_{n}w}{w_{n}}\}$,$\min_{x_{n}\in V^{n}}\frac{x_{n}w}{w_{n}}\}$.

of Problem (6) is alinear programming problem whose, it has an optimal solution which belongs to the vertex set$\min_{x_{i}\in V}:(x_{i}w)/w_{i}$$S^{i}$$V^{i}$(11)$\min\underline{x_{i}w}--\mathrm{m}.\mathrm{n}\underline{x_{i}w}$$x_{i}\in V:w_{i}$$x_{i}\in S^{i}w_{i}$for all $i\in\{1, \ldots, n\}$ . This implies that$= \min_{w>0}\min_{X\in\Pi s:}\max\{\frac{x_{1}w}{w_{1}}$$\min_{X\in\Pi s:}\mathrm{A}(X)$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}=\min_{w>0}\max\{\min_{x_{1}\in V^{1}}\frac{x_{1}w}{w_{1}}$,$\ldots,\min_{x_{n}\in V^{n}}\frac{x_{n}w}{w_{n}}\}$.
$\square$

Theorem 2.3 The optimal value of Problem (2) is equal to that of the following problem:$\max_{w>0}\min\{\min_{x_{1}\in V^{1}}\frac{x_{1}w}{w_{1}}$,$\ldots$,$\min_{x_{1}\in V^{n}}\frac{x_{n}w}{w_{n}}\}$

.

(12)

112
3Coloring matrix and algorithms
Firstly, we will define “coloring matrix” for matrix of order which is similar to abasis matrix
of a linear programming as follows: Amatrix of order is called a coloring matrix if therow vectorof is avertex of
for all $i\in I$ , i.e., $a:\in V^{i}$ for all $i\in I$ . By solving
Problem (10) and Problem (12), we will find an optimal solution of Problem (1) and Problem(2), respectively. The following lemma states that acoloring matrix attaining the optimal valueof Problem (10) is also an optimal solution of Problem (1).
Lemma 3.1 There is a coloring matrix whose largest eigenvalue is the optimal solution of
Problem (1). Let
be an optimal solution of Problem (10). Then is a positive largest
eigenvector of .
$n$

$A$

$i^{th}$$a_{\dot{1}}$

$A$

$n$

$S^{\dot{1}}$$(\overline{w},\overline{X})$$\overline{w}$$\overline{X}$

If acoloring matrix has the largest eigenvalue that is equal to the optimal value of Problem(1), it is called the optimal coloring matrix for Problem (1). We have the following property
for an optimal solution of Problem (10).
Theorem 3.1 Let
be an optimal coloring matrix for Problem (1). Then,
is an
optimal solution of Problem (10) if and only if is a positive largest eigenvector of .
From Lemma (3.1) and Theorem (3.1) we have only to find the least largest eigenvalue of acoloring matrix among those of all the coloring matrices. We develop the following algorithm:
Algorithm for Problem (1)
StepO Choose apositive vector
and set $=1$ .
Stepl Find an optimal solution
and the optimal value . of$\min_{x.\in S}:(x:w^{k-1})/w_{}^{k-1}$ for every $:\in I$ . Let.
Step2 Find the largest eigenvalue Aand alargest eigenvector of
Step3 If
, thenand Aare an optimal coloring matrix and the optimalvalue of Problem (1), respectively and stop. Otherwise let,and$k=k+1$ and go to Step 1.
The algorithm has the following properties:
Lemma 3.2
for k $=1,$ 2,$\overline{X}$$(\mathrm{w},\mathrm{X})\overline{X})$$w-$$w^{0}$$\overline{X}$$k$$x_{}^{k}\in V^{i}$$\gamma_{*}^{k}$$X^{k}=[x_{1}^{kT}, \ldots,x_{n}^{kT}]^{T}$$X^{k}$$\hat{w}$$\mathrm{A}\geq\max_{\dot{|}\in I}\gamma_{i}^{k}$$X^{k}$$\mathrm{A}_{k}=\mathrm{A}$$w^{k}=\hat{w}$$\mathrm{A}_{k+1}<\mathrm{A}_{k}$\ldots .

Lemma 3.3$\min_{j\in I}\gamma_{\dot{1}}^{k}$$\leq \mathrm{A}$$\leq\max:\in I\gamma_{}^{k}$for k $=1,$ 2,\ldots .

Lemma 3.4 $Sup\mu se$ that A
Step3, thenthe least largest eigenvalue among those of all the coloring matrices.
$\geq\max:\in I\gamma_{i}^{k}in$$\min_{\dot{|}\in I}\gamma_{i}^{k}=\mathrm{A}$$= \max:\in I\gamma_{i}^{k}$and Ais

Theorem 3.2 The coloring algorithm for Problem (1) provides its optimal solution after

finite number of iterations.

$a$Replacing $\min/\max$ with $\max/\min$ in the definition of . of Step 1and the stopping criteriaof Step 3, we obtain the same algorithm for Problem (2) as the above one and we can show
the similar properties to the above lemmas and theorem.
Algorithm for Problem (2)$\gamma_{*}^{k}$

StepO
Stepl

and set $k=1$ .
and the optimal valueof$\max_{x:\in S}:(x:w^{k-1})/w_{j}^{k-1}$ for every $i\in I$ .
Let
Find the largest eigenvalue A and alargest eigenvector of
If A, thenand Aare an optimal coloring matrix and the optimalvalue of Problem (2), respectively and stop. Otherwise let,and$k=k+1$ and go to Step

Choose apositive vector
Find an optimal solution$w^{0}$$x_{}^{k}\in V^{:}$$\gamma_{\dot{1}}^{k}$$X^{k}=[x_{1}^{kT}, \ldots, x_{n}^{kT}]^{T}$

Step2
Step3

$\hat{w}$$\leq\min_{j\in I}\gamma_{}^{k}$$X^{k}$$X^{k}$$\mathrm{A}_{k}=\mathrm{A}$$w^{k}=\hat{w}$113of the proposed algorithm for Problem (2) have the similar properties to
The iterates
those in Lemma 3.2 and Lemma 3.3.
The algorithm has the following properties:$\{\mathrm{A}_{\ovalbox{\tt\small REJECT}_{\ovalbox{\tt\small REJECT}}}\}$

for $k=1,2$ ,Lemma 3.5$\mathrm{A}_{k+1}>\mathrm{A}_{k}$Lemma 3.6$\min_{:\in I}\gamma_{i}^{k}\leq \mathrm{A}$$\ldots$$\leq\max_{\grave{|}\in I}\gamma_{i}^{k}f$.

or $k=1,2$ ,$\ldots$.

, thenLemma 3.7 Suppose thatall
the coloring matrices.
largest largest eigenvalue among those of$\min_{i\in I}\gamma_{i}^{k}=\mathrm{A}$$\mathrm{A}\leq\max_{i\in I}\gamma_{i}^{k}$$= \max_{i\in I}\gamma_{i}^{k}$. That is, Ais the

Theorem 3.3 The proposed algorithm for Problem (2) provides its optimal solution after
finite number of iterations.

$a$

4Duality of the largest eigenvalue estimation problems
We define$(w)=$\min_{X\in\Pi s:}\{\frac{x_{1}w}{w_{1}}$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}$

and$\mathrm{w})=x\in\Pi\max_{S^{i}}\{$ $\frac{x_{1}w}{w_{1}}$,$\ldots$,$\frac{x_{n}w}{w_{n}}\}$and consider the following two multifractional problem:$\max_{w>0}$$\min_{w>0}$$\Phi(w)$

(13)

and

(14)

$\Psi(w)$

The following theorem states the weak duality between Problem. (1) and Problem (13)Theorem 4.1 For every positive vector rp and for every matrix
and a positive vector. Furthermore, there are a matrix$X\in\Pi S_{f}^{i}$$\overline{X}\in\square S^{i}$$\Lambda(X)$$\Lambda(\overline{X})$$\overline{w}$.

we have $(w)\leq
such that $(w)=We call Problem (13) adual problem of Problem (1)Corollary 1An optimal solution of Problem (13) is unique up to scalar multiplication.

The following theorem provides the same results between Problem (2) and Problem (14) asthat between (1) and Problem (13).
Theorem 4.2 For every positive vector rp and for every matrix $X\in\Pi S^{i}$ , we have $(w)\geq
and a positive vector such that $(w)=. Furthermore, there are a matrix$\overline{X}\in\Pi S^{i}$$\Lambda(X)$$\overline{w}$$\Lambda(\overline{X})$Corollary 2An optional solution of Problem (14) is unique up to scalar multiplication.

5Numerical experiments
We now give asummary of our computational experiments with the proposed algorithm.
be agiven set of finite -dimensional row vectors for all $i\in I$ . In this section weLetis the convex hull of the given set of for all $i\in I$ . Then we can simplify theconsider that
, $(x_{i}w^{k-1})/w_{i}^{k-1}$ in Step 1of
proposed algorithm for Problem (1) as follows: Replacing
the proposed algorithm for Problem (1) with $\min_{x:\in P}:(x_{i}w^{k-1})/w_{i}^{k-1}$ , we have the proposed$P^{i}$$n$$S^{i}$$P^{\dot{1}}$$\min_{x:\in S}$

114
algorithm for Problem (1). All steps of the proposed algorithm and we have set tolerance of a
stopping criteria in the power method as $1.0\cross 10^{-7}$ .
is the convex hull of
Since
for all $i\in I$ , an equivalent formulation of $\max_{w>0}\Phi(w)$ is
as follows:$S^{i}$$P^{\dot{1}}$$\max_{w>0}\min\{\min_{x_{1}\in P^{1}}\frac{x_{1}w}{w_{1}}$,$\ldots,\min_{x_{n}\in P^{n}}\frac{x_{n}w}{w_{n}}\}$

.

(15)

Problem (15) is alinear fractional problem withratios that is discussed von Neumann[7] and Crouzeix, Ferland and Schaible [8]. We can apply some algorithms of the linear fractional
programming to Problem (15) which is the dual problem of Problem (1).
Let be avector of all ones. From Corollary 2we can add aconstraint $e^{T}w=1$ to Problem(15) without loss of generality. Notice that Problem (15) with the additional constraint $e^{T}w=1$
has aunique optimal solution. Hence, we can solve the dual problem (15) of Problem (1) byaDinkelbach-type algorithm due to Borde and Crouzeix [4] that converges super-linearly for
Problem (15) with the additional constraint $e^{T}w=1$ . The Dinkelbach-type algorithm is asfollows:$\sum_{:\in I}|\dot{P}|$$e$

StepO Choose apositive vector$w^{0}$and set$\eta_{1}=\min\{\min_{x_{1}\in P^{1}}\frac{x_{1}w^{0}}{w_{1}^{0}}$,$x \min_{\in\hslash P^{n}}\frac{x_{n}w^{0}}{w_{n}^{0}}\}$$\ldots,$and set $k=1$ .
Stepl Solve$\min\{\min_{x_{1}\in P^{1}}\frac{x_{1}w-\eta_{k}w_{1}}{w_{1}^{k-1}}$$w>0 \max$, ...,$x \min_{n\epsilon P^{n}}\frac{x_{n}w-\eta_{k}w_{n}}{w_{n}^{k-1}}\}$

.

(16)

$e^{T}w=1$

and let$w^{k}$

and$\xi_{k}$be an optimal solution and an optimal value, respectively.

Step2 If $\xi_{k}=0$ , then stop:andrespectively. Otherwise let$\eta_{k}$$w^{k}$

is an optimal value and solution of Problem (15) ,$\eta_{k+1}=\min\{\min_{x_{1}\in P^{1}}\frac{x_{1}w^{k}}{w_{1}^{k}}$,$\ldots,x_{n}\min_{\in P^{n}}\frac{x_{n}w^{k}}{w_{n}^{k}}\}$

k $=k$ 1 1 and go to Step 1.

In Step 1of the Dinkelbach-type algorithm we solve the linear programming problem (16) withthe coefficient matrix multiplied by the iterates . This means that we must pay sufficientattention to the numerical error in pivoting process and evaluating the reduced cost. All stepsof the algorithm except for Step 1has been implemented inand the linear programmingof Step 1is solved by the commercial source code Xpress-MP in order to avoid the numericalerrors. Tolerance of astopping criterion of both Xpress-MP and Step 2are set as $5.0\cross 10^{-7}$ .
Two programs were run on Sun Ultra-l with double precision arithmetic. The study conducts afactorial experiment in which each treatment has 10 replications. Factors
used in this numerical experiment are summarized in the following manner$\eta_{k}$$\mathrm{C}$$3\cross 3\mathrm{x}3$

115
Type of$\Pi_{i\in I}P^{i}$is generated as follows: For all $i\in I$ , choose $m$ points
Typel The first type ofrandomly from $\{x|x\in R^{n}, 0<x\leq \mathrm{e}\}$ and set
are positive and that at least one element, $m$ }. Note that all row vectors of,
is modeledof each row vector is 1. The coloring matrix of this product set
[9].
of
DEA
matrixefficiency
crossafter the$u_{i}^{J}$$\Pi_{i\in}{}_{I}P^{i}$$P^{i}=\{u_{i}^{jT}/||u_{i}^{j}||_{\infty}|j=$$(\mathrm{j}=1, \ldots,\mathrm{m})$$1$$P^{i}$$\ldots$$\Pi_{i}{}_{\in I}P^{i}$is generated as follows: First, we have generated $m$
Type2 The second type ofof$(k=1,\ldots,m)$ such that for all $i<j$ the element
reciprocal matrices
are chosen uniformly at random from {1/7, 1/5, 1/3, 1, 3, 5, 7}, androw vector ofis given as aset of theand $x_{ii}^{k}=1$ for all $i\in I$ . Next,
is similar to theset
product
thisof$m$, . The coloring matrix
for $k=1$ ,pairwise comparison matrix of AHP[10].
$\Pi_{i\in I}P^{i}$$X^{k}$$x_{ij}^{k}$$x_{ij}^{k}=1/x_{j}^{k}\dot{.}$$X^{k}$$i^{th}$$P^{i}$$X^{k}$$\Pi_{i\in}{}_{I}P^{i}$$\ldots$

is generated as follows: First, we have generated $m$
Type3 the third type ofstochastic matrices $X^{k}(k=1, \ldots, m)$ such that each column is randomly chosen
is given as the set offrom { $x|e^{T}x=1$ , $x_{i}>0$ for all $i\neq k$ , and $x_{k}=0$ }. Next,
the diagonal$m$coloring, . For all
for $k=1$ ,row vector oftheelements are zero.
$\Pi_{i\in}{}_{I}P^{i}$$P^{i}$$X^{k}$$i^{th}$$\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s},\mathrm{a}\mathrm{l}\mathrm{l}$$\ldots$

Matrix size (n) 5,10, and 40
Number of points in $P^{i}(m):$ 4,8 and 16.
Table 1: Number of iterations in our algorithm
method$(\#\mathrm{C})$and Number of iterations in the Power$(\#\mathrm{P})$

4

8

16

$\frac{\#\mathrm{C}\#\mathrm{P}}{2.26.9}$$\frac{\#\mathrm{C}\#\mathrm{P}}{2.36.7}$$\frac{\#\mathrm{C}^{1}\# 1^{\mathrm{J}}}{2.76.5}$$\mathrm{m}$$\mathrm{n}=5$$\mathrm{n}=10$$\mathrm{n}=40$

Type 1
Type 217.7
Type 316.5
Type 16.1
Type 219.0
Type 310.5
Type 15.3
Type 218.8
Type 36.0

16.7
15.8
6.3
18.6
10.2
5.2
19.0
6.0

Table 2: Number of iterations in the proposed algorithm
the Dinkelbach-type algorithm$(\#\mathrm{D})$$(\#\mathrm{C})$

2.3
2.8
2.2
2.7
2.7
3.0
3.4
3.0

16.3
19.0
6.2
18.3
10.9
5.0
17.8
6.0

and Number of iterations in

116$\frac{\mathrm{m}4816}{\frac{\#\mathrm{C}\#\mathrm{P}}{2.24.2}\frac{\#\mathrm{C}\#\mathrm{P}}{2.34.0}\frac{\#\mathrm{C}\#\mathrm{P}}{2.74.0}}$

Type 1
Type 22.6 9.0
Type 32.4 4.2
Type 12.4 4.0
Type 22.9 9.0Type 32.6 4.8Type 12.5 4.0
Type 22.9 18.8
Type 32.8 4.4$\mathrm{n}=5$$\mathrm{n}=10$$\mathrm{n}=40$

2.3 9.2
2.5 4.0
2.1 4.0
2.9 12.2
3.1 5.0
2.6 4.0
3.0 17.0
3.0

4.1

2.3
2.8
2.2
2.7
2.7
3.0
3.4
3.0

8.6
4.0
4.0
12.2
4.6
4.0
16.7
4.0

The same initial point $e/n$ is given to the both algorithms. Table 1reports the average numberof iterations in the proposed algorithm and the average number of iterations in the power
method.
We see from Table 1that the proposed algorithm converges within 4iterations in all cases.
From Table 1we see that the number of iterations in the proposed algorithm is independentof the matrix-size and the number of the points infor all types.
There are large difference of the average number of iterations in power method between
Type 1and the other types in the small matrix-size. The power method converges withinseveral iterations for all cases in Type 1but it converges within about 18 iterations in Type 2
and 3for the small matrix-size. The number of iterations in the power method is much effectedby the distribution of. For Type 3, the average number of iterations in the power
method is in inverse proportion to the matrix-size. For all types the number of iterations in
the power method does not increase for the matrix-size and the number of points.
The proposed algorithm and the Dinkelbach-type algorithm generate an eigenvalue problem
and alinear programming problem as subproblem in each iteration, respectively, and the sizeof the coloring matrix is almost equal to that of the basis matrix in the linear programming
problem of the Dinkelbach-type algorithm.
Table 2reports the average number of iterations in the Dinkelbach-type algorithm and the
proposed algorithm forexperiments. Since the numbers of iterations is coincide with thenumber of subproblems, the number of subproblems in the proposed algorithm is always lessthan that in the Dinkelbach-type algorithm. Especially, in Type 1, the proposed algorithm
has less number of subproblems than the Dinkelbach-type algorithm. If the computational
complexity of solving the subproblem in the Dinkelbach-type algorithm, the computational
complexity of the proposed algorithm is comparable with that of the Dinkelbach-type algorithm.
In fact, we may say from Table 1that solving the subproblem in the proposed algorithm is as
efficient as that in the Dinkelbach-type algorithm.
$P^{\dot{\mathrm{s}}}$$\in P^{\dot{1}}$$x_{\dot{1}}$$3^{3}$

6Extension and further research
In this study, we propose the algorithm for optimizing the largest eigenvalue of amatrix withlinearly perturbed row vectors. For agiven -squared symmetric matrix, $m$ ,
and $i=0$ ,Jarre consider the affine space generated by,,:$X^{:}$$n$$\ldots$$X^{0}$$\ldots$$S= \{X^{0}+\sum_{=1}^{m}\mu:X:|\mu:\in R$

Let $\mu=[\mu_{1}, \ldots,\mu_{m}]$ andlem is as follows:$\mathrm{Y}(\mathrm{p})=X^{0}+\sum_{\dot{|}=1}^{m}\mu_{\dot{1}}X:$$X^{m}$, $i=1$ ,$\ldots$, $m\}$ .

, then largest eigenvalue optimization prob-$\inf\{\Lambda(\mathrm{Y}(\mu))|\mu\in R^{m}\}$.

117
Jarre develop an interior-point algorithm [3] to finding the lower bound of the largest eigenvalue.
In further research, we will consider the largest eigenvalue optimization problem with thematrix set that is similar to that of Jarre’s study as follows:$S= \{_{j}\sum_{=1}^{m}\mu_{i}X^{i}|\sum_{i=1}^{m}\mu_{i}=1$,$\mu_{i}\geq 0i=1,\ldots$

,

$m\}$

.

i
is convex set of amatrices $\{X^{1}, \ldots, X^{m}\}$ . We only assume that
This matrix set
optimization$m$eigenvalue, . In order to solve the largest
apositive matrix for all $i=1$ ,problem with the matrix set , we will develop the similar algorithm to the coloring algorithm.
On computational experiments, we will compare the algorithm with the Jarre ’s algorithm.
$X^{\dot{1}}$$S$$\mathrm{s}$$\ldots$$S$

References[1] A.TAKAYAMA, Mathematical Economics, Cambridge University Press,Cambridge 1985

finding the existence range of the principal eigenvalue of a positive matrix including some uncertain data ,5th Japan-Korea Join Workshop on Algorithms
and Computation ,17-24 (July 21,2000)[2] K.SEKITANI, Algorithm[3] F.JARRE, An interior-point method for minimizing the maximum eigenvalue of a linear
combination of matrices ,SIAM J. CONTROL AND OPTIMIZATION Vol. 31, No. 5
September 1993,1360-1377[4] BoRDE,J.,CROUZEIX, J. P.(1987), Convergence of a Dinkelbach-Type Algorithm in Generalized Fractional Programming. ’Zeitcshrift fiir Operations Research 31, 31-54[5] SEKITANI. K.(2000), Frobenius’ Theorem and its related topics: Estimating the principal eigenvalue of a positive matrix including uncertain data. ,ISM Reports on StatisticalComputing 33,29-46,Zeitcshrift fiir Operations Research 31, 31-54[6] TAKAYAMA.A.(1985), Mathematical Economics.
bridge.

Cambridge University Press, Cam-

[7] VON NEUMANN, J. A.(1945): A Model of General Economic Equilibrium. Review of
Economic Studies 13,1-9.
[8] Crouzeix, J. P.,FERLAND, J. A., SCHAIBLE, S.(1983): Duality in Generalized Linear
Fractional Programming. Mathematical Programming 27, 1382-1403[9] SEXTON, T. R., SILKMAN, R. H., HOGAN. A. J.(1986): Measuring Efficiency: Assessment of Data Envelopment Analysis. R. H. Silkman, ed., Data Envelopment Analysis:
Critique and Extensions. 73-105. Jossey Bass, San Francisco[10] SAATY. T. L. (1996): The Analytic Hierarchy Process, second ed. RWS Publications,
Pittsburgh[11] C. J. GOH, K. L. TEQ. (1988): On Minimax Eigenvalue Problem via Constrained
Optimization. ’Journal of Optimization Theory and Applications: vol. 57,no,l, April[12] MORISHIMA, M. (1964): Equilibrium, Stability and Growth. ’Oxford University Press,

Oxford