# A Generalized Inexact Newton Method for Inverse Eigenvalue Problems

Authors: Weiping Shen
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We propose a generalized inexact Newton method for solving the inverse eigenvalue problems, which includes the generalized Newton method as a special case. Under the nonsingularity assumption of the Jacobian matrices at the solutionc*, a convergence analysis covering both the distinct and multiple eigenvalue cases is provided and the quadratic convergence property is proved. Moreover, numerical tests are given in the last section and comparisons with the generalized Newton method are made.


---

## Body

## 1. Introduction

Inverse eigenvalue problems (IEPs) arise in a remarkable variety of applications such as geophysics, control design, system identification, exploration and remote sensing, principal component analysis, molecular spectroscopy, particle physics, structural analysis, circuit theory, and applied mechanics. One may refer to [1–14] for the applications, mathematical theory, and algorithms of IEPs. Based on different applications, inverse eigenvalue problems appear in many forms, for example, additive inverse eigenvalue problems, multiplicative inverse eigenvalue problems, Jacobian matrix inverse eigenvalue problems, nonnegative matrix inverse eigenvalue problems, and Toeplitz matrix inverse eigenvalue problems [3, 15, 16].Let𝒮 be the linear space of symmetric matrices of size n. Let A
:
ℝ
n
→
𝒮 be continuously differentiable. Given n real numbers {
λ
i
*
}
i
=
1
n, which are arranged in the decreasing order λ
1
*
≤
λ
2
*
≤
⋯
≤
λ
n
*, the IEP considered here is to find a vector c
*
∈
ℝ
n such that
(1)
λ
i
(
c
*
)
=
λ
i
*
for
each
i
=
1,2
,
…
,
n
.
The vector c
* is called a solution of the IEP (1). A typical choice for A
(
c
) is
(2)
A
(
c
)
∶
=
A
0
+
∑
i
=
1
n
‍
c
i
A
i
,
which has been studied extensively (cf. [15, 17–20]).Define the functionf
:
ℝ
n
→
ℝ
n by
(3)
f
(
c
)
=
(
λ
1
(
c
)
-
λ
1
*
,
λ
2
(
c
)
-
λ
2
*
,
…
,
λ
n
(
c
)
-
λ
n
*
)
T
=
(
λ
1
(
c
)
-
λ
1
*
,
λ
2
(
c
)
w
λ
2
*
)
T
for
any
c
∈
ℝ
n
.
Then solving the IEP (1) is equivalent to solving the equation f
(
c
)
=
0 on ℝ
n. Based on this equivalence, Newton’s method can be applied to the IEP, and it converges quadratically [15, 16, 21]. However, distinction of the given eigenvalues is usually assumed among these works. In the case when multiple eigenvalues are present, solving the IEP becomes much more complicated because the eigenvalue function f defined by (3) is not differentiable around the solution c
*, in general, and the eigenvectors {
q
i
(
c
)
} corresponding to the multiplier value cannot generally be defined as a continuous functions of c at c
*; see [15]. Therefore, either Newton’s method or the theoretical analysis may get into trouble. In paper [15], the authors have analyzed the convergence properties of Newton's method in the multiple case. However, the nonsingularity assumption needed for convergence in [15] was that the inverse of the involved Jacobian and/or the involved approximate Jacobian matrices at all iterations {
c
k
} are bounded, and the bound must be independent of the initial point c
0. For ensuring this nonsingularity assumption for Newton's method, D. Sun and J. Sun introduced in [22] a generalized Newton method and, by using the tool of the strong semismoothness of the eigenvalue function for symmetric matrices, developed a new approach to study the convergence issue for the case with multiple eigenvalues. They presented there a nonsingularity assumption in terms of the Jacobian matrices evaluated at the solution c
* to establish a general convergence result of Newton's method. Note that in each Newton iteration (outer iteration) of the generalized Newton method, we need to solve exactly the Jacobian equation (inner iteration). When the problem size n is large, the inversion is costly, and one may employ iterative methods to solve the equation. Although iterative methods can reduce the complexity, it may oversolve the systems in the sense that the last few inner iterations before convergence may not improve the convergence of the outer Newton iteration. The generalized inexact Newton method is a method that stops the inner iteration before convergence. By choosing a suitable stopping criterion, we can reduce the total cost of the whole inner-outer iteration.In this paper, we give a generalized inexact Newton method for solving the IEP (1) which can reduce the generalized Newton method. Motivated by Sun’s idea of the strong semismoothness, we give a convergence analysis of this method. By choosing a suitable stopping criterion, we show that the generalized inexact Newton method converges superlinearly. It should be noted that the analysis of the present paper is “distinction free.” Though the nonsingularity assumption is stated in terms of the Jacobian matrices evaluated at the solution c
*, the inverse of the approximate Jacobian matrices related to all iterations {
c
k
} is ensured to be bounded and moreover the upper bound is independent of the initial point c
0. A numerical example is presented in the last section to illustrate that our results and comparisons with the generalized Newton method are made.


## 2. Semismoothness and Relative Generalized Jacobian

Letg
:
ℝ
n
→
ℝ
m be a locally Lipschitz continuous function. Then, according to Rademacher’s theorem, g is differentiable almost everywhere. Let D
g be the set of differentiable points of g and let g
′ be the Jacobian of g whenever it exists. Denote
(4)
∂
B
g
(
x
)
∶
=
{
V
∈
ℝ
m
×
n
∣
V
=
lim
⁡
x
k
→
x
g
′
(
x
k
)
,
x
k
∈
D
g
}
.
Then Clarke’s generalized Jacobian [23] is
(5)
∂
g
(
x
)
=
conv
{
∂
B
g
(
x
)
}
,
where “conv” stands for the convex hull in the usual sense of convex analysis [24]. Then we are ready to give the following definition of semismoothness. For original concept of semismoothness for functions and vector-valued functions, one may refer to [25, 26].Definition 1.
Suppose thatg
:
ℝ
n
→
ℝ
m is a locally Lipschitz continuous function. g is said to be semismooth at x
∈
ℝ
n if g is directionally differentiable at x and for any V
∈
∂
g
(
x
+
Δ
x
)
(6)
g
(
x
+
Δ
x
)
-
g
(
x
)
-
V
(
Δ
x
)
=
o
(
∥
Δ
x
∥
)
.
gis said to be p-order (0
<
p
<
∞) semismooth at x if g is semismooth at x and
(7)
g
(
x
+
Δ
x
)
-
g
(
x
)
-
V
(
Δ
x
)
=
O
(
∥
Δ
x
∥
1
+
p
)
.
In particular, g is called strongly semismooth at x if g is 1-order semismooth at x. A function g is said to be a (strong) semismooth function if it is (strong) semismooth everywhere on ℝ
n.Now, let us consider the composite nonsmooth function:(8)
g
∶
=
φ
∘
ψ
,
where φ
:
ℝ
n
→
ℝ
m is nonsmooth but of special structure and ψ
:
ℝ
m
→
ℝ
n is continuously differentiable. It should be noted that neither ∂
g
(
x
) nor ∂
B
g
(
x
) is easy to compute even if ∂
φ
(
y
), ∂
B
φ
(
y
), and ψ
′
(
x
) are available. To circumvent the difficulty in computing ∂
B
g
(
x
), Potra et al. [27] introduced the concept of generalized Jacobian:
(9)
∂
Q
g
(
x
)
=
∂
B
(
φ
(
ψ
(
x
)
)
)
ψ
′
(
x
)
.
Furthermore, in order to weaken the nonsingularity assumption on the generalized Jacobians, D. Sun and J. Sun also introduced in [22] the following concepts of relative generalized Jacobians.Definition 2.
LetS be a subset of ℝ
n. The S-relative generalized Jacobians  ∂
B
∣
S
g
(
x
) and ∂
Q
∣
S
g
(
x
) of g at x are defined by
(10)
∂
B
∣
S
g
(
x
)
∶
=
{
V
∣
V
is
a
limit
of
V
i
∈
∂
B
g
(
y
i
)
,
∂
B
∣
S
g
(
x
)
i
∶
=
y
i
∈
S
,
y
i
⟶
x
}
,
∂
Q
∣
S
g
(
x
)
∶
=
{
V
∣
V
is
a
limit
of
V
i
∈
∂
Q
g
(
y
i
)
,
∂
Q
∣
S
g
(
x
)
i
∶
=
∂
Q
g
y
i
∈
S
,
y
i
⟶
x
}
.Lemma3 presents the properties of the relative generalized Jacobians which has been proved in [22]. We omit the proof here.Lemma 3.
Letg be Lipschitz continuous near x. Then(i)
∂
B
∣
S
g
(
x
) and ∂
Q
∣
S
g
(
x
) are compact subsets of ∂
B
g
(
x
) and ∂
Q
g
(
x
), respectively.
(ii)
∂
B
∣
S
g
(
x
) and ∂
Q
∣
S
g
(
x
) are upper semicontinuous at x.


## 3. The Generalized Inexact Newton Method

LetA
:
ℝ
n
→
𝒮 be continuously differentiable and let c
=
(
c
1
,
c
2
,
…
,
c
n
)
T
∈
ℝ
n. In what follows, we suppose that {
λ
i
(
c
)
}
i
=
1
n are the eigenvalues of the matrix A
(
c
) with λ
1
(
c
)
≤
λ
2
(
c
)
≤
⋯
≤
λ
n
(
c
) and write
(11)
Λ
(
c
)
∶
=
diag
⁡
(
λ
1
(
c
)
,
…
,
λ
n
(
c
)
)
.
Let us define
(12)
𝒬
(
c
)
∶
=
{
Q
(
c
)
=
[
q
1
(
c
)
,
…
q
n
(
c
)
]
∣
Q
(
c
)
T
Q
(
c
)
=
I
,
l
l
Q
(
c
)
T
A
(
c
)
Q
(
c
)
=
Λ
(
c
)
}
.
Recall that the function f is defined by (3) and this means that f is a composite nonsmooth function. Then the concept of generalized Jacobian can be applied to f and we get
(13)
∂
Q
f
(
c
)
=
{
J
(
c
)
∣
[
J
(
c
)
]
i
j
=
q
i
(
c
)
T
∂
A
(
c
)
∂
c
j
q
i
(
c
)
l
l
where
[
q
1
(
c
)
q
2
(
c
)
⋯
q
n
(
c
)
]
∈
𝒬
(
c
)
∂
A
(
c
)
∂
c
j
}
;
see [22, Proposition 5.1]. Hence, according to this, the generalized Newton method for solving the IEP can be described as follows; see [22].Algorithm 4 (the generalized Newton method).
(1) Fork
=
0,1
,
… until convergence, do the following.(a)
Compute aQ
(
c
k
)
∈
𝒬
(
c
k
).
(b)
FormJ
(
c
k
)
∈
∂
Q
f
(
c
k
) according to (13).
(c)
Solvec
k
+
1 from the equation
(14)
J
(
c
k
)
(
c
k
+
1
-
c
k
)
=
-
f
(
c
k
)
.
The generalized Newton method converges quadratically; see for instance [22, Theorem 5.3]. In deriving the quadratic convergence of this method, it was assumed that system (14) is solved exactly. Usually, one solves these systems by iterative methods, in particular in the case when n is large. However iterative methods may bring an oversolving problem in the sense that the last few iterations before convergence are usually insignificant as far as the convergence of the outer iteration is concerned. This oversolving of the inner iterations will cause a waste of time and does not improve the efficiency of the whole method. The generalized inexact Newton method is derived precisely to avoid the oversolving problem in the inner iterations. Instead of solving (14) exactly, one solves it iteratively until a reasonable tolerance is reached. The tolerance is chosen carefully such that it is small enough to guarantee the convergence of the outer iteration, but large enough to reduce the oversolving problem of the inner iterations. We find that the tolerance has to be of ∥
c
k
-
c
*
∥
β in order to have a convergence rate of β for the outer iteration. We now give the generalized inexact Newton method for solving the IEP. We will prove in Section 4 that the convergence rate of the method is equal to β.Algorithm 5 (the generalized inexact Newton method).
(1) Fork
=
0,1
,
… until convergence, do the following.(a) Compute aQ
(
c
k
)
∈
𝒬
(
c
k
).
(b) FormJ
(
c
k
)
∈
∂
Q
f
(
c
k
) according to (13).
(c) Solvec
k
+
1 inexactly from the equation
(15)
J
(
c
k
)
(
c
k
+
1
-
c
k
)
=
-
f
(
c
k
)
+
r
k
,
until the residualr
k satisfies
(16)
∥
r
k
∥
≤
∥
f
(
c
k
)
∥
β
,
1
<
β
≤
2
.


## 4. Convergence Analysis

In this section, we carry on a convergence analysis of Algorithm5. Let {
λ
i
*
}
i
=
1
n be given with
(17)
λ
1
*
≤
λ
2
*
≤
⋯
≤
λ
n
*
.
Let c
* be the solution of the IEP. Let Λ
(
c
) be defined by (11) and
(18)
S
=
{
c
∈
ℝ
n
∣
A
(
c
)
has
distinct
eigenvalues
}
.
Then for any c
∈
S,  f is continuously differentiable at c and moreover
(19)
∂
B
f
(
c
)
=
∂
Q
f
(
c
)
=
{
f
′
(
c
)
}
.
Thus, according to Definition 2, we obtain the following relative generalized Jacobian of f at c:
(20)
∂
Q
∣
S
f
(
c
)
=
∂
B
∣
S
f
(
c
)
=
{
J
(
c
)
∣
J
(
c
)
is
the
limit
of
J
(
y
i
)
∈
∂
Q
f
(
y
i
)
where
y
i
∈
S
,
y
i
⟶
c
}
.We first present the following two lemmas which are important for the proof of the main theorem. Lemma6 illustrates the continuous property about the eigenvalues and can be found in many papers; see for example [15–18, 28]. However Lemma 7 is a crucial result in [22] and has been proved there.Lemma 6.
Suppose that there existsc
* such that the matrix A
(
c
*
) has eigenvalues given by (17). Suppose that A
′ is Lipschitz continuous around c
*. Then there exist positive numbers δ
0 and L
0 such that, for each c
∈
B
(
c
*
,
δ
0
), the following assertion holds:
(21)
∥
f
(
c
)
∥
≤
L
0
∥
c
-
c
*
∥
.Lemma 7.
f
(
·
) is a strongly semismooth function.With Lemmas6 and 7, we are in the position to prove the superlinear convergence of Algorithm 5. In order to ensure the superlinear convergence, one may want to assume that all J
(
c
*
)
∈
∂
Q
f
(
c
*
) are nonsingular. However, as noted by [15], it is generally possible to choose the eigenvectors such that J
(
c
*
) is nonsingular when multiple eigenvalues are presented. Hence we assume here that all matrices J
(
c
*
)
∈
∂
Q
∣
S
f
(
c
*
) are nonsingular.Theorem 8.
Suppose that there existsc
*
∈
c
l
S such that the matrix A
(
c
*
) has eigenvalues given by (17). Let ∂
Q
∣
S
f
(
c
) be defined by (20). If (i) for each k, c
k
∈
S, (ii) all J
(
c
*
)
∈
∂
Q
∣
S
f
(
c
*
) are nonsingular, and (iii) A
′ is Lipschitz continuous around c
*, then there exists a positive number δ such that, for each c
0
∈
B
(
c
*
,
δ
)
⋂
S, the sequence {
c
k
} generated by Algorithm 5 converges to c
* with
(22)
∥
c
k
+
1
-
c
*
∥
≤
α
∥
c
k
-
c
*
∥
β
.
Here α is a positive constant.Proof.
SinceA
′ is Lipschitz continuous around c
*, it follows from Lemma 6 that f
(
·
) is also Lipschitz continuous around c
*. On the other hand, note that all J
(
c
*
)
∈
∂
Q
∣
S
f
(
c
*
) are nonsingular. Thus, thanks to Lemma 3, there exist positive numbers δ
1 and L
1 such that, for each c
∈
B
(
c
*
,
δ
1
)
⋂
S, all J
(
c
)
∈
∂
Q
∣
S
f
(
c
) are nonsingular and
(23)
∥
J
(
c
)
-
1
∥
≤
L
1
.
Since, by Lemma 7, f
(
·
) is a strong semismooth function, there exist positive numbers L
2 and δ
2 such that for all c
∈
B
(
c
*
,
δ
2
)
⋂
S and all J
(
c
)
∈
∂
Q
∣
S
f
(
c
)
(24)
∥
f
(
c
)
-
f
(
c
*
)
-
J
(
c
)
(
c
-
c
*
)
∥
≤
L
2
∥
c
-
c
*
∥
2
.
Let
(25)
α
=
L
1
L
2
+
L
1
L
0
β
.
Take δ such that
(26)
0
<
δ
<
min
⁡
{
1
,
δ
0
,
δ
1
,
δ
2
,
α
1
/
(
1
-
β
)
}
.
Below we will show that α and δ are as desired. For this end, let c
m be the mth-iteration. We assert that
(27)
c
m
∈
B
(
c
*
,
δ
)
⋂
‍
S
⟹
∥
c
m
+
1
-
c
*
∥
≤
α
∥
c
m
-
c
*
∥
β
,
c
m
+
1
∈
B
(
c
*
,
δ
)
⋂
‍
S
.
Granting this and by the assumption that c
0
∈
B
(
c
*
,
δ
)
⋂
S, we can complete the proof of the theorem. To give the proof of assertion (27), we suppose that c
m
∈
B
(
c
*
,
δ
)
⋂
S. Note that 0
<
δ
<
min
⁡
{
δ
1
,
δ
2
}. Then, by (23) and (24), we obtain that for all J
(
c
m
)
∈
∂
Q
|
S
f
(
c
m
)
(28)
∥
J
(
c
m
)
-
1
∥
≤
L
1
,
(29)
∥
f
(
c
m
)
-
f
(
c
*
)
-
J
(
c
m
)
(
c
m
-
c
*
)
∥
≤
L
2
∥
c
m
-
c
*
∥
2
.
On the other hand, noting that δ
<
δ
0, one has by Lemma 6 and (16) that
(30)
∥
r
m
∥
≤
∥
f
(
c
m
)
∥
β
≤
L
0
β
∥
c
m
-
c
*
∥
β
.
Since f
(
c
*
)
=
0, we derive from (15) that
(31)
c
m
+
1
-
c
*
=
J
(
c
m
)
-
1
[
f
(
c
m
)
-
f
(
c
*
)
-
J
(
c
m
)
(
c
m
-
c
*
)
-
r
m
]
.
Combining this with (28)–(30), we obtain
(32)
∥
c
m
+
1
-
c
*
∥
≤
L
1
(
L
2
∥
c
m
-
c
*
∥
2
+
L
0
β
∥
c
m
-
c
*
∥
β
)
≤
α
∥
c
m
-
c
*
∥
β
,
where the last inequality holds because  ∥
c
m
-
c
*
∥
<
δ
<
1 and  α
=
L
1
L
2
+
L
1
L
0
β. Furthermore, by the fact that α
∥
c
m
-
c
*
∥
β
-
1
<
α
δ
β
-
1
<
1, we get
(33)
∥
c
m
+
1
-
c
*
∥
<
∥
c
m
-
c
*
∥
<
δ
,
which together with the assumption (
i
) implies c
m
+
1
∈
B
(
c
*
,
δ
)
⋂
S. Therefore, we complete the proof of the assertion and hence the proof of the whole theorem.In the special case whenr
k
≡
0, Algorithm 5 reduces Algorithm 4. Thus, applying Theorem 8, we have the following result for the generalized Newton method which coincides with [22, Theorem 5.4].Corollary 9.
Suppose that there existsc
*
∈
c
l
S such that the matrix A
(
c
*
) has eigenvalues given by (17). Let ∂
Q
|
S
f
(
c
) be defined by (20). If (i) for each k, c
k
∈
S, (ii) all J
(
c
*
)
∈
∂
Q
|
S
f
(
c
*
) are nonsingular, and (iii) A
′ is Lipschitz continuous around c
*, then there exists a positive number δ such that, for each c
0
∈
B
(
c
*
,
δ
)
⋂
S, the sequence {
c
k
} generated by Algorithm 4 converges quadratically to c
*.


## 5. A Numerical Example

In this section, we present the numerical performance of Algorithm5 with that of Algorithm 4. Our aim is, for the inverse eigenvalue problems with multiple eigenvalues, to illustrate the advantage of the generalized inexact Newton method over the generalized Newton method in terms of minimizing the oversolving problem and the overall computational complexity. The test was carried out in MATLAB 7.0 running on a Genuine Intel(R) PC with 1.6 GHz CPU.We consider the typical choice,(34)
A
(
c
)
∶
=
A
0
+
∑
i
=
1
n
‍
c
i
A
i
,
and use Toeplitz matrices as our {
A
i
}
i
=
1
n:
(35)
A
1
=
I
,
A
2
=
(
0
1
0
⋯
0
1
0
1
⋱
⋮
0
1
⋱
⋱
0
⋮
⋱
⋱
0
1
0
⋯
0
1
0
)
,
…
,
A
n
=
(
0
0
⋯
0
1
0
⋱
⋱
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
⋱
⋱
0
1
0
⋯
0
0
)
.
Thus A
(
c
) is a symmetric Toeplitz matrix with the first column equal to c. This numerical example has been studied extensively; see for instance [12, 14, 17, 18, 20].In the tests, we tried Algorithms4 and 5 on ten 100-by-100 matrices. For each matrix, we first generate a vector c such that there exist some integers 1
≤
k
≤
n
-
1 such that |
λ
k
+
1
(
c
)
-
λ
k
(
c
)
|
<
5
e
-
6, where {
λ
i
(
c
)
}
i
=
1
n are the eigenvalues of matrix A
(
c
). Set
(36)
λ
i
*
=
{
λ
k
(
c
)
,
i
=
k
,
k
+
1
;
λ
i
(
c
)
,
otherwise
.
Then we choose {
λ
i
*
}
i
=
1
n as the prescribed eigenvalues. Since both Algorithms 4 and 5 are locally convergent, c
0 is formed by chopping the components of c
* to four decimal places. For both algorithms, the stopping tolerance for the outer (Newton) iterations is 1
0
-
10. The inner systems (14) and (15) are all solved by the QMR method [29] via the MATLAB QMR function, where the maximal number of iterations is set to be 1000. Also, the initial guess for the Jacobian equations in the (
k
+
1
)th outer iteration is set to be c
k obtained at the kth outer iteration. The inner loop stopping tolerance for (15) is given by (16), while for (14) in Algorithm 4, we are supposed to solve it up to machine precision eps (which is ≈2.2 × 10−16).Comparisons of Algorithm5 with Algorithm 4 are illustrated in Table 1. In this table, we give the total numbers of outer iterations N
o averaged over the ten tests and the average total numbers of inner iterations N
i required for solving the Jacobian equations. Here “I” means no preconditioner, while “P” means that the MATLAB incomplete LU factorization (MILU) is adopted as the preconditioner, that is, LUINC (A, [drop-tolerance, 1, 1, 1]), where the drop tolerance is set to be 0.01. We can see from this table that N
o is small for Algorithm 4 and also for Algorithm 5 when β
≥
1.6. This confirms the theoretical convergence rate of the two algorithms. In terms of N
i, we see that one requires less inner iterations in Algorithm 5 than those in Algorithm 4. Thus, we can conclude that Algorithm 5 with β around 1.5 is much better than Algorithm 4. On the other hand, we also note that the MILU preconditioner is quite effective for the Jacobian equations.Table 1
Averaged total numbers of outer and inner iterations.
Algorithm4
β in Algorithm 5
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
I
N
o
6.0
11.8
8.7
6.7
6.5
6.3
6.1
6.0
6.0
6.0
6.0
N
i
1373.0
1342.1
1072.6
878.8
874.1
884.6
874.7
890.8
944.8
967.7
1001.5
P
N
o
5.8
8.5
7.4
6.7
6.2
6.0
5.8
5.8
5.8
5.8
5.8
N
i
55.5
14.6
17.3
17.8
20.4
21.8
23.7
24.9
28.3
29.7
31.6


## 6. Concluding Remarks

In this paper, we have proposed a generalized inexact Newton method for the inverse eigenvalue problem. We show that our inexact method converges superlinearly. This inexact version can minimize the oversolving problem of the generalized Newton method and give a good tradeoff between the inner and outer iterations. We also present numerical experiments to illustrate our results.It is a pity that similar approaches cannot been extended to the inexact Newton-like method up till now. This is another interesting topic of our works.



---

*Source: 721346-2014-02-19.xml*