Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices

M. L. Overton^{1} and R. S. Womersley^{2}

June 1991 Submitted to Math Programming

Abstract: This paper gives max characterizations for the sum of the largest eigenvalues of a symmetric matrix. The elements which achieve the maximum provide a concise characterization of the generalized gradient of the eigenvalue sum in terms of a dual matrix. The dual matrix provides the information required to either verify first-order optimality conditions at a point or to generate a descent direction for the eigenvalue sum from that point, splitting a multiple eigenvalue if necessary. A model minimization algorithm is outlined, and connections with the classical literature on sums of eigenvalues are explained. Sums of the largest eigenvalues in absolute value are also addressed.

Key words: symmetric matrix, maximum eigenvalues, spectral radius, minimax problem, max characterization, generalized gradient.

Short title: Minimizing sums of eigenvalues

1. Courant Institute of Mathematical Sciences, New York University, New York, New York, 10012. The work of this author was supported by the National Science Foundation under grant CCR-88-02408.

2. School of Mathematics, University of New South Wales, P.O. Box 1, Kensington, N.S.W. 2033, Australia. The work of this author was supported in part during a visit to Argonne National Laboratory by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under contract W-31-109-Eng-38, and in part during a visit to the Courant Institute by the U.S. Department of Energy under Contract DEFG0288ER25053.

1 Introduction

Let A be an n by n real symmetric matrix, and let κ ∈ {1,…, n}. Denote the eigenvalues of A by λ_{1},…, λ_{n} and also by μ_{1},…, μ_{n}, the difference being that the former are ordered by

λ_{1} ≥ ⋯ ≥ λ_{n},  (1.1)

while the latter are ordered by

|μ_{1}| ≥ ⋯ ≥ |μ_{n}|.  (1.2)

Define

f_{κ}(A) = ∑_{i=1}^{κ} λ_{i}  (1.3)

and

g_{κ}(A) = ∑_{i=1}^{κ} |μ_{i}|.  (1.4)

Note that f_{1}(A) is the largest eigenvalue of A, while g_{1}(A) is the spectral radius of A (its largest eigenvalue in absolute value).

After establishing some further notation in Section 2, the main results of the paper are given in Sections 3 and 4 for the functions f_{κ}(A) and g_{κ}(A) respectively. Max characterizations of these functions are established in terms of the Frobenius inner product ⟨ A, B ⟩ = tr(AB^{T}) for A, B ∈ R^{m×n} (where tr(A) denotes the trace of A), and sets of matrices defined by positive semi-definite inequalities (see Section 2). Let S_{n} denote the set of real n by n symmetric matrices,

Φ_{n,κ} = { U ∈ S_{n} : 0 ≤ U ≤ I, tr(U) = κ }  (1.5)

and

Ψ_{n,κ} = { W ∈ S_{n} : W = U − V, where U, V ∈ S_{n},
0 ≤ U ≤ I, 0 ≤ V ≤ I, tr(U) + tr(V) = κ }.  (1.6)

The sets Φ_{n,κ} and Ψ_{n,κ} are compact convex subsets of S_{n}. It is shown that

f_{κ}(A) = max_{U∈Φ_{n,κ}} ⟨ A, U ⟩  (1.7)

and

g_{κ}(A) = max_{W ∈Ψ_{n,κ}} ⟨ A, W ⟩.  (1.8)

In fact, equation (1.7) implies a well known result of Fan (1949), namely

f_{κ}(A) = max_{Z∈R^{n×κ},Z^{T} Z=I} tr(Z^{T} AZ).  (1.9)

Fan’s result is widely referenced; see Wielandt (1955), Cullum, Donath and Wolfe (1975), Friedland (1981), Sameh and Wisniewski (1982), Horn and Johnson (1985) and Fletcher (1985). Both (1.7) and (1.9) show that f_{κ}(A) is a convex function. The advantage of (1.7) over (1.9) is that it leads directly to a characterization of the subdifferential of f_{κ} which is computationally very useful, since it does not involve a convex hull operation. Equation (1.8) has a similar advantage over a corresponding analogue of (1.9).

In the case κ = 1, (1.9) reduces to the Rayleigh principle

f_{1}(A) = max_{q^{T} q=1} q^{T} A(x)q  (1.10)

while (1.7) reduces to

f_{1}(A) = max_{U≥0,tr(U)=1}⟨ A, U ⟩.  (1.11)

Note that the inequality U ≤ I is not required. Equation (1.11) is moderately well known; see Fletcher (1985) and Overton (1988, 1990).

Now consider the composite functions

f_{κ}(x) ≡ f_{κ}(A(x)),  g_{κ}(x) ≡ g_{κ}(A(x))  (1.12)

where A(x) is a smooth symmetric matrix function defined on a vector of parameters x ∈ R^{m}. The use of the same symbol f_{κ} for a function defined on the set of symmetric matrices and on the parameter space R^{m} is convenient, and the distinction should be clear from the context. The max characterizations (1.7) and (1.8) prove that f_{κ}(x) and g_{κ}(x) are locally Lipschitz, subdifferentially regular, and have generalized gradients ∂f_{κ}(x) and ∂g_{κ}(x) respectively, which are nonempty compact convex sets in R^{m} (see Clarke (1983)). These generalized gradients are obtained by composing the subdifferential of f_{κ}(A) and g_{κ}(A) with the derivative of A(x), using the chain rule. In fact Clarke (1983, Proposition 2.8.8) derives an expression for the generalized gradient of the largest eigenvalue f_{1}(x), but in a form which requires a convex hull operation. An important feature of our max characterizations is that they lead to first-order optimality conditions which are computationally verifiable, providing matrix analogues of Lagrange multipliers in constrained optimization, namely U or U and V, which we call dual matrices. The necessary condition 0 ∈ ∂f_{κ}(x) or 0 ∈ ∂g_{κ}(x) (see Clarke (1983)) provides systems of linear equations which can be solved to obtain the dual matrices. Inequalities of the form 0 ≤ U ≤ I determine if the current point is a stationary point, or provide information from which a descent direction can be calculated.

Equations (1.7) and (1.8) show that if A(x) is an affine function then f_{κ}(x) and g_{κ}(x) are convex functions. They also illustrate that minimizing f_{κ}(x) or g_{κ}(x) are minimax problems:

min_{x∈R^{m}} f_{κ}(x) ≡ min_{x∈R^{m}} max_{U∈Φ_{n,κ}} ⟨ A(x), U ⟩,  (1.13)

and

min_{x∈R^{m}} g_{κ}(x) ≡ min_{x∈R^{m}} max_{W ∈Ψ_{n,κ}} ⟨ A(x), W ⟩.  (1.14)

If A(x) is affine, the saddle point result

min_{x∈R^{m}} max_{U∈Φ_{n,κ}} ⟨ A(x), U ⟩ = max_{U∈Φ_{n,κ}} min_{x∈R^{m}} ⟨ A(x), U ⟩,

and a similar result for (1.14) are established. This is similar to the result of Shapiro (1985) for minimizing a function of a symmetric matrix subject to positive semidefinite constraints. These saddle point results justify the dual matrix terminology.

If the eigenvalues of A(x) are distinct then (1.13) and (1.14) are just minimax problems with smooth functions λ_{i}(x) : R^{m} → R for i = 1,…, n. Let λ(x) = ( λ_{1}(x),…, λ_{n}(x) )^{T}, using any ordering for the eigenvalues. Then

f_{κ}(x) = max_{u∈ϕ_{n,κ}} λ(x)^{T} u  (1.15)

where

ϕ_{n,κ} = { u ∈ R^{n} : 0 ≤ u_{i} ≤ 1, i = 1,…, n, ∑_{i=1}^{n} u_{i} = κ },  (1.16)

and

g_{κ}(x) = max_{w∈ψ_{n,κ}} λ(x)^{T} w  (1.17)

where

ψ_{n,κ} = { w ∈ R^{n} : −1 ≤ w_{i} ≤ 1, i = 1,…, n, ∑_{i=1}^{n} |w_{i}| = κ }.  (1.18)

The additional complication in (1.13) and (1.14) arises from the possibility of multiple eigenvalues; hence the positive semi-definite constraints defining the sets Φ_{n,κ} and Ψ_{n,κ}.

This paper is not concerned with algorithm development. However, a brief discussion of model algorithms for minimizing f_{κ}(x) and g_{κ}(x) is given. These are generalizations of the algorithm presented by Overton (1988) for the case when κ = 1 and A(x) is affine. It is, in fact, possible to design the model algorithms so that they have quadratic local convergence, even if the objective function is not smooth at the solution; see Overton (1988) and Overton (1990). More detail will be given by Overton and Womersley (to appear). Cullum, Donath and Wolfe (1975) gave an algorithm, related to the ϵ-subgradient methods of Lemarechal and others, for the case that the variables x are the diagonal elements of A(x). The most important difference between this earlier work and our model algorithms is that the latter compute the dual matrices which demonstrate optimality. These matrices are also the key to sensitivity analysis of the solution; see Overton (1990, Section 3).

Sums of eigenvalues of symmetric matrices have been addressed in one form or another in many classical papers on matrix theory; a good overview is Bellman (1970, Chapter 8). However, the rich interconnection between this subject and the sets Φ_{n,κ} and Ψ_{n,κ} appears to have been largely overlooked. Note that although all our results are given in terms of real symmetric matrices, generalization to the complex Hermitian case is straightforward.

The classical literature on sums of eigenvalues does not include much discussion of applications. However, these appear to be quite numerous, especially in connection with adjacency matrices of graphs. See in particular Cullum, Donath and Wolfe (1975), as well as Rendl and Wolkowicz (1990), and Alizadeh (1991). Another application is the “orthogonal Procrustes” problem, which refers to rotating a number of matrices towards a best least squares fit. This problem is discussed by Shapiro and Botha (1988) and has also been addressed by Watson (1990). There is a large variety of applications in the case κ = 1; see Overton(1990).

2 Notation

The following notation is used throughout this paper. Let

1. S_{n} = set of all n by n real symmetric matrices (A^{T} = A).

2. K_{n} = set of all n by n real skew-symmetric matrices (A^{T} = −A).

3. D_{n} = set of all n by n real diagonal matrices.

4. O_{m,n} = set of all m by n real orthogonal matrices, where m ≥ n. Thus Z^{T} Z = I_{n} for all Z ∈ O_{m,n}.

The vector e_{i} is the ith coordinate vector, e is the vector of all 1s, and I is the identity matrix, with the dimensions of e_{i}, e and I determined by the context. A matrix D ∈ D_{n} is denoted by diag(α_{1},…, α_{n}), or diag(u) where u ∈ R^{n}. The convex hull of a set Ω is denoted by conv Ω.

For A ∈ R^{n×n} the eigenvalues of A are denoted by (1.1) and by (1.2). The trace of A is

tr(A) = ∑_{i=1}^{n} a_{ii} = ∑_{i=1}^{n} λ_{i} = ∑_{i=1}^{n} μ_{i}.

The positive semi-definite partial ordering on S_{n} is used to express matrix inequalities (see Golub and van Loan (1985) or Horn and Johnson (1985) for example). Thus A ≥ 0 means that A is positive semi-definite (equivalently y^{T} Ay ≥ 0 ∀y, or λ_{i} ≥ 0 for i = 1,…, n). Hence A ≥ B means that A − B is positive semi-definite. For example the constraints 0 ≤ A ≤ I on A ∈ S_{n} mean that 0 ≤ λ_{i} ≤ 1 for i = 1,…, n.

The Frobenius inner product ⟨ A, B ⟩ of two matrices A, B ∈ R^{m×n} is

⟨ A, B ⟩ = tr(AB^{T}) = ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}b_{ij}.

This inner product is the natural extension for real matrix variables of the standard inner product x^{T} y = ∑_{i=1}^{n} x_{i}y_{i} on R^{n}. It is widely used in problems with matrix variables, for example in the work of Bellman and Fan (1963), Arnold (1971), Craven and Mond (1981). Fletcher (1985), Overton (1988), and Overton and Womersley (1988) used the notation A : B for ⟨ A, B ⟩.

Some useful properties of the Frobenius inner product are summarized below.

1. ⟨ A, A ⟩ = ||A||_{F}^{2} .

2. ⟨ A, I ⟩ = tr(A).

3. If A ∈ S_{n} and K ∈ K_{n} then ⟨ A, K ⟩ = 0.

4. As tr(AB^{T}) = tr(BA^{T}) = tr(A^{T} B)

⟨ A, B ⟩ = ⟨ B, A ⟩ = ⟨ A^{T} , B^{T} ⟩ = ⟨ B^{T} , A^{T} ⟩.

In particular

(a) For any nonsingular matrices S ∈ R^{m×m} and T ∈ R^{n×n}

⟨ A, B ⟩ = ⟨ S^{−1}A, S^{T} B ⟩ = ⟨ AT^{−1}, BT^{T} ⟩.

(b) If A ∈ R^{n×n}, B ∈ R^{m×m} and Z ∈ R^{n×m} then

⟨ Z^{T} AZ, B ⟩ = ⟨ A, ZBZ^{T} ⟩.

3 Sum of the largest eigenvalues

Let A ∈ S_{n} have eigenvalues

λ_{1} ≥ ⋯ ≥ λ_{n},

and let Q ∈ O_{n,n} be a matrix whose columns are normalized eigenvectors of A, so

Q^{T} AQ = Λ  (3.1)

where Λ = diag(λ_{1},…, λ_{n}). The matrix Q will be regarded as fixed, although if A has multiple eigenvalues the choice of Q is not unique.

Let κ ∈ {1,…, n}. Section 3.1 establishes a max characterization of

f_{κ}(A) = ∑_{i=1}^{κ} λ_{i}.  (3.2)

Thereafter we concentrate on the case when A : R^{m} → S_{n} is a smooth matrix-valued function and

f_{κ}(x) = f_{κ}(A(x)).  (3.3)

Section 3.2 considers the differential properties of f_{κ}(x), Section 3.3 gives necessary conditions for a local minimizer, Section 3.4 establishes a saddle point result, Section 3.5 gives a formula for the directional derivative, Section 3.6 discusses the generation of descent directions by splitting multiple eigenvalues and Section 3.7 considers a model algorithm for minimizing f_{κ}(x).

3.1 A max characterization

Let

Φ_{n,κ} = { U ∈ S_{n} : 0 ≤ U ≤ I, tr(U) = κ },  (3.4)

and

ϕ_{n,κ} = { u ∈ R^{n} : 0 ≤ u ≤ e, e^{T} u = κ }.  (3.5)

Lemma 3.1 The sets Φ_{n,κ} and ϕ_{n,κ} are compact and convex. Moreover Φ_{n,κ} is invariant under orthogonal similarity transformations (i.e. U ∈ Φ_{n,κ} ⟺ Z^{T} UZ ∈ Φ_{n,κ} where Z ∈ O_{n,n}), and Φ_{n,κ} and ϕ_{n,κ} are related by

Φ_{n,κ} = { U ∈ S_{n} : U = ZDZ^{T} where Z ∈ O_{n,n},
D = diag(u_{1},…, u_{n}) and u ∈ ϕ_{n,κ} },  (3.6)

and

ϕ_{n,κ} = { u ∈ R^{n} : u_{i} = U_{ii} for i = 1,…, n where U ∈ Φ_{n,κ} }.  (3.7)

Proof: That Φ_{n,κ} and ϕ_{n,κ} are compact convex sets is immediate. A spectral decomposition of U yields (3.6) and the orthogonal invariance of Φ_{n,κ}. The set ϕ_{n,κ} is contained in the right-hand side of (3.7) since for any u ∈ ϕ_{n,κ}, diag(u_{1},…, u_{n}) ∈ Φ_{n,κ}. To obtain the reverse inclusion, let U ∈ Φ_{n,κ} and define u by u_{i} = U_{ii}. The facts that the trace is the sum of the diagonal elements and that a positive semidefinite matrix cannot have a negative diagonal element then show that u ∈ ϕ_{n,κ}.

To characterize the elements that achieve the maximum in the following results, information about the multiplicity of the eigenvalues of A is needed. Let

λ_{1} ≥ ⋯ ≥ λ_{r} >
λ_{r+1} = ⋯ = λ_{κ} = ⋯ = λ_{r+t} >  (3.8)
λ_{r+t+1} ≥ ⋯ ≥ λ_{n},

where t ≥ 1 and r ≥ 0 are integers. The multiplicity of the κth eigenvalue is t. The number of eigenvalues larger than λ_{κ} is r. Here r may be zero; in particular this must be the case if κ = 1. Note that by definition

r + 1 ≤ κ ≤ r + t ≤ n,

so t ≥ κ − r. Also, t = 1 implies that κ = r + 1.

First two lemmas, which depend only on the definitions of the sets Φ_{n,κ} and ϕ_{n,κ} and the ordering of the elements λ_{i} in (3.8), are established. In particular they do not require λ_{i} to be an eigenvalue of a matrix.

Lemma 3.2 If the elements of λ ∈ R^{n} satisfy (3.8) then

max_{u∈ϕ_{n,κ}} λ^{T} u = ∑_{i=1}^{κ} λ_{i}

with

argmax { λ^{T} u : u ∈ ϕ_{n,κ} } = { u ∈ R^{n} : u_{i} = 1  i = 1,…, r,

0 ≤ u_{i} ≤ 1 i = r + 1,…, r + t, u_{i} = 0 i = r + t + 1,…, n and

∑_{i=r+1}^{r+t} u_{i} = κ − r }.

Proof: These results follow directly from (3.5) and (3.8).

Lemma 3.3 Let Λ = diag(λ) where the elements of λ ∈ R^{n} satisfy (3.8). Then

max_{U∈Φ_{n,κ}} ⟨ Λ, U ⟩ = ∑_{i=1}^{κ} λ_{i}  (3.9)

with

argmax { ⟨ Λ, U ⟩ : U ∈ Φ_{n,κ} }
=  { U ∈ S_{n} : U = [ I ; Ũ ; 0 ] , Ũ ∈ Φ_{t,κ−r} }  (3.10)

where

Φ_{t,κ−r} = { Ũ ∈ S_{t} : 0 ≤ Ũ ≤ I and tr(Ũ) = κ − r }.  (3.11)

Here the diagonal blocks of U have dimension r, t, and n − r − t respectively.

Proof: Λ = diag(λ) so

⟨ Λ, U ⟩ = ∑_{i=1}^{n} λ_{i}U_{ii}.  (3.12)

Hence (3.9) follows from combining Lemmas 3.1 and 3.2.

If U^{∗} is any element of the right hand side of (3.10) then from (3.8)

⟨ Λ, U^{∗} ⟩ = ∑_{i=1}^{r} λ_{i} + λ_{κ}tr(Ũ) = ∑_{i=1}^{κ} λ_{i}.  (3.13)

Now suppose U^{∗} ∈ argmax { ⟨ Λ, U ⟩ : U ∈ Φ_{n,κ} }. Then u^{∗} = (U_{11}^{∗},…, U_{nn}^{∗})^{T} ∈ ϕ_{n,κ} satisfies λ^{T} u^{∗} = ∑_{i=1}^{κ} λ_{i}, so from Lemma 3.2 it follows that

U_{ii}^{∗} = 1, i = 1,…, r,

0 ≤ U_{ii}^{∗} ≤ 1, i = r + 1,…, r + t (3.14)

U_{ii}^{∗} = 0, i = r + t + 1,…, n

∑_{i=r+1}^{r+t} U_{ii}^{∗} = κ − r.

Partition the rows and columns of U^{∗} into blocks of r, t and n − r − t elements so

U^{∗} = [ \begin{matrix}C_{11} & C_{12} & C_{13} \\ C_{12}^{T} & C_{22} & C_{23} \\ C_{13}^{T} & C_{23}^{T} & C_{33} \end{matrix} ]  (3.15)

where C_{11} ∈ S_{r}, C_{22} ∈ S_{t}, C_{33} ∈ S_{n−r−t}. As U^{∗} ∈ Φ_{n,κ},

0 ≤ C_{ii} ≤ I, i = 1, 2, 3 and ∑_{i=1}^{3} tr(C_{ii}) = κ.

From (3.14) and (3.15) the diagonal elements of C_{11} are all 1 and the diagonal elements of C_{33} are all zero. Suppose an off-diagonal element of C_{11} is nonzero. Then I − C_{11} is symmetric, has zero elements on the diagonal and a nonzero offdiagonal element, so is indefinite. This contradicts C_{11} ≤ I, so C_{11} = I. Similarly

I − [ \begin{matrix}C_{11} & C_{12} \\ C_{12}^{T} & C_{22} \end{matrix} ] = [ \begin{matrix}0 & −C_{12} \\ −C_{12}^{T} & I − C_{22} \end{matrix} ] ≥ 0

implies that C_{12} = 0. As the diagonal elements of C_{33} are all zero the existence of a nonzero off-diagonal element in C_{33} would contradict C_{33} ≥ 0, so C_{33} = 0. Similarly it follows that C_{13} = 0 and C_{23} = 0 as the existence of a nonzero element in either of these submatrices contradicts U^{∗} ≥ 0. The only conditions remaining then are 0 ≤ C_{22} ≤ I with tr(C_{22}) = κ − r as required.

Remark: The proof uses the basic results that if C ∈ S_{n} then

C ≥ 0, tr(C) = 0 ⇒ C = 0,  (3.16)
C ≤ I, tr(C) = n ⇒ C = I,  (3.17)

which follow from the observation that if C ≥ 0 and C_{ii} = 0 then C_{ij} = 0 and C_{ji} = 0 for j = 1,…, n.

Now consider sums of the eigenvalues of A. Let P_{1} ∈ O_{n,r} be the matrix consisting of the first r columns of Q (defined in equation (3.1)), and let Q_{1} ∈ O_{n,t} be the matrix consisting of the next t columns of Q. By (3.8) we have

P_{1}^{T} AP_{1} = diag(λ_{1},…, λ_{r});  Q_{1}^{T} AQ_{1} = λ_{κ}I.  (3.18)

Theorem 3.4 Let A ∈ S_{n} have eigenvalues λ_{1} ≥ ⋯ ≥ λ_{n}. Then

max_{U∈Φ_{n,κ}} ⟨ A, U ⟩ = ∑_{i=1}^{κ} λ_{i}.  (3.19)

If the eigenvalues satisfy (3.8) then

argmax { ⟨ A, U ⟩ : U ∈ Φ_{n,κ}}
=  { U ∈ S_{n} : U = P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T}; Ũ ∈ Φ_{t,κ−r} },  (3.20)

where P_{1}, Q_{1} satisfy (3.18).

Proof: For any U ∈ Φ_{n,κ} equation (3.1) and the properties of the Frobenius inner product imply that

⟨ A, U ⟩ = ⟨ QΛQ^{T} , U ⟩ = ⟨ Λ, Q^{T} UQ ⟩,  (3.21)

with Q^{T} UQ ∈ Φ_{n,κ} as Φ_{n,κ} is invariant to orthogonal transformations. Hence

max_{U∈Φ_{n,κ}} ⟨ A, U ⟩ = max_{U∈Φ_{n,κ}} ⟨ Λ, U ⟩ = ∑_{i=1}^{κ} λ_{i},

where the second equality follows from Lemma 3.3.

From (3.21) and the invariance of Φ_{n,κ} to orthogonal transformations

argmax { ⟨ A, U ⟩ : U ∈ Φ_{n,κ}} = { QU^{∗}Q^{T} : U^{∗} ∈ Ω }

where Ω = argmax { ⟨ Λ, U ⟩ : U ∈ Φ_{n,κ} }. The proof is completed by applying Lemma 3.3 since

QU^{∗}Q^{T} = Q [ I ; Ũ ; 0 ] Q^{T} = P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T} .

Remark: The term dual matrix is used to refer to either U ∈ Φ_{n,κ} or Ũ ∈ Φ_{t,κ−r}. The distinction between U and Ũ is analogous to the question of whether or not to assign zero Lagrange multipliers to inactive constraints in nonlinear programming.

Remark: If κ = r + t then Ũ = I and

argmax { ⟨ A, U ⟩ : U ∈ Φ_{n,κ}} = P_{1}P_{1}^{T} + Q_{1}Q_{1}^{T} .  (3.22)

The matrix achieving the maximum is unique if and only if κ = r + t. In particular this is the case if t = 1, i.e. the κth largest eigenvalue is simple.

Remark: All the freedom in the choice of Q_{1} in (3.18) is absorbed into the matrix Ũ. It also makes no difference if any of the eigenvalues λ_{1},…, λ_{r} have multiplicity greater than 1, as all of these multiple eigenvalues are included in f_{κ}(A). The corresponding columns of P_{1} can be any orthonormal basis for the corresponding eigenspace, without affecting P_{1}P_{1}^{T}.

Remark: As A ∈ S_{n} it follows that ⟨ A, K ⟩ = 0 for any K ∈ K_{n} (the set of skew-symmetric n by n matrices). Hence

f_{κ}(A) = ⟨ A, U + K ⟩

for any U belonging to (3.20) and K ∈ K_{n}.

Corollary 3.5 The function f_{κ}(A) : S_{n} → R is convex and its subdifferential ∂f_{κ}(A) is the nonempty compact convex set

∂f_{κ}(A) = { U ∈ S_{n} : ∃ Ũ ∈ Φ_{t,κ−r} with U = P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T} }.  (3.23)

Proof: For any U ∈ Φ_{n,κ} the inner product ⟨ A, U ⟩ is a linear function of A ∈ S_{n}, so the convexity of f_{κ}(A) follows from the max characterization in Theorem 3.4. Moreover, from Rockafellar (1970, corollary 23.5.3), the subdifferential of a function defined as a pointwise maximum of a set of linear functions is the convex hull of the gradients of the linear functions achieving the maximum at the given point. Thus the subdifferential of f_{κ}(A) is

∂f_{κ}(A) = conv { U ∈ S_{n} : ⟨ A, U ⟩ = f_{κ}(A) }.

The result follows from Theorem 3.4 as the set (3.20) is already convex.

Remark: As previously noted any skew-symmetric matrix can be added to U without affecting the inner product ⟨ A, U ⟩. As f_{κ}(A) is defined on S_{n} only the symmetric subdifferential is of interest.

Remark: In the case κ = 1, the condition Ũ ≤ I is unnecessary since it is implied by Ũ ≥ 0, tr(Ũ) = 1. This case is moderately well known; see Fletcher (1985). Fletcher also addressed the case κ > 1 in an appendix, but his Theorem A.4 is incorrect in the case κ > 1 since the condition Ũ ≤ I was omitted.

This section is concluded by relating our max characterization to the well known result of Fan (1949).

Lemma 3.6 The extreme points of ϕ_{n,κ} are

\{ u : u_{i} = \{ \begin{matrix}1 & for exactly κ of the indicies 1,…, n; \\ 0 & otherwise. \end{matrix} \}.  (3.24)

Proof: Straightforward.

Lemma 3.7 The extreme points of Φ_{n,κ} are the elements in Φ_{n,κ} with rank κ, that is the set of matrices U ∈ Φ_{n,κ} with κ eigenvalues equal to 1, and n − κ eigenvalues equal to zero.

Proof: Matrices in Φ_{n,κ} must have rank at least κ. Since Φ_{n,κ} and ϕ_{n,κ} are related by (3.6), it is straightforward to show that any element of Φ_{n,κ} with rank greater than κ is not an extreme point. The only candidates for extreme points, then, are those with rank κ. But it is clearly not possible that some rank κ elements are extreme points and others not, since the definition of Φ_{n,κ} does not in any way distinguish between different rank κ elements. Since a compact convex set must have extreme points, the proof is complete.

Fan’s theorem now follows as a corollary.

Theorem 3.8 (Fan)

max_{Z∈O_{n,κ}} tr(Z^{T} AZ) = ∑_{i=1}^{κ} λ_{i}.  (3.25)

Proof: Since a linear function on a convex set must assume its maximum at an extreme point, combining Theorem 3.4 with the lemma just given shows that

max_{U∈Φ_{n,κ}, rank U=κ}⟨ A, U ⟩ = ∑_{i=1}^{κ} λ_{i}.  (3.26)

Such matrices U have precisely the form ZZ^{T}, where Z ∈ O_{n,κ}. The proof is completed by noting that

⟨ A, ZZ^{T} ⟩ = ⟨ Z^{T} AZ, I ⟩ = tr(Z^{T} AZ).  (3.27)

Remark: Another expression for the subdifferential is

∂f_{κ}(A) = conv { ZZ^{T} : columns of Z form an orthonormal set
of κ eigenvectors for λ_{1},…, λ_{κ} }.  (3.28)

Note that these are just the elements that achieve the maximum in Fan’s theorem, and that the elements whose convex hull is being taken are the extreme points of (3.23). Although simpler to write than (3.23) this expression is not as useful, as the structure of the subdifferential is not apparent.

Remark: H. Woerdeman and C.-K. Li recently informed us that the equality

conv {ZZ^{T} : Z ∈ O_{n,κ}} = Φ_{n,κ}.

appeared in Fillmore and Williams (1971). This implies the equivalence of (3.19) and (3.25), although it does not by itself imply either of them; nor, strictly speaking, does it imply Lemma 3.7.

3.2 The generalized gradient

Let A(x) : R^{m} → S_{n} be a smooth (at least once continuously differentiable) function whose partial derivative with respect to x_{k} is

A_{k}(x) ≡ \frac{∂A(x)}{∂x_{k}} for k = 1,…, m.

This section is concerned with finding a computationally useful characterization of the generalized gradient of the function

f_{κ}(x) = f_{κ}(A(x)).

Although the eigenvalues and eigenvectors of A(x) are functions of x ∈ R^{m}, the explicit dependence on x will usually be omitted. Thus the eigenvalues of A(x) are denoted by as before (3.8), with r and t now dependent on x, and with corresponding eigenvectors satisfying (3.18).

Theorem 3.9 The function f_{κ}(x) is locally Lipschitz, subdifferentially regular, and its generalized gradient is the nonempty compact convex set

∂f_{κ}(x) = { u ∈ R^{m} : ∃ Ũ ∈ S_{t} with 0 ≤ Ũ ≤ I, tr(Ũ) = κ − r, and
u_{k} = tr(P_{1}^{T} A_{k}(x)P_{1}) + ⟨ Q_{1}^{T} A_{k}(x)Q_{1}, Ũ ⟩, k = 1,…, m }.(3.29)

Proof: Since f_{κ}(A) is convex and A(x) is smooth the chain rule (Clarke (1983), Theorem 2.3.10) implies that f_{κ}(x) is locally Lipschitz, subdifferentially regular, and that

∂f_{κ}(x) = { u ∈ R^{m} : u_{k} = ⟨ A_{k}(x), U ⟩, k = 1,…, m
where U ∈ ∂f_{κ}(A(x)) }.  (3.30)

Corollary 3.5 and the properties of the inner product complete the proof.

Remark: Since by Theorem 3.4

f_{κ}(x) = max_{U∈Φ_{n,κ}} ⟨ A(x), U ⟩.

the result also follows from the characterization of generalized gradients of functions defined by a pointwise maximum in Clarke (1983, Theorem 2.8.6). The Clarke characterization shows that

∂f_{κ}(x) = conv { u ∈ R^{m} : u_{k} = ⟨ A_{k}(x), U ⟩, k = 1,…, m
where ⟨ A(x), U ⟩ = f_{κ}(x) }.  (3.31)

Equation (3.29) follows from Theorem 3.4 since the maximizing set is already convex.

Remark: Bellman and Fan (1963) gave an example where the set

{ u ∈ R^{m} : u_{k} = ⟨ A_{k}, U ⟩, where U ≥ 0 }

is not closed, and gave sufficient conditions for it to be closed. This is not a difficulty in our case because the trace condition ensures that Φ_{n,κ} is compact. As f_{κ}(x) : R^{m} → R is a locally Lipschitz function its generalized gradient is a nonempty compact convex set in R^{m}.

Corollary 3.10 If λ_{κ} > λ_{κ+1} (i.e. κ = r + t) the function f_{κ} is differentiable at x with

\frac{∂f_{κ}(x)}{∂x_{k}} = tr(P_{1}^{T} A_{k}(x)P_{1}) + tr(Q_{1}^{T} A_{k}(x)Q_{1}).  (3.32)

Proof: As κ − r = t the only solution to tr(Ũ) = t and 0 ≤ Ũ ≤ I is Ũ = I. Hence the set ∂f_{κ}(x) is a singleton, f_{κ}(x) is differentiable, and (3.29) reduces to (3.32).

Remark: A key point here is that if λ_{j} is an eigenvalue of A(x) with multiplicity ℓ there exists a neighbourhood of x in which the corresponding group of ℓ eigenvalues is distinct from all the other eigenvalues. The sum of all the eigenvalues in this group is a differentable function in this neighbourhood (see Kato(1982)). In particular, simple eigenvalues are smooth functions of x.

Remark: Cullum, Donath and Wolfe (1975) studied the case where A(x) is affine and only the diagonal elements of A(x) vary, so that m = n,

A(x) = A_{0} + diag(x_{1},…, x_{n}),

and A_{k}(x) = e_{k}e_{k}^{T} for k = 1,…, n. Using Fan’s theorem they showed that f_{κ}(x) is differentiable at x when λ_{κ} > λ_{κ+1}, and that

∂f_{κ}(x) = conv { v ∈ R^{n} : v_{k} = tr(P_{1}^{T} A_{k}(x)P_{1}) + tr(Z^{T} Q_{1}^{T} A_{k}(x)Q_{1}Z)
for k = 1,…, m and Z ∈ O_{n,t} }.  (3.33)

The relationship between (3.33) and (3.29) is precisely that already explained between (3.28) and (3.23), namely the argument of the convex hull in (3.33) is the set of extreme points of (3.29).

3.3 Necessary conditions

The standard necessary condition for x to be a local minimizer of f_{κ}, namely 0 ∈ ∂f(x) (see Clarke (1983)), implies there exists

U ∈ argmax {⟨ A(x), U ⟩ : U ∈ Φ_{n,κ}}  (3.34)

such that

⟨ A_{k}, U ⟩ = 0 for k = 1,…, m.  (3.35)

From Theorem 3.9 equations (3.34) and (3.35) are equivalent to the existence of a Ũ ∈ S_{t} such that

0 ≤ Ũ ≤ I, tr(Ũ) = κ − r,  (3.36)

and

tr(P_{1}^{T} A_{k}P_{1}) + ⟨ Q_{1}^{T} A_{k}Q_{1}, Ũ ⟩ = 0 for k = 1,…, m.  (3.37)

The conditions (3.36) and (3.37) are useful computationally as one can relax the inequalities on Ũ and solve (3.37) together with tr(Ũ) = κ − r for Ũ. This requires solving a system of m + 1 linear equations for the t(t + 1)/2 unknowns in the symmetric matrix Ũ. If the inequalities 0 ≤ Ũ ≤ I are not satisfied then a descent direction may be generated. This is discussed in Section 3.6.

If f_{κ} is convex (for example if A(x) is affine) then equations (3.36) and (3.37) are both necessary and sufficient for x to be a minimizer of f_{κ}.

3.4 A saddle point result

Consider the function

L(x, U) = ⟨ A(x), U ⟩.  (3.38)

This section establishes a saddle point result, based on well known results for Lagrangian functions in convex programming (Rockafellar (1970)). A point x^{∗} ∈ R^{m}, U^{∗} ∈ Φ_{n,κ} is a saddle point of L(x, U) if and only if

L(x^{∗}, U) ≤ L(x^{∗}, U^{∗}) ≤ L(x, U^{∗}) ∀ x ∈ R^{m} ∀ U ∈ Φ_{n,κ}.  (3.39)

It is well known and easy to show that

min_{x∈R^{m}} max_{U∈Φ_{n,κ}} L(x, U) ≥ max_{U∈Φ_{n,κ}} min_{x∈R^{m}} L(x, U).  (3.40)

The primal problem is

min_{x∈R^{n}} f_{κ}(x)  (3.41)

where

f_{κ}(x) = max_{U∈Φ_{n,κ}} L(x, U).  (3.42)

Define the dual problem to be

max_{U∈Φ_{n,κ}} h(U),  (3.43)

where

h(U) = min_{x∈R^{m}} L(x, U).  (3.44)

The following saddle point result is similar to that of Shapiro (1985) for minimizing a function of a symmetric matrix subject to positive semi-definite constraints. Indeed, it follows from the general saddle point theory for convex-concave functions (Rockafellar(1970), Theorem 36.3), but we give the proof for completeness.

Theorem 3.11 For each U ∈ Φ_{n,κ} let L(., U) be a convex function, and let the primal problem attain its solution at x^{∗}. Then the primal and dual problems have the same optimal value so

min_{x∈R^{m}} max_{U∈Φ_{n,κ}} L(x, U) = max_{U∈Φ_{n,κ}} min_{x∈R^{m}} L(x, U),  (3.45)

and U^{∗} satisfying (3.34) and (3.35) solves the dual problem (3.43).

Proof: From (3.42) f_{κ}(x) is a convex function as it is a maximum of convex functions, so 0 ∈ ∂f_{κ}(x^{∗}). Hence there exists a U^{∗} satisfying equations (3.34) and (3.35). We only have to show that (x^{∗}, U^{∗}) is a saddle point of L(x, U). From Theorem 3.4 and (3.34)

L(x^{∗}, U^{∗}) = f_{κ}(x^{∗}) ≥ L(x^{∗}, U) ∀ U ∈ Φ_{n,κ}.

The function L(., U^{∗}) is convex, so 0 ∈ ∂f_{κ}(x^{∗}) implies that L(., U^{∗}) attains its minimum at x^{∗}. This establishes (3.39).

Remark: As A(x) is a smooth function of x, so is L(., U) for any U. Hence a necessary condition for x^{∗} to be a local minimizer of L(., U) is that

⟨ A_{k}(x^{∗}), U ⟩ = 0 for k = 1,…, m.  (3.46)

If A(x) is an affine function then L(., U) is also an affine (and hence convex) function. In this case L(., U) does not have a finite minimum unless it is constant, so (3.46) holds for all x ∈ R^{m}.

3.5 The directional derivative

As f_{κ}(x) is subdifferentially regular the standard one-sided directional derivative at x in a direction d ∈ R^{m} exists and satisfies

f′_{κ}(x; d) ≡ lim_{α→0^{+}} \frac{f_{κ}(x + αd) − f_{κ}(x)}{α}
= max_{u∈∂f_{κ}(x)} u^{T} d
= ∑_{k=1}^{m} d_{k} tr(P_{1}^{T} A_{k}P_{1}) + max_{Ũ∈Φ_{t,κ−r}} ∑_{k=1}^{m} d_{k}⟨ Q_{1}^{T} A_{k}Q_{1}, Ũ ⟩. (3.47)

Recall that the matrices P_{1} and Q_{1}, defined by (3.18), are evaluated at the point x, and that A_{k} is the partial derivative of A(x) with respect to x_{k} evaluated at the point x. Define

b_{k} = tr(P_{1}^{T} A_{k}P_{1}),  B_{k} = Q_{1}^{T} A_{k}Q_{1} for k = 1,…, m  (3.48)

and define B(d) ∈ S_{t} by

B(d) = ∑_{k=1}^{m} d_{k}B_{k}.  (3.49)

Note that b^{T} d is the sum of the eigenvalues (the trace) of

∑_{k=1}^{m} d_{k} P_{1}^{T} A_{k}P_{1}.

Let the eigenvalues of B(d) be β_{1} ≥ ⋯ ≥ β_{t}. Then from (3.47) and Theorem 3.4 it follows that

f′_{κ}(x; d) = b^{T} d + ∑_{i=1}^{κ−r} β_{i}.  (3.50)

Hence f′_{κ}(x; d) is the sum of all r eigenvalues of ∑_{k=1}^{m} d_{k} P_{1}^{T} A_{k}P_{1} plus the sum of the κ − r largest eigenvalues of ∑_{k=1}^{m} d_{k} Q_{1}^{T} A_{k}Q_{1}. Note that, unless κ = r + t, this is generally not the same as the sum of the κ largest eigenvalues of

∑_{k=1}^{m} d_{k} [ \begin{matrix}P_{1}^{T} \\ Q_{1}^{T} \end{matrix} ] A_{k}[P_{1} Q_{1}].

Remark: Classical eigenvalue perturbation theory (Kato(1982)) states that, in general, as A(x) is perturbed by α ∑ d_{k}A_{k} + o(α), the multiple eigenvalue λ_{r+1} = ⋯ = λ_{r+t} splits, with the t perturbed eigenvalues having first-order changes given, respectively, by the t eigenvalues of B(d). This, together with the fact that the sum of the first r eigenvalues, being separated from λ_{r+1}, is a smooth function, provides an alternative proof of (3.50). However, the proof of these classical results is by no means straightforward.

3.6 Splitting multiple eigenvalues

Given x, it is desired to either (a) generate a descent direction for f_{κ}, or (b) demonstrate that x satisfies the first-order condition for optimality. If κ = r+t then f_{κ}(x) is differentiable; consequently it is sufficient to examine the gradient, whose entries are given by (3.29). If the gradient is zero, the first-order optimality conditions hold; conversely if it is not zero, the negative gradient provides a descent direction. We therefore consider only the nonsmooth case κ < r + t in the remainder of this section, although the following results actually apply in general (with a slight modification in the second case). When a descent direction exists, we are not particularly interested in obtaining the steepest descent direction, since it is generally advantageous to maintain the correct multiplicity when possible (by analogy with active set methods for constrained optimization). In the first of the next three cases a descent direction is generated keeping λ_{κ} of multiplicity t (to first order), while in the second case, generation of a descent direction requires splitting the group of eigenvalues corresponding to λ_{κ}.

Case 1. I ∈ Span{ B_{1},…, B_{m} }.

Solve the system

δI − ∑_{k=1}^{m} d_{k}B_{k} = 0  (3.51)

(κ − r)δ + ∑_{k=1}^{m} d_{k}b_{k} = −1.  (3.52)

This is a system of t(t + 1)/2 + 1 linear equations in m + 1 unknowns δ, d_{1},…, d_{m}. Equation (3.51) implies that the eigenvalues of B(d) defined by (3.49) are all equal to δ. The system is solvable since (3.51) is solvable for any δ by assumption, and (3.52) scales this solution. Hence, from equations (3.50) and (3.52), f′_{κ}(x; d) = −1, where the direction d ∈ R^{m} has components d_{1},…, d_{m}. Note that the −1 on the right-hand side of (3.52) is just a normalization constant and can be replaced by any η < 0 giving f′_{κ}(x; d) = η. To first order all the eigenvalues λ_{r+1}(x),…, λ_{r+t}(x) decrease at the same rate along d, and δ gives a first order estimate of the change in their common value. Case 1 holds generically if m ≥ t(t + 1)/2, that is the generic dimension of the manifold defined by

λ_{r+1}(x) = ⋯ = λ_{r+t}(x)  (3.53)

is greater than zero (see Overton and Womersley (1988), Section 2 for more detail).

Case 2. Case 1 does not apply and the span of the m + 1 vectors in R^{t(t+1)/2} associated with I, B_{1},…, B_{m} has the maximum dimension t(t + 1)/2.

Solve the linear system

tr(Ũ) = κ − r  (3.54)
−⟨ B_{k}, Ũ ⟩ = b_{k}, k = 1,…, m  (3.55)

for the dual matrix Ũ ∈ S_{t}. Note that the trace condition (3.54) is equivalent to ⟨ I, Ũ ⟩ = κ − r. Since the {B_{k}} may not form a linearly independent set, (3.55) may be replaced by considering only a maximal independent set of {B_{k}}; the system cannot be inconsistent because of the related definitions of the left and right-hand sides (B_{k} and b_{k}). By the rank assumption, the resulting linear system is square and nonsingular, with order t(t + 1)/2, and having a unique solution Ũ. If Ũ satisfies 0 ≤ Ũ ≤ I then 0 ∈ ∂f_{κ}(x), so x satisfies the first-order necessary conditions for a minimum. If these inequalities on Ũ are not satisfied then the following result shows how to generate a descent direction.

Theorem 3.12 Suppose (3.54) and (3.55) are satisfied but 0 ∉ ∂f_{κ}(x), so Ũ has an eigenvalue θ outside [0, 1]. Let z ∈ R^{t} be the corresponding normalized eigenvector of Ũ. Choose β ∈ R so that β < 0 if θ > 1 and β > 0 if θ < 0. Solve

δI − ∑_{k=1}^{m} d_{k}B_{k} = βzz^{T} .  (3.56)

Then d = [d_{1} ⋯, d_{m}]^{T} is a descent direction.

Proof: The linear system (3.56) is solvable by hypothesis, although d is unique only if the {B_{k}} are independent. Note that the coefficient matrix of the left hand side (3.56) is the transpose of that for the system (3.54), (3.55). Taking the inner product of (3.56) with Ũ gives

δ tr(Ũ) − ∑_{k=1}^{m} d_{k}⟨ B_{k}, Ũ ⟩ = β⟨ zz^{T} , Ũ ⟩,  (3.57)

so from (3.54), (3.55) and the spectral decomposition of Ũ

δ(κ − r) + b^{T} d = βθ.  (3.58)

From (3.56) B(d) = δI − βzz^{T} has eigenvalues δ − β, δ,…, δ. If β < 0 the sum of the κ − r largest eigenvalues of B(d) is δ(κ − r) − β. Hence (3.50) and (3.58) give

f′_{κ}(x; d) = β(θ − 1).  (3.59)

Thus if θ > 1 choosing β < 0 and solving (3.56) produces a descent direction. If β > 0 then, since κ < r + t, the sum of the κ − r largest eigenvalues of B(d) is δ(κ − r). Then (3.50) and (3.58) give

f′_{κ}(x; d) = βθ.  (3.60)

Therefore, if θ < 0, choosing β > 0 and solving (3.56) produces a descent direction.

Remark: For the case κ = 1 this result was given in Overton (1988) and Overton and Womersley (1988). As noted earlier the condition Ũ ≤ I is not required when κ = 1.

Remark: Progress is made by splitting the multiple eigenvalue while maintaining multiplicity t − 1 to first order, i.e., the first-order change in all the eigenvalues but one in the cluster is the same. This is analogous to moving off a single active nonlinear constraint in the context of constrained optimization. The dual matrix Ũ provides the information which leads to the generation of a descent direction, just as negative Lagrange multipliers provide similar information in constrained optimization. The distinction between the cases θ < 0 and θ > 1 is as follows: if θ < 0, one eigenvalue in the group of multiplicity t is separated from the others by a reduction, reducing the approximate multiplicity but leaving the number of eigenvalues larger than λ_{κ}, to first order, unchanged. If θ > 1 one eigenvalue is separated from the others by an increase, again reducing the approximate multiplicity but increasing the number of larger eigenvalues (to first order). In either case the theorem guarantees an overall reduction in f_{κ}.

Case 2 applies generically if m + 1 = t(t + 1)/2, i.e. the generic dimension of the manifold defined by (3.53) consists of a single point. It also applies if x minimizes f_{κ} on this manifold; see Overton (1988) for a further explanation.

Case 3. Neither of Cases 1 and 2 apply. In this case degeneracy is said to occur. Generation of a descent direction is not straightforward.

3.7 Model algorithms

Practical algorithms for minimizing f_{κ}(x) based on successive linear or quadratic programming may be defined to fully exploit the structure of the generalized gradient of f_{κ}. Such algorithms have been described and tested extensively in the case κ = 1 by Overton (1988, 1990).

Suppose that x^{∗} is a (local) minimizer of f_{κ}(x), with corresponding values r^{∗} and t^{∗} defined by (3.8). The model algorithm must use estimates, say r and t, of r^{∗} and t^{∗}. Note that, in general, the matrix iterates generated by the algorithm will have eigenvalues which are strictly multiple only in the limit at x = x^{∗}. The simplest way to estimate r and t is to use an eigenvalue separation tolerance. The basic step of a model algorithm for minimizing f_{κ}(x) then becomes the solution of the following quadratic program:

min_{d∈R^{m},δ∈R} (κ − r)δ + b^{T} d + \frac{1}{2}d^{T} Hd  (3.61)
Subject to δI − ∑_{k=1}^{m} d_{k}Q_{1}^{T} A_{k}Q_{1} = diag(λ_{r+1},…, λ_{r+t}).  (3.62)

Here H is some positive semi-definite matrix and all the quantities Q_{1}, A_{k}, λ_{i} and b (defined in (3.48)) are evaluated at the current point x. The next trial point is x + d, and δ gives an estimate of λ_{κ}(x + d).

Briefly, equation (3.62) represents the appropriate linearization of the nonlinear system

λ_{r+1}(x + d) = ⋯ = λ_{r+t}(x + d) = δ;  (3.63)

since this system is not differentiable, this needs justification (Friedland, Nocedal and Overton(1987)). The first two terms in the objective function (3.61) represent a linearization of f_{κ}(x + d), while the third term may be used to incorporate second derivative information. The Lagrange multipliers corresponding to the t(t + 1)/2 equality constraints (3.62) make up a dual matrix estimate of Ũ.

Inequalities may be included in the quadratic program, to ensure that linearizations of the first r eigenvalues (or at least their average) are no smaller than δ, and that the linearizations of λ_{r+t+1},…, are no larger than δ. A trust region constraint may be used to ensure reduction of the objective function at the trial point. It is possible to choose H so that local quadratic convergence takes place; alternatively, H can be set to zero for a first-order method using a linear programming subproblem. Further details are beyond the scope of this paper, but see Overton(1990) for the case κ = 1.

4 Sum of the largest eigenvalues in absolute value

We are now interested in functions of the form

g_{κ}(A) = ∑_{i=1}^{κ} |μ_{i}|  (4.1)

where the eigenvalues μ_{i} of A are ordered by

|μ_{1}| ≥ ⋯ ≥ |μ_{n}|.  (4.2)

Let ζ = |μ_{κ}|, the κth largest eigenvalue modulus.

One approach is to apply the results of the previous section to minimizing the sum of the κ largest eigenvalues of

[ \begin{matrix}A(x) & 0 \\ 0 & −A(x) \end{matrix} ] .

However not only is the size of the problem then doubled, but the structure of the subdifferential is lost.

The techniques in Section 4 are related to the well known idea of representing a scalar α by its positive part α_{+} = max{0, α} and its negative part α_{−} = max{0, −α}, so α = α_{+} − α_{−} and |α| = α_{+} + α_{−}. For w ∈ R^{n} the vectors w_{+} and w_{−} are defined componentwise. This is discussed further in the Appendix.

4.1 A max characterization

This section establishes a max characterization of the κ largest, in absolute value, eigenvalues of a matrix, and the elements which achieve the maximum in this characterization. Let κ ∈ {1,…, n}, and define

Ψ_{n,κ} = { W ∈ S_{n} : W = U − V, where U, V ∈ S_{n},
0 ≤ U ≤ I, 0 ≤ V ≤ I, tr(U) + tr(V) = κ }  (4.3)

and

ψ_{n,κ} = { w ∈ R^{n} : w = u − v, where u, v ∈ R^{n},
0 ≤ u ≤ e, 0 ≤ v ≤ e for i = 1,…, n, and e^{T} (u + v) = κ }. (4.4)

Lemma 4.1 Ψ_{n,κ} and ψ_{n,κ} are compact convex sets, Ψ_{n,κ} is invariant under orthogonal similarity transformations (i.e. W ∈ Ψ_{n,κ} ⟺ Z^{T} W Z ∈ Ψ_{n,κ} for any Z ∈ O_{n,n}), and Ψ_{n,κ} and ψ_{n,κ} are related by

Ψ_{n,κ} = { W ∈ S_{n} : W = U − V, U = ZDZ^{T} , V = Y EY^{T}
where Z, Y ∈ O_{n,n}, D = diag(u), E = diag(v),
0 ≤ u ≤ e, 0 ≤ v ≤ e, i = 1,…, n and e^{T} (u + v) = κ } (4.5)

and

ψ_{n,κ} = { w ∈ R^{n} : w_{i} = W_{ii} for i = 1,…, n where W ∈ Ψ_{n,κ} }. (4.6)

Proof: It is easily verified that Ψ_{n,κ} and ψ_{n,κ} are compact convex sets. A spectral decomposition of the matrices U, V ∈ S_{n} in the definition of Ψ_{n,κ} shows that

Ψ_{n,κ} = { W ∈ S_{n} : W = ZDZ^{T} − Y EY^{T}
where Z, Y ∈ O_{n,n}, D, E ∈ D_{n},
0 ≤ D ≤ I, 0 ≤ E ≤ I and tr(D) + tr(E) = κ },  (4.7)

which establishes (4.5), and the invariance of Ψ_{n,κ} to orthogonal similarity transformations. Let Ω denote the set on the right hand side of equation (4.6). Choosing Z = Y = I, D = diag(w_{+}) and E = diag(w_{−}) in (4.7) , for any w ∈ ψ_{n,κ}, shows that ψ_{n,κ} ⊆ Ω. To establish the reverse inclusion let w ∈ Ω, i.e. w_{i} = W_{ii}, where W = U −V with U,V satisfying the conditions in (4.3). Define u and v by u_{i} = U_{ii}, v_{i} = V_{ii}. Then e^{T} (u + v) = tr(U) + tr(V) = κ, and 0 ≤ u ≤ e, 0 ≤ v ≤ e, by (4.3), i.e. w ∈ ψ_{n,κ}.

To characterize the elements which achieve the maximum in the following results requires information about the multiplicity of the eigenvalues of A. Although the ordering (4.2) is useful to give the simple definition (4.1) for g_{κ}(A), as well as ζ = |μ_{κ}|, we shall now revert to the standard ordering.

Consider the case when ζ > 0 and let the eigenvalues of A be written

λ_{1} ≥ ⋯ ≥ λ_{r_{1}} >
λ_{r_{1}+1} = ⋯ = ζ = ⋯ = λ_{r_{1}+t_{1}} >
λ_{r_{1}+t_{1}+1} ≥ ⋯ ≥ λ_{n−r_{2}−t_{2}} >  (4.8)
λ_{n−r_{2}−t_{2}+1} = ⋯ = −ζ = ⋯ = λ_{n−r_{2}} >
λ_{n−r_{2}+1} ≥ ⋯ ≥ λ_{n},

where r_{1}, t_{1}, r_{2}, t_{2} are nonnegative integers. The eigenvalue equal to ζ has multiplicity t_{1} and the eigenvalue equal to −ζ has multiplicity t_{2}. By assumption there is at least one eigenvalue with modulus ζ, so t_{1} + t_{2} ≥ 1. The number of eigenvalues greater than ζ is r_{1}, while the number of eigenvalues less than −ζ is r_{2}. Note that by definition

r_{1} + r_{2} + 1 ≤ κ ≤ r_{1} + t_{1} + r_{2} + t_{2}.  (4.9)

Thus r_{1} = r_{2} = 0 if κ = 1. Also if t_{1} = 1 and t_{2} = 0, or t_{1} = 0 and t_{2} = 1 then κ = r_{1} + r_{2} + 1.

We have λ_{i} > 0 for i = 1,…, r_{1} + t_{1} and λ_{i} < 0 for i = n − r_{2} − t_{2} + 1,…, n. Thus

g_{κ}(A) = ∑_{i=1}^{κ} |μ_{i}| = ∑_{i=1}^{r_{1}} λ_{i} − ∑_{i=n−r_{2}+1}^{n} λ_{i} + (κ − r_{1} − r_{2})ζ.  (4.10)

Example 4.2 Suppose n = 11 and λ^{T} = (5, 4, 4, 4, 2, −1, −4, −4, −6, −6, −7). If κ = 2 or 3 then ζ = 6, r_{1} = 0, t_{1} = 0, r_{2} = 1 and t_{2} = 2. If κ = 5, 6, or 7 then ζ = 4, r_{1} = 1, t_{1} = 3, r_{2} = 3 and t_{2} = 2.

If ζ = 0 then the appropriate ordering is

λ_{1} ≥ ⋯ ≥ λ_{r_{1}} >
λ_{r_{1}+1} = ⋯ = 0 = ⋯ = λ_{r_{1}+t} >  (4.11)
λ_{n−r_{2}+1} ≥ ⋯ ≥ λ_{n},

and n − r_{2} = r_{1} + t. Only the situation where ζ > 0 will be considered in the rest of this section. The modifications required when ζ = 0 can be derived from the ordering (4.11).

We first give two lemmas which depend only on the orderings (4.2), (4.8) for a single set of n real numbers, and not on the fact that these are eigenvalues of a matrix A.

Lemma 4.3 If the vector λ ∈ R^{n} is ordered as in (4.8) then

max_{w∈ψ_{n,κ}} λ^{T} w = ∑_{i=1}^{κ} |μ_{i}|

and

argmax { λ^{T} w : w ∈ ψ_{n,κ} } = { w ∈ R^{n} :
w_{i} = 1 for i = 1,…, r_{1},
0 ≤ w_{i} ≤ 1 for i = r_{1} + 1,…, r_{1} + t_{1},
w_{i} = 0 for i = r_{1} + t_{1} + 1,…, n − r_{2} − t_{2},
−1 ≤ w_{i} ≤ 0 for i = n − r_{2} − t_{2} + 1,…, n − r_{2},
w_{i} = −1 for i = n − r_{2} + 1,…, n and
∑_{i=r_{1}+1}^{r_{1}+t_{1}} w_{i} − ∑_{i=n−r_{2}−t_{2}+1}^{n−r_{2}} w_{i} = κ − r_{1} − r_{2} }.(4.12)

Proof: The result follows directly from (4.2), (4.8) and the definition (4.4) of ψ_{n,κ}.

Lemma 4.4 Let Λ = diag(λ). Then

max_{W ∈Ψ_{n,κ}} ⟨ Λ, W ⟩ = ∑_{i=1}^{κ} |μ_{i}|  (4.13)

and

argmax { ⟨ Λ, W ⟩ : W ∈ Ψ_{n,κ} } =
{ W ∈ S_{n} : W = U − V, where
U = diag(I, Ũ, 0, 0, 0), Ũ ∈ S_{t_{1}}, 0 ≤ Ũ ≤ I,
V = diag(0, 0, 0, Ṽ , I), Ṽ ∈ S_{t_{2}}, 0 ≤ Ṽ ≤ I,
tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2} }.  (4.14)

Here the diagonal blocks of U and V have dimensions r_{1}, t_{1}, n − r_{1} − t_{1} − t_{2} − r_{2}, t_{2} and r_{2} respectively.

Proof: As Λ = diag(λ)

⟨ Λ, W ⟩ = ∑_{i=1}^{n} λ_{i}W_{ii}.

Equation (4.13) follows from Lemmas 4.1 and 4.3.

If W^{∗} is any element of the right hand side of (4.14) then from (4.8) and (4.10)

⟨ Λ, W^{∗} ⟩ = ∑_{i=1}^{r_{1}} λ_{i} + ζtr(Ũ) + ζtr(Ṽ) − ∑_{i=n−r_{2}+1}^{n} λ_{i} = ∑_{i=1}^{κ} |μ_{i}|.  (4.15)

Conversely let W^{∗} ∈ argmax { ⟨ Λ, W ⟩ : W ∈ Ψ_{n,κ} }. Then w^{∗} = (W_{11}^{∗}… W_{nn}^{∗})^{T} ∈ ψ_{n,κ} satisfies λ^{T} w^{∗} = ∑_{i=1}^{κ} |μ_{i}|, and therefore also satisfies the properties given on the right-hand side of (4.12). Furthermore, W^{∗} has the representation W^{∗} = U^{∗} − V^{∗}, where 0 ≤ U^{∗} ≤ I, 0 ≤ V^{∗} ≤ I, tr(U^{∗}) + tr(V^{∗}) = κ, so

U_{ii}^{∗} = 1, V_{ii}^{∗} = 0 for i = 1,…, r_{1},

0 ≤ U_{ii}^{∗} ≤ 1, V_{ii}^{∗} = 0 for i = r_{1} + 1,…, r_{1} + t_{1},

U_{ii}^{∗} = 0, V_{ii}^{∗} = 0 for i = r_{1} + t_{1} + 1,…, n − r_{2} − t_{2},  (4.16)

U_{ii}^{∗} = 0, 0 ≤ V_{ii}^{∗} ≤ 1 for i = n − r_{2} − t_{2} + 1,…, n − r_{2},

U_{ii}^{∗} = 0, V_{ii}^{∗} = 1 for i = n − r_{2} + 1,…, n and

∑_{i=r_{1}+1}^{r_{1}+t_{1}} U_{ii}^{∗} + ∑_{i=n−r_{2}−t_{2}+1}^{n−r_{2}} V_{ii}^{∗} = κ − r_{1} − r_{2} }.

Partition the rows and columns of W^{∗} = U^{∗} − V^{∗} into blocks so

U^{∗} = [ \begin{matrix}C_{11} & C_{12} & C_{13} & C_{14} & C_{15} \\ C_{12}^{T} & C_{22} & C_{23} & C_{24} & C_{25} \\ C_{13}^{T} & C_{23}^{T} & C_{33} & C_{34} & C_{35} \\ C_{14}^{T} & C_{24}^{T} & C_{34}^{T} & C_{44} & C_{45} \\ C_{15}^{T} & C_{25}^{T} & C_{35}^{T} & C_{45}^{T} & C_{55} \end{matrix} ] , V^{∗} = [ \begin{matrix}E_{11} & E_{12} & E_{13} & E_{14} & E_{15} \\ E_{12}^{T} & E_{22} & E_{23} & E_{24} & E_{25} \\ E_{13}^{T} & E_{23}^{T} & E_{33} & E_{34} & E_{35} \\ E_{14}^{T} & E_{24}^{T} & E_{34}^{T} & E_{44} & E_{45} \\ E_{15}^{T} & E_{25}^{T} & E_{35}^{T} & E_{45}^{T} & E_{55} \end{matrix} ]

where the dimensions of the symmetric matrices C_{ii} and E_{ii} for i = 1,…, 5 are respectively r_{1}, t_{1}, n − r_{1} − t_{1} − r_{2} − t_{2}, t_{2} and r_{2}. As W^{∗} ∈ Ψ_{n,κ}

0 ≤ C_{ii} ≤ I, i = 1,…, 5 0 ≤ E_{ii} ≤ I, i = 1,…, 5

∑_{i=1}^{5} tr(C_{ii}) + ∑_{i=1}^{5} tr(E_{ii}) = κ.

As in Section 3 the proof is completed using the basic results (3.16) and (3.17) for positive semi-definite matrices. From (4.16) C_{11} = I, as C_{11} ≤ I and the diagonal elements of C_{11} are all 1. Then as U^{∗} ≤ I, C_{11} = I implies that C_{1j} = 0 for all j ≠ 1. For i = 3, 4, 5 C_{ii} = 0, as C_{ii} ≥ 0 and the diagonal elements of C_{ii} are all zero. Then for i = 3, 4, 5 U^{∗} ≥ 0 and C_{ii} = 0 imply that C_{ij} = 0 for all j ≠ i. Similarly E_{ii} = 0 for i = 1, 2, 3 and E_{55} = I. Then 0 ≤ V^{∗} ≤ I implies that E_{ij} = 0 for all i ≠ j. The matrices U^{∗} and V^{∗} now reduced to those given in (4.14). The trace condition comes directly from (4.16).

Now consider sums of the eigenvalues of A, and recall that Q ∈ O_{n,n} is a matrix of eigenvectors for A satisfying

Q^{T} AQ = Λ.  (4.17)

Let P_{1} ∈ O_{n,r_{1}}, P_{2} ∈ O_{n,r_{2}} be the matrices consisting of the first r_{1} and last r_{2} columns of Q respectively. Also let Q_{1} ∈ O_{n,t_{1}} be the matrix consisting of columns r_{1} + 1,…, r_{1} + t_{1} of Q, and let Q_{2} ∈ O_{n,t_{2}} be the matrix consisting of columns n − r_{2} − t_{2} + 1,…, n − r_{2} of Q. By (4.8) we have

P_{1}^{T} AP_{1} = diag(λ_{1},…, λ_{r_{1}}), P_{2}^{T} AP_{2} = diag(λ_{n−r_{2}+1},…, λ_{n}),  (4.18)

and

Q_{1}^{T} AQ_{1} = ζI, Q_{2}^{T} AQ_{2} = −ζI.  (4.19)

Theorem 4.5

max_{W ∈Ψ_{n,κ}}⟨ A, W ⟩ = g_{κ}(A),  (4.20)

with

argmax { ⟨ A, W ⟩ : W ∈ Ψ_{n,κ} } =
{ W ∈ S_{n} : W = U − V, where U, V ∈ S_{n}
U = P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T} , V = P_{2}P_{2}^{T} + Q_{2}Ṽ Q_{2}^{T} ,
Ũ ∈ S_{t_{1}}, 0 ≤ Ũ ≤ I, Ṽ ∈ S_{t_{2}}, 0 ≤ Ṽ ≤ I
and tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2} }.  (4.21)

Proof: For any W ∈ Ψ_{n,κ} equation (4.17) and the properties of the Frobenius inner product imply that

⟨ A, W ⟩ = ⟨ QΛQ^{T} , W ⟩ = ⟨ Λ, Q^{T} W Q ⟩,  (4.22)

with Q^{T} W Q ∈ Ψ_{n,κ} as Ψ_{n,κ} is invariant to orthogonal similarity transformations. Hence

max_{W ∈Ψ_{n,κ}} ⟨ A, W ⟩ = max_{W ∈Ψ_{n,κ}} ⟨ Λ, W ⟩ = g_{κ}(A),

where the second equality follows from Lemma 4.4.

From (4.22) and the invariance of Ψ_{n,κ} to orthogonal transformations

argmax { ⟨ A, W ⟩ : W ∈ Ψ_{n,κ} } = { QW^{∗}Q^{T} : W^{∗} ∈ Ω }

where Ω = argmax { ⟨ Λ, W ⟩ : W ∈ Ψ_{n,κ} }. The proof is completed by applying Lemma 4.4 since

QW^{∗}Q^{T} = Q diag(I, Ũ, 0, 0, 0) Q^{T} − Q diag(0, 0, 0, Ṽ , I) Q^{T}
= P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T} − Q_{2}Ṽ Q_{2}^{T} − P_{2}P_{2}^{T} .

Remark: If κ = r_{1} + r_{2} + t_{1} + t_{2} then Ũ = I, Ṽ = I and

argmax { ⟨ A, W ⟩ : W ∈ Ψ_{n,κ} } = P_{1}P_{1}^{T} + Q_{1}Q_{1}^{T} − Q_{2}Q_{2}^{T} − P_{2}P_{2}^{T} .  (4.23)

The matrix achieving the maximum in (4.13) is unique only in this case. It is precisely the case when g_{κ}(A) is a smooth function of the elements of A.

Remark: If t_{1} = 1, t_{2} = 1, and κ = r_{1}+r_{2}+1, then Ũ = α, Ṽ = β where α, β ∈ R satisfy α, β ∈ [0, 1] and α + β = κ − r_{1} − r_{2} = 1. Also

argmax { ⟨ A, W ⟩ : W ∈ Ψ_{n,κ} } = P_{1}P_{1}^{T} + αQ_{1}Q_{1}^{T} − βQ_{2}Q_{2}^{T} − P_{2}P_{2}^{T}; (4.24)

here Q_{1} and Q_{2} have only one column. This is precisely the case when g_{κ}(A) is nonsmooth but is the maximum of a finite number of smooth functions (λ_{r_{1}+1} and −λ_{n−r_{2}}).

Remark: When t_{1} > 1 or t_{2} > 1 all the flexibility in the choices of Q_{1} and Q_{2} in (4.19) is absorbed into the matrices Ũ and Ṽ. It makes no difference if any of the eigenvalues λ_{1},…, λ_{r_{1}} or λ_{n−r_{2}+1},…, λ_{n} have multiplicity greater than 1, as all these multiple eigenvalues are included in g_{κ}(A) and the corresponding columns of P_{1} or P_{2} can be any orthonormal basis for the corresponding eigenspace.

Corollary 4.6 The function g_{κ}(A) : S_{n} → R is convex and its subdifferential ∂g_{κ}(A) is the nonempty compact convex set

∂g_{κ}(A) = { W ∈ S_{n} : there exists
Ũ ∈ S_{t_{1}} with 0 ≤ Ũ ≤ I,
Ṽ ∈ S_{t_{2}} with 0 ≤ Ṽ ≤ I,
tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2},
W = P_{1}P_{1}^{T} + Q_{1}ŨQ_{1}^{T} − Q_{2}Ṽ Q_{2}^{T} − P_{2}P_{2}^{T} }.  (4.25)

Proof: For any W ∈ Ψ_{n,κ} the inner product ⟨ A, W ⟩ is a linear function of A ∈ S_{n}, so from Rockafellar (1970) g_{κ}(A) is a convex function of A. Moreover the subdifferential is

∂g_{κ}(A) = conv { W ∈ S_{n} : ⟨ A, W ⟩ = g_{κ}(A) }.

The result follows from Theorem 4.5 as the set on the right hand side of (4.25) is already convex.

As in Section 3 there are various equivalent forms for the argmax involving a convex hull operation, which are discussed in the Appendix. These lead to equivalent, but computationally less useful, expressions for ∂g_{κ}(A).

4.2 The generalized gradient

As in Section 3.2 let A(x) : R^{m} → S_{n} be a continuously differentiable function with partial derivatives

A_{k}(x) ≡ \frac{∂A(x)}{∂x_{k}} for k = 1,…, m.

This section is concerned with finding a computationally useful characterization of the generalized gradient of the function

g_{κ}(x) = g_{κ}(A(x)).

The eigenvalues of A(x) are, as before, denoted by by both (4.2) and (4.8), with r_{1}, t_{1}, r_{2}, t_{2} now dependent on x, and with the corresponding eigenvectors satisfying (4.18), (4.19). Thus the explicit dependence of the eigensystem of A(x) on x is generally omitted.

Theorem 4.7 The function g_{κ}(x) is locally Lipschitz, subdifferentially regular, and its generalized gradient is the nonempty compact convex set

∂g_{κ}(x) = { w ∈ R^{m} : ∃ Ũ ∈ S_{t_{1}}, Ṽ ∈ S_{t_{2}} with  (4.26)
0 ≤ Ũ ≤ I, 0 ≤ Ṽ ≤ I, tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2},
and for k = 1,…, m
w_{k} = tr(P_{1}^{T} A_{k}(x)P_{1}) + ⟨ Q_{1}^{T} A_{k}(x)Q_{1}, Ũ ⟩
− tr(P_{2}^{T} A_{k}(x)P_{2}) − ⟨ Q_{2}^{T} A_{k}(x)Q_{2}, Ṽ ⟩ }.  (4.27)

Proof: By the Clarke chain rule, g_{κ}(x) is locally Lipschitz, subdifferentially regular, and

∂g_{κ}(x) = { w ∈ R^{m} : w_{k} = ⟨ A_{k}(x), W ⟩,: W ∈ ∂g_{κ}(A(x)) }.

Corollary 4.6 and the properties of the inner product complete the proof.

Corollary 4.8 If κ = r_{1} + t_{1} + r_{2} + t_{2} then the function g_{κ}(x) is differentiable at x with

\frac{∂g(x)}{∂x_{k}} = tr(P_{1}^{T} A_{k}(x)P_{1}) + tr(Q_{1}^{T} A_{k}(x)Q_{1})
−tr(Q_{2}^{T} A_{k}(x)Q_{2}) − tr(P_{2}^{T} A_{k}(x)P_{2}).  (4.28)

Proof: This is precisely the case when (4.21) and hence ∂g_{κ}(x) is a singleton. Hence g_{κ}(x) is differentiable, and (4.27) reduces to (4.28).

4.3 Necessary conditions

If x is a local minimizer of g_{κ} then the standard necessary condition 0 ∈ ∂g_{κ}(x) and Theorem 4.7 imply there exist Ũ ∈ S_{t_{1}} and Ṽ ∈ S_{t_{2}} such that

0 ≤ Ũ ≤ I, 0 ≤ Ṽ ≤ I,  (4.29)
tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2},  (4.30)

and for k = 1,…, m

0 = tr(P_{1}^{T} A_{k}(x)P_{1}) + ⟨ Q_{1}^{T} A_{k}(x)Q_{1}, Ũ ⟩
− tr(P_{2}^{T} A_{k}(x)P_{2}) − ⟨ Q_{2}^{T} A_{k}(x)Q_{2}, Ṽ ⟩.  (4.31)

These conditions are useful computationally as one can relax the inequalities on Ũ and Ṽ and solve (4.30) and (4.31) for Ũ and Ṽ. This requires solving a system of m+1 linear equations for the t_{1}(t_{1} +1)/2 + t_{2}(t_{2} +1)/2 unknowns in the symmetric matrices Ũ and Ṽ. When κ = 1 these are the same conditions as those used in Overton (1988). If the inequalities 0 ≤ Ũ ≤ I or 0 ≤ Ṽ ≤ I are not satisfied then this information can be used to generate a descent direction; see Section 4.6.

If g_{κ}(x) is convex (e.g. if A(x) is affine) then equations (4.29), (4.30) and (4.31) are both necessary and sufficient for x to be a minimizer of g_{κ}(x).

4.4 A saddle point result

As in Section 3.4 it is possible to establish saddle point results for the Lagrangian function

L(x, W) = ⟨ A(x), W ⟩,  (4.32)

where W ∈ Ψ_{n,κ}. The primal problem is

min_{x∈R^{n}} g_{κ}(x)  (4.33)

where

g_{κ}(x) = max_{W ∈Ψ_{n,κ}} L(x, W).  (4.34)

The dual problem is

max_{W ∈Ψ_{n,κ}} h(W),  (4.35)

where

h(W) = min_{x∈R^{m}} L(x, W).  (4.36)

Theorem 4.9 For each W ∈ Ψ_{n,κ} let L(., W) be a convex function, and let the primal problem attain its solution at x^{∗}. Then the primal and dual problems have the same optimal value so

min_{x∈R^{m}} max_{W ∈Ψ_{n,κ}} L(x, W) = max_{W ∈Ψ_{n,κ}} min_{x∈R^{m}} L(x, W),  (4.37)

and W^{∗} ∈ argmax{ ⟨ A(x^{∗}), W ⟩ : W ∈ Ψ_{n,κ} } satisfying ⟨ A_{k}(x^{∗}), W^{∗} ⟩ = 0 for k = 1,…, m solves the dual problem.

Proof: Analogous to the proof of Theorem 3.11.

4.5 The directional derivative

As g_{κ}(x) is subdifferentially regular the standard one-sided directional derivative g′_{κ}(x; d) at x in a direction d ∈ R^{m} exists and satisfies

g′_{κ}(x; d) = max_{w∈∂g_{κ}(x)} w^{T} d
= ∑_{k=1}^{m} d_{k} [tr(P_{1}^{T} A_{k}P_{1}) − tr(P_{2}^{T} A_{k}P_{2})] +
max_{Ũ,Ṽ} ∑_{k=1}^{m} d_{k}[⟨ Q_{1}^{T} A_{k}Q_{1}, Ũ ⟩ − ⟨ Q_{2}^{T} A_{k}Q_{2}, Ṽ ⟩],  (4.38)

where the maximum is over all Ũ ∈ S_{t_{1}}, Ṽ ∈ S_{t_{2}} satisfying

0 ≤ Ũ ≤ I, 0 ≤ Ṽ ≤ I and tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2}.  (4.39)

Recall that the matrices P_{1}, P_{2} and Q_{1}, Q_{2} are evaluated at the point x, and that A_{k} is the partial derivative of A(x) with respect to x_{k} evaluated at the point x. For k = 1,…, m define

b_{k} = tr(P_{1}^{T} A_{k}P_{1}) − tr(P_{2}^{T} A_{k}P_{2}),  (4.40)

and

B_{k} = [ \begin{matrix}Q_{1}^{T} A_{k}Q_{1} & 0 \\ 0 & −Q_{2}^{T} A_{k}Q_{2} \end{matrix} ] .  (4.41)

Note that B_{k} ∈ S_{t_{1}+t_{2}}. Let

B(d) = ∑_{k=1}^{m} d_{k}B_{k},  (4.42)

and let the eigenvalues of B(d) be γ_{1}, ≥ … ≥ γ_{t_{1}+t_{2}}. Also let

T = [ \begin{matrix}Ũ & 0 \\ 0 & Ṽ \end{matrix} ] .  (4.43)

Then from Theorem 4.5 and (4.38) and (4.39) it follows that

g′_{κ}(x; d) = b^{T} d + max_{T} ⟨ B(d), T ⟩

where the maximum is over all matrices T satisfying (4.39) and (4.43). Since B(d) is block diagonal, the maximum may equivalently be taken over matrices T ∈ Φ_{t_{1}+t_{2},κ−r_{1}−r_{2}}. Hence the directional derivative is

g′_{κ}(x; d) = b^{T} d + ∑_{i=1}^{κ−r_{1}−r_{2}} γ_{i},  (4.44)

the sum of all r_{1} eigenvalues of ∑_{k=1}^{m} d_{k} P_{1}^{T} A_{k}P_{1} minus the sum of all r_{2} eigenvalues of ∑_{k=1}^{m} d_{k} P_{2}^{T} A_{k}P_{2} plus the sum of the κ − r_{1} − r_{2} largest eigenvalues of B(d).

4.6 Splitting multiple eigenvalues

This section discusses the generation of a descent direction from points where the first-order optimality conditions do not hold. In the first case a descent direction is generated keeping the eigenvalues corresponding to ζ of multiplicity t_{1}, and the eigenvalues corresponding to −ζ of multiplicity t_{2} (to first order). The second case requires splitting at least one eigenvalue away from the common value ±ζ.

When g_{κ}(x) is differentiable (κ = r_{1} +t_{1} +t_{2} +r_{2}) and the gradient is nonzero its negative provides a descent direction. Therefore we only consider the nonsmooth case κ < r_{1} + t_{1} + t_{2} + r_{2}.

Case 1. I ∈ Span{ B_{1},…, B_{m} }.

Solve the system

δI − ∑_{k=1}^{m} d_{k}B_{k} = 0  (4.45)
(κ − r_{1} − r_{2})δ + ∑_{k=1}^{m} d_{k}b_{k} = −1.  (4.46)

Noting the structure of B_{k} in (4.41) this is a system of t_{1}(t_{1} + 1)/2 + t_{2}(t_{2} + 1)/2 linear equations in m + 1 unknowns δ, d_{1},…, d_{m}. Equation (4.45) implies that the eigenvalues of B(d) defined by (4.42) are all equal to δ. Hence from equation (4.44) and (4.46) g′_{κ}(x; d) = −1 where the direction d ∈ R^{m} has components d_{1},…, d_{m}. To first order all the eigenvalues λ_{r_{1}+1}(x),…, λ_{r_{1}+t_{1}}(x) decrease at the same rate along d, and all the eigenvalues λ_{n−r_{2}−t_{2}+1}(x),…, λ_{n−r_{2}}(x) increase at the same rate along d. Thus δ gives a first order estimate of the change in ζ along d. This case holds generically if the manifold defined by

λ_{r_{1}+1}(x) = ⋯ = λ_{r_{1}+t_{1}}(x) = ζ  (4.47)

and

λ_{n−r_{2}−t_{2}+1}(x) = ⋯ = λ_{n−r_{2}}(x) = −ζ  (4.48)

has dimension greater than zero, so m ≥ t_{1}(t_{1} + 1)/2 + t_{2}(t_{2} + 1)/2.

Case 2. Case 1 does not apply and { I, B_{1},…, B_{m} } has full rank t_{1}(t_{1} + 1)/2 + t_{2}(t_{2} + 1)/2.

Solve the linear system

tr(Ũ) + tr(Ṽ) = κ − r_{1} − r_{2}  (4.49)
− ⟨ B_{k}, T ⟩ = b_{k} k = 1,…, m  (4.50)

for the dual matrices Ũ ∈ S_{t_{1}} and Ṽ ∈ S_{t_{2}}, where T is defined by (4.43). This is a system of m + 1 equations in t_{1}(t_{1} + 1)/2 + t_{2}(t_{2} + 1)/2 unknowns. A similar argument to that given in Section 3.6 shows that a unique solution exists. If Ũ satisfies 0 ≤ Ũ ≤ I and Ṽ satisfies 0 ≤ Ṽ ≤ I then 0 ∈ ∂g_{κ}(x), so x is a stationary point.

Theorem 4.10 Suppose (4.49) and (4.50) are satisfied but 0 ∉ ∂g_{κ}(x), so either Ũ or Ṽ has an eigenvalue outside [0, 1].

If an eigenvalue θ of Ũ lies outside [0, 1], let z ∈ R^{t_{1}} be the corresponding normalized eigenvector of Ũ. Let β ∈ R and solve

δI − ∑_{k=1}^{m} d_{k}B_{k} = [ \begin{matrix}βzz^{T} & 0 \\ 0 & 0 \end{matrix} ] .  (4.51)

Alternatively if an eigenvalue η of Ṽ lies outside [0, 1], let y ∈ R^{t_{2}} be the corresponding normalized eigenvector of Ṽ. Let β ∈ R and solve

δI − ∑_{k=1}^{m} d_{k}B_{k} = [ \begin{matrix}0 & 0 \\ 0 & βyy^{T} \end{matrix} ] .  (4.52)

Then β can be chosen so d = [d_{1} ⋯, d_{m}]^{T} is a descent direction.

Proof: First consider the case when an eigenvalue θ of Ũ lies outside [0, 1]. The linear system (4.51) is solvable by hypothesis, although d is not unique if {B_{k}}, k = 1,…, m, are linearly dependent. Taking an inner product of (4.51) with T defined in (4.43) gives

δ tr(T) − ∑_{k=1}^{m} d_{k}⟨ B_{k}, T ⟩ = β⟨ zz^{T} , Ũ ⟩,

so from (4.49) and (4.50)

δ(κ − r_{1} − r_{2}) + b^{T} d = βθ.  (4.53)

From (4.42) and (4.51)

B(d) = δI − [ \begin{matrix}βzz^{T} & 0 \\ 0 & 0 \end{matrix} ]

has t_{1} + t_{2} eigenvalues δ − β, δ,…, δ.

If β < 0, the sum of the κ−r_{1}−r_{2} largest eigenvalues of B(d) is δ(κ−r_{1}−r_{2})−β. Hence (4.44) and (4.53) give

g′_{κ}(x; d) = β(θ − 1)  (4.54)

Thus if θ > 1 choosing β < 0 and solving (4.51) produces a descent direction.

On the other hand, if β > 0, the sum of the κ − r_{1} − r_{2} largest eigenvalues of B(d) is δ(κ − r_{1} − r_{2}). Then (4.44) and (4.53) give

g′_{κ}(x; d) = βθ.  (4.55)

Thus if θ < 0 choosing β > 0 and solving (4.51) produces a descent direction.

The proof follows the same lines when an eigenvalue η of Ṽ lies outside [0, 1] and (4.52) is solved instead of (4.51).

Remark: In general, the system (4.51) splits the multiple eigenvalue λ_{r_{1}+1} = … = λ_{r_{1}+t_{1}} = ζ, to first order, reducing the approximate multiplicity by one, while (4.52) splits λ_{n−r_{2}−t_{2}+1} = … = λ_{n−r_{2}} = −ζ. A special case occurs when t_{1} = t_{2} = 1 (and consequently, by assumption, κ = r_{1} + r_{2} + 1). In this case both eigenvalues already have multiplicity one, but the direction d splits the common value ζ = λ_{r_{1}+1} = −λ_{n−r_{2}}.

Remark: For the case κ = 1 this result was given by Overton (1988). In the previous work with κ = 1 the inequalities Ũ ≤ I and Ṽ ≤ I did not appear. This is because κ = 1 implies r_{1} = r_{2} = 0 and the conditions tr(Ũ) + tr(Ṽ) = 1, Ũ ≥ 0 and Ṽ ≥ 0 imply that Ũ ≤ I and Ṽ ≤ I.

Case 3. Neither of Cases 1 or 2 apply. In this case degeneracy is said to occur. Generation of a descent direction is not straightforward.

4.7 Model algorithms

As in Section 3.7 algorithms for minimizing g_{κ}(x) may be developed based on successive linear or quadratic programming.

Suppose that x^{∗} is a (local) minimizer of g_{κ}(x), with corresponding values r_{1}^{∗}, r_{2}^{∗}, t_{1}^{∗} and t_{2}^{∗} (defined by (4.8)). The model algorithm must use estimates, say r_{1}, r_{2}, t_{1} and t_{2}, of these quantities. Note that, in general, the matrix iterates generated by the algorithm will have eigenvalues which are strictly multiple only in the limit at x = x^{∗}.

The basic step of a model algorithm for minimizing g_{κ}(x) then becomes the solution of the following linear or quadratic program:

min_{d∈R^{m},δ∈R} (κ − r_{1} − r_{2})δ + b^{T} d + \frac{1}{2}d^{T} Hd  (4.56)
δI − ∑_{k=1}^{m} d_{k}Q_{1}^{T} A_{k}Q_{1} = diag(λ_{r_{1}+1},…, λ_{r_{1}+t_{1}})  (4.57)
δI + ∑_{k=1}^{m} d_{k}Q_{2}^{T} A_{k}Q_{2} = −diag(λ_{n−r_{2}−t_{2}+1},…, λ_{n−r_{2}}) (4.58)

(4.59)

Here the quantities Q_{1}, Q_{2}, λ_{i} and b (defined by (4.40)) are evaluated at the current point x. The new trial point is x + d, and δ is an estimate of ζ evaluated at the point x + d.

Equation (4.57) represents the appropriate linearization of the nonlinear system

λ_{r_{1}+1}(x + d) = ⋯ = λ_{r_{1}+t_{1}}(x + d) = δ,  (4.60)

while (4.58) is the linearization of

λ_{n−r_{2}−t_{2}+1}(x + d) = ⋯ = λ_{n−r_{2}}(x + d) = −δ.  (4.61)

The first two terms in the objective function (4.56) represent a linearization of g_{κ}(x + d), while the third term may be used to incorporate second derivative information. The Lagrange multipliers corresponding to the t_{1}(t_{1} + 1)/2 equality constraints (4.57) make up a dual matrix estimate of Ũ, while the Lagrange multipliers corresponding to the t_{2}(t_{2} + 1)/2 equality constraints (4.58) make up a dual matrix estimate of Ṽ.

Inequalities may be added to the quadratic program to ensure that linearizations of the inequalities λ_{i}(x + d) ≥ δ for i = 1,…, r_{1}, −δ ≤ λ_{i}(x + d) ≤ δ for i = r_{1} + t_{1} + 1,…, n − r_{2} − t_{2} and λ_{i}(x + d) ≤ −δ for i = n − r + 2 + 1,…, n are satisfied. A trust region constraint may be added to ensure a reduction in the objective function at the trial point. See Overton (1990) for further explanation of these ideas.

A Appendix

This Appendix discusses further properties of the sets ψ_{n,κ} and Ψ_{n,κ} which, while not needed in the derivation of the subdifferential of g_{κ}(A) given in Section 4.1, are of some independent interest. They lead to an alternative representation for the subdifferential of g_{κ}(A), in much the same way that Fan’s theorem was obtained in Section 3.1 as a corollary of our main results and led to (3.28), the alternative form for the subdifferential of f_{κ}(A).

As already mentioned, the techniques in Section 4 are related to the idea of representing a scalar α by its positive part α_{+} = max{0, α} and its negative part α_{−} = max{0, −α}, so α = α_{+} − α_{−} and |α| = α_{+} + α_{−}. The same definition applies to a vector componentwise, and, as will be seen, can also be extended in a natural way to matrices.

Consider the set

ξ_{n,κ} = { w ∈ R^{n} : −e ≤ w ≤ e, ∑_{i=1}^{n} |w_{i}| = κ }.  (A.1)

It is immediately apparent that ξ_{n,κ} ⊆ ψ_{n,κ}, since for any w ∈ ξ_{n,κ}, setting u = w_{+}, v = w_{−} satisfies the requirements w = u−v, 0 ≤ u ≤ e, 0 ≤ v ≤ e, and e^{T} (u+v) = κ. However, the example n = κ = 1 and u = 0.75, v = 0.25 shows that the converse does not hold, since w = 0.5 ∈ ψ_{n,κ}, but w ∉ ξ_{n,κ}. Instead, the following holds:

Lemma A.1

ψ_{n,κ} = { w ∈ R^{n} : −e ≤ w ≤ e, ∑_{i=1}^{n} |w_{i}| ≤ κ }.  (A.2)

Proof: Let w ∈ ψ_{n,κ}, so w = u − v, 0 ≤ u ≤ e, 0 ≤ v ≤ e, and e^{T} (u + v) = κ. Then

|w_{i}| = |u_{i} − v_{i}| ≤ max{u_{i}, v_{i}} ≤ u_{i} + v_{i}

so w is an element of the right-hand side of (A.2). Conversely, if w is an element of the right-hand side, the following algorithm produces vectors u and v which demonstrate that w = u − v ∈ ψ_{n,κ}.

Δ := κ − ∑_{i=1}^{n} |w_{i}|

For i = 1,…, n do

α := \frac{1}{2} min\{1 − |w_{i}|, Δ\}
u_{i} := [w_{i}]_{+} + α
v_{i} := [w_{i}]_{−} + α
Δ := Δ − 2α.

Each step enforces w_{i} = u_{i} −v_{i} , 0 ≤ u_{i} ≤ 1, 0 ≤ v_{i} ≤ 1 but increases e^{T} (u+v) until it equals κ. Note that Δ must be nonnegative initially and zero on termination (since ∑_{i=1}^{n} |w_{i}| ≤ κ ≤ n).

An immediate corollary is

Corollary A.2 The set of extreme points of the compact convex set ψ_{n,κ} is

{ w ∈ R^{n} : w_{i} ∈ {0, ±1}, for i = 1,…, n, ∑_{i=1}^{n} |w_{i}| = κ },

that is the n-vectors with κ_{1} elements equal to +1, κ_{2} elements equal to −1, and all other elements equal to zero, where κ_{1} ≥ 0, κ_{2} ≥ 0 and κ_{1} + κ_{2} = κ.

These results are now extended to the set Ψ_{n,κ}, by consideration of the eigenvalues of W = U − V. The first step is the following lemma, for which it is necessary to order the eigenvalues of U, V and W so as to be able to exploit a classical result of Weyl. (The last statement in this lemma is not actually needed but is included for completeness.)

Lemma A.3 Let W = U − V, where U ≥ 0, V ≥ 0 and tr(U) + tr(V) = κ. Let σ_{1} ≥ ⋯ ≥ σ_{n}, τ_{1} ≥ ⋯ ≥ τ_{n}, and ω_{1} ≥ ⋯ ≥ ω_{n} respectively denote the eigenvalues of U, the eigenvalues of V and the eigenvalues of W = U − V. Then

∑_{i=1}^{n} |ω_{i}| ≤ κ.  (A.3)

Moreover, equality holds in (A.3) if and only if, for i = 1,…, n,

σ_{i}τ_{n−i+1} = 0  (A.4)

and

ω_{i} = \{ \begin{matrix}σ_{i} & if σ_{i} > 0; \\ 0 & if σ_{i} = τ_{n−i+1} = 0; \\ −τ_{n−i+1} & if τ_{n−i+1} > 0. \end{matrix}  (A.5)

Proof: Weyl’s theorem (see e.g. Horn and Johnson (1985), Section 4.3) shows that for j = 1,…, n

σ_{n} − τ_{n−j+1} ≤ ω_{j} ≤ σ_{j} − τ_{n}.

As U ≥ 0, V ≥ 0 this implies that

− τ_{n−j+1} ≤ ω_{j} ≤ σ_{j},  (A.6)

so

|ω_{j}| ≤ max{ σ_{j}, τ_{n−j+1} } ≤ σ_{j} + τ_{n−j+1}.  (A.7)

Hence

∑_{j=1}^{n} |ω_{j}| ≤ ∑_{j=1}^{n} σ_{j} + ∑_{j=1}^{n} τ_{n−j+1} = κ,  (A.8)

which establishes (A.3).

Suppose now that (A.3) is an equality. Then (A.8) holds with equality, i.e. (A.7) holds with equality for j = 1,…, n. This implies that for each j = 1,…, n at least one of σ_{j} and τ_{n−j+1} is zero, establishing (A.4).

If τ_{n} > 0 equation (A.4) and the ordering of the eigenvalues imply that U = 0. Similarly if σ_{n} > 0 then V = 0. In both cases (A.5) is trivial. Consider now the case when σ_{n} = τ_{n} = 0. If σ_{j} > 0 then τ_{n−j+1} = 0 so (A.6) implies that

0 ≤ ω_{j} ≤ σ_{j}.

Similarly if τ_{n−j+1} > 0 then σ_{j} = 0 so

−τ_{n−j+1} ≤ ω_{j} ≤ 0.

If σ_{j} = τ_{n−j+1} = 0 then ω_{j} = 0. Thus if (A.3) holds with equality then

κ = ∑_{j=1}^{n} |ω_{j}| = ∑_{j:σ_{j}>0} ω_{j} + ∑_{j:τ_{n−j+1}>0} −ω_{j}
≤ ∑_{j:σ_{j}>0} σ_{j} + ∑_{j:τ_{n−j+1}>0} τ_{n−j+1}
= κ.

The only way this can hold with equality is if (A.5) holds.

Conversely as U ≥ 0, V ≥ 0 and tr(U) + tr(V) = κ equations (A.4) and (A.5) directly give (A.3) with equality.

The following results are stated using the positive and negative parts of a symmetric matrix, although they could also be stated directly in terms of eigenvalues. Let W ∈ S_{n} have eigenvalues ω_{i} for i = 1,…, n and corresponding normalized eigenvectors v_{i}, so

W = ∑_{i=1}^{n} ω_{i}v_{i}v_{i}^{T} .

The positive and negative parts of the symmetric matrix W are then

W_{+} = ∑_{i=1}^{n}[ω_{i}]_{+}v_{i}v_{i}^{T} ,  (A.9)

W_{−} = ∑_{i=1}^{n}[ω_{i}]_{−}v_{i}v_{i}^{T} .  (A.10)

Then W_{+} ≥ 0, W_{−} ≥ 0, W = W_{+} − W_{−},

tr(W) = ∑_{i=1}^{n} ω_{i} = tr(W_{+}) − tr(W_{−})  (A.11)

and

∑_{i=1}^{n} |ω_{i}| = tr(W_{+}) + tr(W_{−}).  (A.12)

Now consider the set

Ξ_{n,κ} = { W ∈ S_{n} : −I ≤ W ≤ I, tr(W_{+}) + tr(W_{−}) = κ }.  (A.13)

Note that from equations (A.1) and (A.12)

Ξ_{n,κ} = { W ∈ S_{n} : W = Xdiag(w)X^{T} , X ∈ O_{n,n}, w ∈ ξ_{n,κ} }.

For any W ∈ Ξ_{n,κ}, setting U = W_{+}, V = W_{−} shows that W ∈ Ψ_{n,κ} and so Ξ_{n,κ} ⊆ Ψ_{n,κ}. The same example given earlier to show that ξ_{n,κ} does not equal ψ_{n,κ} also shows that Ξ_{n,κ} does not equal Ψ_{n,κ}. Instead, the following holds.

Corollary A.4

Ψ_{n,κ} = { W ∈ S_{n} : −I ≤ W ≤ I, tr(W_{+}) + tr(W_{−}) ≤ κ }.  (A.14)

Proof: Let W ∈ Ψ_{n,κ}. Since W = U − V with 0 ≤ U ≤ I, 0 ≤ V ≤ I, tr(U) + tr(V) = 1, equations (A.6) and (A.8) show that Ψ_{n,κ} is contained in the set on the right-hand side. To establish the reverse inclusion note that any W in the set on the right side has eigenvalues w = [ω_{1},…, ω_{n}]^{T} satisfying the conditions on the right side of (A.2). Therefore, from Lemma A.1, there exist u, v such that w = u − v ∈ ψ_{n,κ}. Taking U = Xdiag(u)X^{T} and V = Xdiag(v)X^{T} shows that W = U − V ∈ Ψ_{n,κ}.

Remark: The lack of convexity of the sets ξ_{n,κ} and Ξ_{n,κ} limits their use. Hence the preference for exploiting ψ_{n,κ} and Ψ_{n,κ}, which are convex since the restricting equations are linear, involving sums rather than sums of absolute values.

Characterization of the extreme points of Ψ_{n,κ} is now possible.

Lemma A.5 The set

{ Y Y^{T} − ZZ^{T} : Y^{T} Z = 0, Y^{T} Y = I_{κ_{1}}, Z^{T} Z = I_{κ_{2}}, and κ_{1} + κ_{2} = κ }.

is the set of extreme points of Ψ_{n,κ}.

Proof: Combining Lemma A.1 and Corollary A.4 gives

Ψ_{n,κ} = { W ∈ S_{n} : W = Xdiag(w)X^{T} , X ∈ O_{n,n}, w ∈ ψ_{n,κ} }.

The extreme points of Ψ_{n,κ} therefore have the form Xdiag(w)X^{T} where w is an extreme point of ψ_{n,κ}. Corollary A.2 then gives the desired result.

An obvious generalization of Fan’s theorem (which we have nonetheless not encountered in the literature) now follows as a corollary:

Theorem A.6

g_{κ}(A) = max {tr(Y^{T} AY) − tr(Z^{T} AZ) :
Y^{T} Z = 0, Y^{T} Y = I_{κ_{1}}, Z^{T} Z = I_{κ_{2}}, and κ_{1} + κ_{2} = κ }.

Lemma A.5 also leads immediately to another characterization of the elements achieving the maximum in (4.21), namely Theorem A.7

argmax {⟨ A, W ⟩ : W ∈ Ψ_{n,κ}} = conv { Y Y^{T} − ZZ^{T} : Y^{T} Z = 0
Y^{T} Y = I_{κ_{1}}, Z^{T} Z = I_{κ_{2}},
κ_{1} + κ_{2} = κ and
Y^{T} AY − Z^{T} AZ = g_{κ}(A) } (A.15)

From the ordering (4.8) of the eigenvalues of A the requirement Y^{T} AY − Z^{T} AZ = g_{κ}(A) means that the columns of Y must include r_{1} orthonormal eigenvectors for all the eigenvalues λ_{1},…, λ_{r_{1}} and the columns of Z must include r_{2} orthonormal eigenvectors for all the eigenvalues λ_{n−r_{2}+1},…, λ_{n}, so κ_{1} ≥ r_{1} and κ_{2} ≥ r_{2}. The remaining columns of Y and Z may be any orthonormal sets of eigenvectors corresponding to λ_{r_{1}+1} = … = λ_{r_{1}+t_{1}} and λ_{n−r_{2}−t_{2}+1} = … = λ_{n−r_{2}} respectively.

This leads to the following characterization of the subdifferential of g_{κ}(A).

Corollary A.8

∂g_{κ}(A) = conv { Y Y^{T} − ZZ^{T} :

the columns of Y form an o.n. set of κ_{1} eigenvectors for λ_{1},…, λ_{κ_{1}} the columns of Z form an o.n. set of κ_{2} eigenvectors for λ_{n−κ_{2}+1},…, λ_{n}

where r_{1} ≤ κ_{1} ≤ r_{1} + t_{1}, r_{2} ≤ κ_{2} ≤ r_{2} + t_{2}, and κ_{1} + κ_{2} = κ }

The presence of the convex hull operation means that this form is not as computationally convenient as that given in Corollary 4.6, nor does it display the structure of the subdifferential revealed there.

REFERENCES

1. F. Alizadeh (1991), Private communication.

2. V. I. Arnold (1971), “On matrices depending on parameters”, Russian Mathematical Surveys 26,2, pp. 29-43.

3. R. Bellman (1970), Introduction to Matrix Analysis, McGraw-Hill, New York, 2nd edition.

4. R. Bellman and K. Fan (1963), “On systems of linear inequalities in matrix variables”, in: V. L. Klee ed., Convexity, American Mathematical Society, Providence, R.I., pp. 1-11.

5. F. Clarke (1983), Optimization and Nonsmooth Analysis, John Wiley, New York. Reprinted by SIAM, Philadelphia, 1990.

6. B. D. Craven and B. Mond (1981), “Linear programming with matrix variables”, Linear Algebra and its Applications 38, pp. 73-80.

7. J. E. Cullum, W. E. Donath and P. Wolfe (1975), “The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices”, Mathematical Programming Study 3, pp. 35-55.

8. K. Fan (1949), “On a theorem of Weyl concerning the eigenvalues of linear transformations”, Proceedings of the National Academy of the Sciences of U.S.A 35, pp. 652-655.

9. P. A. Fillmore and J. P. Williams (1971), “Some convexity theorems for matrices”, Glasgow Mathematical Journal 12, pp. 110-117.

10. R. Fletcher (1985), “Semi-definite matrix constraints in optimization”, SIAM Journal on Control and Optimization 23, pp. 493-513.

11. S. Friedland (1981), “Convex spectral functions”, Linear and Multilinear Algebra 9, pp. 299-316.

12. S. Friedland, J. Nocedal and M. L. Overton (1987), “The formulation and analysis of numerical methods for inverse eigenvalue problems”, SIAM Journal on Numerical Analysis 24, pp. 634-667.

13. G. H. Golub and C. van Loan (1983), Matrix Computations, John Hopkins University Press, Baltimore.

14. R. A. Horn and C. Johnson (1985), Matrix Analysis, Cambridge University Press, New York.

15. T. Kato (1982), A Short Introduction to Perturbation Theory for Linear Operators, Springer-Verlag, New York.

16. M. L. Overton (1988), “On minimizing the maximum eigenvalue of a symmetric matrix”, SIAM Journal on Matrix Analysis and Application 9, pp. 256-268.

17. M. L. Overton (1990), “Large-scale optimization of eigenvalues”, NYU Computer Science Dept Report 505. To appear in SIAM Journal on Optimization.

18. M. L. Overton and R. S. Womersley (1988), “On minimizing the spectral radius of a nonsymmetric matrix function: Optimality conditions and duality theory”, SIAM Journal on Matrix Analysis and Applications 9, pp. 473-498.

19. M. L. Overton and R. S. Womersley (to appear), “Second derivatives for optimizing eigenvalues of symmetric matrices”. in preparation.

20. L. Qi and R. S. Womersley (to appear) “On extreme singular values”, in preparation.

21. F. Rendl and H. Wolkowicz (1990), “A projection technique for partitioning the nodes of a graph”, Department of Combinatorics and Optimization Report 90-20, University of Waterloo.

22. R. T. Rockafellar (1970), Convex Analysis, Princeton University Press, Princeton, NJ.

23. A. H. Sameh and J. A. Wisniewski (1982), “A trace minimization algorithm for the generalized eigenvalue problem”, SIAM Journal on Numerical Analysis 19, pp. 1243-1259.

24. A. Shapiro (1985), “Extremal problems on the set of nonnegative definite matrices”, Linear Algebra and its Applications 67 pp. 7-18.

25. A. Shapiro and J. D. Botha (1988), “Dual algorithms for orthogonal procrustes rotations”, SIAM Journal on Matrix Analysis 9, pp. 378-383.

26. G. A. Watson (1990), Private communication.

27. H. Wielandt (1955), “An extremum property of sums of eigenvalues”, Proceedings of the American Mathematical Society 6, pp. 106-110.