Hector Ramírez

Alberto Seeger

David Sossa

Keywords: Mathematics Subject Classification. 15A18, 15A99, 17C99, 49J53 Euclidean Jordan algebra, ordered Jordan frame, variational problem, operator commutation, spectral sets and spectral functions Mathematical subject classification: 15A18, 65F20, 65H10 Nonlinear complementarity problem, Loewner ordering, cone-constrained eigenvalue problem, semismooth Newton method Mathematics Subject Classification: 15A18, 15A48, 52A40, 90C26, 90C33 Maximal angle, critical angle, principal angle, convex cone. Mathematics Subject Classification. 17C27, 90C05 Key words. Euclidean Jordan algebra, symmetric cone linear programming, central path

Cette thèse concerne quatre thèmes apparemment différents, mais en fait étroitement liés: des problèmes variationnels sur les algèbres de Jordan euclidiennes, des problèmes de complémentarité sur l'espace des matrices symétriques, l'analyse angulaire entre deux cônes convexes fermés et analyse du chemin central en programmation conique symétrique.

Dans la première partie de ce travail, le concept de "commutation au sens opérationnel" dans les algèbres de Jordan euclidiennes est étudié en fournissant un principe de commutation pour les problèmes variationnels avec des données spectrales.

Dans la deuxième partie, nous abordons l'analyse et la résolution numérique d'une large classe de problèmes de complémentarité sur l'espace des matrices symétriques. Les conditions de complémentarité sont exprimées en termes de l'ordre de Loewner ou, plus généralement, en termes d'un cône du type Loewnerien.

La troisième partie de ce travail est une tentative de construction d'une théorie générale des angles critiques pour une paire de cônes convexes fermés. L'analyse angulaire pour une paire de cônes spécialement structurés est également considérée. Par-exemple, nous travaillons avec des sous-espaces linéaires, des cônes polyédriques, des cônes de révolution, des cônes "topheavy" et des cônes de matrices.

La dernière partie de ce travail étudie la convergence et le comportement asymptotique du chemin central en programmation conique symétrique. Ceci est fait en utilisant des techniques propres aux algèbres de Jordan.

Resumen

En esta tesis doctoral se abordan cuatro tópicos diferentes pero mutuamente relacionados: Problemas variacionales sobre álgebras de Jordan Euclideanos, problemas de complementariedad sobre espacios de matrices simétricas, análisis angular entre dos conos convexos y cerrados, y el camino central en programación cónica simétrica.

La primera parte de este trabajo corresponde al estudio del concepto de "operator commutation" en álgebras de Jordan Euclideanos por medio del establecimiento de un principio de conmutación para problemas variacionales los cuales poseen datos espectrales.

El principal enfoque de la segunda parte es el análisis y resolución numérica de una amplia clase de problemas de complementariedad formuladas en espacios de matrices simétricas. Las condiciones de complementariedad son expresadas en términos de la ordenación de Loewner o, mas general, con respecto a un par dual de conos Loewnerianos.

En la tercera parte presentamos una construcción de la teoría general de ángulos críticos para pares de conos convexos y cerrados. El análisis angular de pares de conos con estructuras especiales es también abordada. Por ejemplo, en nuestro estudio incluimos: subespacios lineales, conos poliedrales, conos de revolución, conos topheavy y conos de matrices.

La última parte de este trabajo está dedicada al estudio de la convergencia del camino central y del comportamiento de su punto límite en programación cónica simétrica. Esto es hecho por medio del uso de herramientas de álgebras de Jordan. vii

❆ ♠✐s ♣❛❞r❡s (♦•❛ ② ❱✐❝t♦r✐❛♥♦✱ ❛ ♠✐ ❡s♣♦s❛ ▲✐③ ❋❛❜✐♦•❛ ② ❛ ♠✐ ❤✐•❛ ❋•♦r ❉❛•✐③✳ ❈♦♥ ♠✉❝❤♦ ❆♠♦r✳

Introduction

This doctoral thesis deals with variational problems over Euclidean Jordan algebras and variational problems involving conic constrains. It is composed by five chapters which are based on the papers [12,15] and the manuscripts [16,17,13], respectively. In order to facilitate the reading of this work, each chapter is presented in a self-contained way.

In the first chapter we give some contributions to the theory of Euclidean Jordan algebras by establishing a commutation principle for variational problems formulated in this context.

The second chapter deals with the analysis and numerical resolution of complementarity problems with respect to Loewnerian cones.

The concept of critical angles between two closed convex cones is developed in the third and fourth chapter. The general theory is presented in the third chapter and some particular structures are studied in the fourth chapter.

In the last chapter we present some results concerning to the convergence and the limiting behavior of the central path in symmetric cone linear programming.

A brief description of the main problems that we have considered and the main results that we have obtained is presented in the next paragraphs.

Commutation principle for variational problems on Euclidean Jordan algebras

Q ⊆ R r such that Ω = {x ∈ V : λ(x) ∈ Q},
where λ(x) ∈ R r is the vector of the eigenvalues of x arranged in nondecreasing order. A function Φ : V → R is called spectral function if there exist a permutation invariant function g : R r → R such that Φ(x) = g(λ(x)).

The main contribution presented in this chapter is the establishment of a commutation principle for variational problems involving spectral data. It reads as follows:

Theorem. Let (V, •, •, • ) be a Euclidean Jordan algebra and let a, b ∈ V. Suppose that Ω ⊆ V is a spectral set and that Φ : V → R is a spectral function. Under these assumptions, if b is a local minimum or a local maximum of x ∈ Ω → F (x) = a, x + Φ(x), then a and b operator commute.

This result was inspired by the commutation principle established by Iusem and Seeger [7,Lemma 4] for the particular case of the space of symmetric matrices.

Complementarity problems with respect to Loewnerian cones

This chapter is devoted to the analysis and numerical resolution of a class of nonlinear complementarity problems formulated in S n , the space of symmetric matrices of order n. The complementarity problem studied is of the form

Φ(X, Y, λ) = 0 K ∋ X ⊥ Y ∈ K * , (1)
where λ stands for an unknown parameter vector in some Euclidean space, Φ is a continuously differentiable function and K is a Loewnerian cone, i.e., it is the image of the positive semidefinite cone S n + under some linear endomorphism on S n .

We show that, under some assumptions over the dimension of the involved spaces, the problem (1) can be equivalently formulated as a square system of nonlinear equations by using complementarity functions for the cone S n + . In this work we make use of the Fischer-Burmeister complementarity function and the Minimum complementarity function. Hence, for solving (1) we apply the Semismooth Newton Method to the equivalent formulation.

The performance of these methods is studied by considering the particular case when K = S n + . The problem tested in our numerical experiments is that of finding a Loewnereigenvalue of a linear map generated by means of a random mechanism.

As a theoretical result of this chapter we study some properties of Loewnerian cones and we provide a list of examples of Loewnerian cones and counter-examples.

We start by considering a pair of revolution cones in any Euclidean space X. In this case, we provide explicit formulas for computing each critical angle.

A topheavy cone in R n+1 is a closed convex cone of the form epif := {(ξ, t) ∈ R n+1 : f (ξ) ≤ t}, where f is a norm on R n . The class of topheavy cones is quite large and includes in particular the ℓ p -cones and the ellipsoidal cones. We show that under the assumption of "lower correlated norms" the maximal angle between two topheavy cones can be computed by considering the maximal angle of each cone (cf. [14]). This result is illustrated by computing the maximal angle between two ℓ p -cones and between two ellipsoidal cones.

We have also obtained explicitly the maximal angle for the following situations: an ellipsoidal cone versus a nonnegative orthant and an ellipsoidal cone versus a ray.

Concerning the critical angles between two cones of symmetric matrices, we show that the set of critical angles between two "orthogonally invariant" cones is in correspondence with the set of critical angles between the respective permutation invariant cones.

At the end of this chapter we give a discussion about a difficult question arising in numerical linear algebra: how large can be the angle between a positive semidefinite symmetric matrix and a symmetric matrix that is nonnegative entrywise? We give some partial answers. For instance, we show that for dimension three the answer is (3/4)π and for dimensions greater or equal than five the maximal angle must be greater than (3/4)π. By using numerical methods we have obtained lower bounds for this maximal angle for dimensions ranging from 4 to 30. Recently, Goldberg and Shaker-Monderer [4] have proved that this maximal angle tends to π when the dimension goes to ∞. It remains an open question to compute the exact value of this maximal angle for any dimension.

On the central path in symmetric cone linear programming

A symmetric cone linear program is an optimization problem of the form

(P ) min x∈V { c, x : Ax = b, x ∈ K}
where (V, •, •, • ) is a Euclidean Jordan algebra, K is the cone of square elements on V (symmetric cone), c ∈ V, b ∈ R m and A : V → R m is a linear map. (P ) is called the primal problem an its dual is denoted by (D).

The (primal-dual) central path is defined as the set {(x(µ), y(µ), s(µ)) : µ > 0} derived from the optimality conditions of the penalized problem associated with (P ), where the logarithm barrier function is used.

In this chapter we show that the central path converges to a point in the optimal sets of problems (P )-(D). By using the Peirce decomposition of V with respect to particular idempotents, we provide a characterization of the primal and dual optimal sets. We also conclude that the limit point is a maximally complementary solution and it lies in the relative interior of the primal and dual optimal sets. A full characterization of the limit point is still an open problem. We expect to study this topic in a future work.

The results presented in this chapter are inspired by the results obtained for the central path in the particular context of semidefinite programming (cf. [5,6,9]).

Chapter 1

Commutation principle for variational problems on Euclidean Jordan algebras1

Introduction

Let the space S n of real symmetric matrices of order n be equipped with the Frobenius or trace inner product X, Y = tr(XY ). The notation λ(X) refers to the (column) vector of eigenvalues λ 1 (X) ≤ . . . ≤ λ n (X)

of X ∈ S n arranged in nondecreasing order. Recall that a spectral set in S n is a set of the form

Ω = λ -1 (Q) := {X ∈ S n : λ(X) ∈ Q},
where Q is a permutation invariant set in R n . A spectral function on S n is a real-valued function Φ : S n → R admitting the representation Φ(X) = g(λ(X)),

where g : R n → R is a real-valued permutation invariant function. Spectrality is a property that some authors refer to as orthogonal invariance. General information on the theory of spectral sets and spectral functions can be found in [3,11,14] and the references therein.

Iusem and Seeger [9, Lemma 4] established recently the following commutativity result for variational problems involving spectral data. By a local extremum of a function one understands a local minimum or a local maximum.

Lemma 1.1. Let A, B ∈ S n . Suppose that Ω ⊆ S n is a spectral set and that Φ : S n → R is a spectral function. Under these assumptions, if B is a local extremum of X ∈ Ω → F (X) = A, X + Φ(X), then A and B commute, i.e., AB = BA.

It is worthwhile to keep in mind that if two symmetric matrices commute, then it is possible to diagonalize them by means of a common orthogonal matrix. The possibility of simultaneous diagonalization opens the way to significant simplifications in the proof of various linear algebra results. The commutation principle stated in Lemma 1.1 has applications in various fields, see for instance

            
Fenchel conjugate and subdifferential of a convex spectral function (cf. [11]), distance to a spectral set (cf. [3,Proposition 2.3]), inradius and incenter of a spectral convex cone (cf. [7,Theorem 3.3]), distance between a pair of spectral convex cones (cf. [10,Proposition 6.6]), antipodal pairs in spectral convex cones (cf. [9,Theorem 4]).

It turns out that Lemma 1.1 is a particular instance of a more general and deep commutation principle for variational problems on Euclidean Jordan algebras. The main result of this paper reads as follows:

Theorem 1.2. Let (V, •, •, • ) be a Euclidean Jordan algebra and let a, b ∈ V. Suppose that Ω ⊆ V is a spectral set and that Φ : V → R is a spectral function. Under these assumptions, if b is a local extremum of

x ∈ Ω → F (x) = a, x + Φ(x), (1.1)
then a and b operator commute, i.e.,

a • (b • z) = b • (a • z) for all z ∈ V. (1.2)
For simplicity in the exposition we consider Φ as a spectral function on the whole space V, but one could restrict Φ to the spectral subset Ω. Section 1.2 reviews some basic material on Euclidean Jordan algebras and prepares the ground for proving Theorem 1.2. The proof itself is given in Section 1.3. Some applications are mentioned in Section 1.4.

Preliminary material on Euclidean Jordan algebras

Throughout this work one assumes that (V, •, •, • ) is a Euclidean Jordan algebra (EJA) with unit element e ∈ V. This means that V is a finite dimensional real vector space equipped with an inner product •, • and a bilinear function • : V × V → V satisfying the axioms:

         x • y = y • x for all x, y ∈ V, x • (x 2 • y) = x 2 • (x • y) for all x, y ∈ V, x • y, z = y, x • z for all x, y, z ∈ V, e • x = x for all x ∈ V.
The unit element e is clearly unique. Here and in the sequel one uses the notation

x 2 = x • x.
Higher order powers are defined recursively by

x k+1 = x • x k . The rank of V is declared to be r = max{deg(x) : x ∈ V},
where deg(x) is the smallest positive integer k such that {e, x, x 2 , . . . , x k } is linearly dependent.

The Lyapunov operator associated to a given x ∈ V is the linear map L x : V → V given by L x y = x • y. The operator commutation property (1.2) amounts to saying that the bracket

[L a , L b ] := L a L b -L b L a is equal to the zero map on V. An element c ∈ V is an idempotent if c 2 = c. An idempotent c is primitive if it is nonzero
and cannot be written as a sum of two nonzero idempotents. A Jordan frame is a collection {c 1 , . . . , c r } of primitive idempotents satisfying r i=1 c i = e and c i • c j = 0 when i = j.

We recall below a spectral decomposition theorem taken from [4,Theorem III.1.2].

Theorem 1.3. Let (V, •, •, • ) be an EJA with rank r. Then, for every x ∈ V, there exists a Jordan frame {c 1 , . . . , c r } and real numbers λ 1 , . . . , λ r such that

x = λ 1 c 1 + . . . + λ r c r .
The λ i 's are uniquely determined by x.

We write λ i (x) to underline the dependence with respect to x. Renumbering the c i 's if necessary, one may suppose that the λ i (x)'s are arranged in nondecreasing order, i.e.,

λ 1 (x) ≤ . . . ≤ λ r (x).
By analogy with the case of symmetric matrices, one refers to the (column) vector λ(x) ∈ R r as the vector of "eigenvalues" of x ∈ V. A spectral set in V is then a set of the form

Ω = λ -1 (Q) := {x ∈ V : λ(x) ∈ Q} (1.3) with Q ⊆ R r permutation invariant. A spectral function on V is a real-valued function Φ : V → R admitting the representation Φ(x) = g(λ(x))
with g : R r → R permutation invariant. The formulation of Theorem 1.2 is now perfectly clear.

Remark 1.4. Note that Lemma 1.1 can be derived from Theorem 1.2 by working with the particular EJA

         V = S n , X, Y = tr(XY ), X • Y = 1 2 (XY + Y X
), e = I n (identity matrix of order n).

(1.4) One can easily check that the operator commutation property

A • (B • Z) = B • (A • Z) for all Z ∈ S n
is equivalent to the usual commutation condition AB = BA.

The following result, borrowed from [1,Theorem 27], shows the importance of the concept of operator commutation. We mention in passing that this concept admits also other equivalent characterizations, see for instance in [12,Theorem 1].

Theorem 1.5. Let (V, •, •, • ) be an EJA with rank r. Then a ∈ V and b ∈ V operator commute if and only if a and b admit a common Jordan frame, i.e., there exist a Jordan frame {c 1 , . . . , c r } and real numbers λ 1 , . . . , λ r and µ 1 , . . . , µ r such that

a = λ 1 c 1 + . . . + λ r c r b = µ 1 c 1 + . . . + µ r c r .

The tangent space to the set of ordered Jordan frames

The proof of Theorem 1.2 relies on the analysis of an optimization problem of the form minimize f (c)

c ∈ O V , (1.5)
where f : V r → R is a continuously differentiable function and

O V := {c = (c 1 , . . . , c r ) ∈ V r : {c 1 , . . . , c r } is a Jordan frame }. (1.6)
Each element of (1.6) is called an ordered Jordan frame. A local solution c to the problem (1.5) satisfies the first-order optimality condition

f ′ (c)h ≥ 0 for all h ∈ T c[O V ], (1.7)
where

f ′ (c) : V r → R is the differential map of f at c and T c[O V ] is the Bouligand tangent set to O V at c (cf. [2, Definition 4.1.1]).
The next lemma shows that T c[O V ] is a linear subspace and provides an explicit formula for computing this set. It also characterizes the orthogonal complement

(T c[O V ]) ⊥ := q ∈ V r : r i=1 q i , h i = 0 for all h ∈ T c[O V ] .
For notational convenience we introduce the index sets

N r := {1, . . . , r} M r := {(i, j) ∈ N r × N r : i < j}. Lemma 1.6. Let (V, •, •, • ) be an EJA with rank r and let c ∈ O V . Then the following hold (a) h = (h 1 , . . . , h r ) ∈ V r belongs to T c[O V ] if and only if 2c i • h i -h i = 0 for all i ∈ N r (1.8) ci • h j + cj • h i = 0 for all (i, j) ∈ M r .
(1.9)

In particular, T c[O V ] is a linear subspace.

(b) q = (q 1 , . . . , q r ) ∈ V r belongs to (T c[O V ]) ⊥ if and only if there are vectors

{α i : i ∈ N r } ⊆ V and {β i,j : (i, j) ∈ M r } ⊆ V (1.10)
such that

q i = 2α i • ci -α i + i-1 j=1 β j,i • cj + r j=i+1 β i,j • cj for all i ∈ N r . (1.11)
Proof. Part (a). Let R V be the set of all c ∈ V r satisfying the nonlinear system

c 2 i -c i = 0 for all i ∈ N r c i • c j = 0 for all (i, j) ∈ M r .
(1.12)

Since O V ⊆ R V , it is clear that T c[O V ] ⊆ T c[R V ].
Let B c be the set of all h ∈ V r satisfying the linear system (1.8)-(1.9). Observe that (1.8)-(1.9) is obtained by linearizing (1.12) around the reference point c. This observation shows that

T c[R V ] ⊆ B c.
For completing the proof of (a) it suffices to check that

B c ⊆ T c[O V ].
Let h ∈ B c. To start with, we check that

r i=1 h i = 0. (1.13)
One has

σ := r i=1 r j=1 {c i • h j + cj • h i } = r i=1 ci • r j=1 h j + r j=1 cj • r i=1 h i = 2 r i=1 h i .
On the other hand,

σ = r i=1 2 ci • h i + 2 (i,j)∈Mr {c i • h j + cj • h i } = r i=1 h i .
This confirms the equality (1.13). Next, we construct a continuously differentiable function

t ∈ R → γ(t) = (γ 1 (t), . . . , γ r (t)) such that γ(t) ∈ O V for all t ∈ R (1.14) γ(0) = c (1.15) γ ′ (0) = h. (1.16)
The existence of such function γ implies that h ∈ T c[O V ]. We suggest to take as the i-th component of γ a function of the form

γ i (t) = exp(tD) At ci ,
where D : V → V is some linear map and {A t } t∈R is the associated semigroup, i.e.,

A t := ∞ p=0 t p p! D p .
The condition (1.15) clearly holds and γ ′ (0) = (Dc 1 , . . . , Dc r ). Hence, D is to be constructed so that Dc i = h i for all i ∈ N r .

(1.17)

Inspired in the technique used in [8, Section 3], we take

D := 2 r k=1 [L h k , L ck ]
is a suitable choice. A matter of computation shows that

Dc i = 2 r k=1 h k • (c k • ci ) -2 r k=1 ck • (h k • ci ) = 2h i • (c i • ci ) -2c i • (h i • ci ) -2 k∈Nr\{i} ck • (h k • ci ).
Since ci is idempotent and (1.8) holds, one gets

Dc i = 1 2 h i -2 k∈Nr\{i} ck • (h k • ci ) = 1 2 h i -2 k∈Nr\{i} ci • (h k • ck ),
the last equality being due to the fact that ck and ci operator commute (cf. [5,Proposition 6]). By using (1.8) and simplifying, one obtains

Dc i = 1 2 h i - k∈Nr\{i} ci • h k = 1 2 h i -ci •   k∈Nr\{i} h k   .
By using (1.13) and (1.8), one gets finally

Dc i = 1 2 h i -ci • (-h i ) = h i .
This proves (1.17) and the condition (1.16). We now take care of (1.14), that is to say, we pick an arbitrary t ∈ R and check that {γ 1 (t), . . . , γ r (t)} is a Jordan frame. Thanks to [4, Proposition II.4.1] one knows that D is a derivation on V, i.e.,

D(x • y) = (Dx) • y + x • Dy for all x, y ∈ V.
Such a property implies in turn that A t : V → V satisfies the identity

(A t x) • (A t y) = A t (x • y) for all x, y ∈ V.
In particular, one has

γ i (t) • γ j (t) = (A t ci ) • (A t cj ) = A t (c i • cj ) = 0
whenever i and j are different. Similarly,

γ i (t) • γ i (t) = (A t ci ) • (A t ci ) = A t (c i • ci ) = A t ci = γ i (t),
that is to say, γ i (t) is idempotent. We claim that γ i (t) is also primitive. Indeed, if γ i (t) is not primitive, then one can write

γ i (t) = A t ci = āi + bi ,
where a i and b i are nonzero idempotents. Hence,

ci = A -1 t āi + A -1 t bi .
Since -D is a derivation and {A -1 t } t∈R is its associated semigroup, it follows that A -1 t āi and A -1 t bi are nonzero idempotents, contradicting the fact that ci is primitive. Finally, we observe that

r i=1 γ i (t) = r i=1 A t ci = A t r i=1 ci = A t e.
Keeping in mind that D is a derivation, one sees that

De = D(e • e) = (De) • e + e • (De) = 2 De.
Thus De = 0 and A t e = e. This completes the proof of (a).

Part (b). The linear system (1.8)-(1.9) is formed by

s r := r + r(r -1) 2
equations. So, the linear subspace B c corresponds to the kernel of a linear map M : V r → V sr whose definition is clear. Hence, the orthogonal complement of B c is equal to the range of the adjoint map M * : V sr → V r . The explicit computation of this adjoint leads to the announced formula (1.11). The details are omitted.

Proof of the general commutation principle

This section takes care of the proof of Theorem

E : V → R is continuously differentiable. Suppose that Ω ⊆ V is a spectral set and that Φ : V → R is a spectral function. Under these assumptions, if b is a local extremum of x ∈ Ω → F (x) = E(x) + Φ(x), (1.18)
then b and ∇E(b) operator commute.

Proof of the general commutation principle

Proof. Suppose that b is a local minimum of (1.18), the case of a local maximum can be treated in a similar way. One has b ∈ Ω and

E(b) + Φ(b) ≤ E(x) + Φ(x) for all x ∈ Ω ∩ N b ,
where N b is some neighborhood of b. Let c ∈ O V be an ordered Jordan frame such that b = r i=1 λi ci with λi = λ i (b). Consider the linear function Γ : V r → V defined by

Γ(c) = r i=1 λi c i . Let x := Γ(c) with c ∈ V r . If c is taken in a small neighborhood N c of c, then x ∈ N b by the continuity of Γ. On the other hand, if c belongs to O V , then λ(x) = λ(b) and, a posteriori, x ∈ Ω. Hence, E r i=1 λi ci + Φ r i=1 λi ci ≤ E r i=1 λi c i + Φ r i=1 λi c i for all c ∈ O V ∩ N c.
The spectrality of Φ leads to the simpler inequality

E r i=1 λi ci ≤ E r i=1 λi c i for all c ∈ O V ∩ N c.
We have shown in this way that c is a local minimum on O V of the function

c ∈ V r → f (c) = E r i=1 λi c i .
Note that f is differentiable at c because E is differentiable at b. The optimality condition (1.7) takes the particular form ( λ1 a, . . . , λr a)

∇f (c) ∈ (T c[O V ]) ⊥ ,
where a := ∇E(b). In view of the characterization (1.11) of the subspace

(T c[O V ]) ⊥ , one gets λi a = 2α i • ci -α i + i-1 j=1 β j,i • cj + r j=i+1 β i,j • cj for all i ∈ N r (1.19)
for suitable vectors α i and β i,j as in (1.10). With this information at hand, we are now ready to show that a and b operator commute. One has

[L a , L b ] = L a r i=1 λi L ci - r i=1 λi L ci L a = r i=1 Lλ i a L ci - r i=1 L ci Lλ i a = r i=1 [Lλ i a , L ci ]. But (1.19) implies that Lλ i a = 2L α i • ci -L α i + L ν i with ν i := i-1 j=1 β j,i • cj + r j=i+1 β i,j • cj . Hence [L a , L b ] = r i=1 {2[L α i • ci , L ci ] -[L α i , L ci ]} ∆ 1 + r i=1 [L ν i , L ci ] ∆ 2
.

We claim that ∆ 1 is the zero map on V. Indeed,

2[L α i • ci , L ci ] = [L α i , L ci ] for all i ∈ N r ,
as one can see from the general identity (cf. [4, Proposition II.1.1])

2[L u•z , L z ] = [L u , L z 2 ] for all u, z ∈ V
and the fact that ci is idempotent. Also ∆ 2 is the zero map on V. To see this, we write

∆ 2 = r i=1 i-1 j=1 L β j,i • cj + r j=i+1 L β i,j • cj , L ci = r i=1 i-1 j=1 L β j,i • cj , L ci + r j=i+1 L β i,j • cj , L ci = (i,j)∈Mr L β i,j • ci , L cj + L β i,j • cj , L ci and observe that L β i,j • ci , L cj + L β i,j • cj , L ci = 0.
The above equality follows from the general identity (cf. [4, Proposition II.1.1])

[L u•y , L z ] + [L u•z , L y ] = [L u , L z•y ] for all u, y, z ∈ V
and the fact that ci • cj = 0 for all (i, j) ∈ M r . This shows that a and b operator commute, finishing the proof.

Applications

Some simple but illuminating examples suffice to illustrate how the commutation principle works in practice.

Variational inequalities

The next proposition concerns a variational inequality of the form

G(x), u -x + Φ(u) -Φ(x) ≥ 0 for all u ∈ Ω x ∈ Ω, (1.20)
where G : V → V is an arbitrary function.

Proposition 1.9. Let (V, •, •, • ) be an EJA. Suppose that Ω ⊆ V is a spectral set and that Φ :

V → R
G(b), u + Φ(u) ≥ G(b), b + Φ(b) for all u ∈ Ω.
Hence, b is a global minimum of

u ∈ Ω → F (u) = G(b), u + Φ(u).
Theorem 1.2 leads to the announced conclusion.

Distance to a spectral set

Recall that the trace operator on a Euclidean Jordan algebra (V, •, •, • ) with rank r is the real-valued function

u ∈ V → Tr(u) = r i=1 λ i (u).
An EJA is said to be scalarizable if there exists a positive constant θ such that

x, y = θ Tr(x • y) for all x, y ∈ V.

(1.21)

Such constant is unique and called the scaling factor of the EJA. Of course, it is given by θ = e, e Tr(e) .

As a consequence of the scalarization property (1.21) one gets

x = √ θ λ(x) 2 for all x ∈ V, (1.22)
where • 2 is the usual Euclidean norm on R r . It is well known that:

• The EJA given by (1.4) is of rank r = n. It is scalarizable and has θ = 1 as scaling factor.

• The EJA given by

         V = R n-1 × R,
(ξ, t), (η, s) = ξ T η + ts, (ξ, t) • (η, s) = sξ + tη, ξ T η + ts , e = ((0, . . . , 0), 1) T is of rank r = 2. It is scalarizable and has θ = 1/2 as scaling factor.

Remark 1.10. If an EJA is simple in the sense that it does not contain any nontrivial ideal, then it is scalarizable, see [4,Proposition III.4.1].

The next proposition provides a formula for computing the distance

dist[a, Ω] := inf x∈Ω a -x (1.23) from a point a ∈ V to a spectral set Ω ⊆ V. Our result is a generalization of [3, Proposi- tion 2.3].
Proposition 1.11. Let (V, •, •, • ) be an EJA with rank r and scaling factor θ. Let Ω ⊆ V be a spectral set as in (1.3). Then for all a ∈ V one has

1 √ θ dist[a, Ω] = inf µ∈Q λ(a) -µ 2 . (1.24)
In particular, dist[ • , Ω] is a spectral function.

Proof. The topological closure of Q is permutation invariant and one has

cl(Ω) = λ -1 (cl(Q)).
Hence, cl(Ω) is a spectral set. Since a distance function is blind with respect to topological closure, there is no loss of generality in assuming that Q is already closed (in which case, also Ω is closed). Let b be a solution to (1.23). Then b is a global maximum of Clearly,

x ∈ Ω → F (x) = a, x - 1 2 x 2 . But (1.22) implies that -(1/2) • 2 is
dist[a, Ω] = a -b = √ θ λ(a) -μ 2 .
We claim that μ solves the minimization problem on the right-hand side of (1.24). Up to a permutation, the vector μ is equal to λ(b). Hence, μ ∈ Q. Suppose that there exists μ ∈ Q such that λ(a)μ 2 < λ(a)μ 2 . In such a case x = r i=1 μi c i belongs to Ω and a

-x = √ θ λ(a) -μ 2 < √ θ λ(a) -μ 2 = dist[a, Ω],
a clear contradiction.

Inradius of a spectral cone

Proposition 1.11 has in turn several applications. For instance, it can be used to derive a formula for computing the inradius

ρ(K) := sup x∈K x =1 dist[x, bd(K)] (1.25)
of a spectral proper cone K in V. By a proper cone one understands a closed convex cone that is pointed and has nonempty interior. The notation bd(K) refers to the boundary of K. The maximization problem (1.25) has a unique solution, which is called the incenter of K and it is denoted by inc(K). General information concerning the theory of inradiuses and incenters of proper cones can be found in [6,7].

The next corollary is an extension of [7,Theorem 3.3]. The symbol 1 r refers to the rdimensional vector of ones.

Corollary 1.12. Let (V, •, •, • ) be a scalarizable EJA with rank r. Let Q be a permutation invariant proper cone in R r . Then (a) The spectral set K = {x ∈ V : λ(x) ∈ Q} is a proper cone in V.

(b) K has the same inradius as Q, i.e.,

ρ(K) = sup µ∈Q µ 2 =1 dist[µ, bd(Q)].
(1.26)

(c) The incenter of K is given by

inc(K) = e e if 1 r ∈ Q -e e if 1 r / ∈ Q. (1.27)
Proof. The statement (a) is part of the folklore on spectral sets. Note that

bd(K) = {x ∈ V : λ(x) ∈ bd(Q)}
is a spectral set because bd(Q) is permutation invariant. By using Proposition 1.11 one gets

ρ(K) = sup x∈V, λ(x)∈Q √ θ λ(x) 2 =1 √ θ dist[λ(x), bd(Q)],
where θ is the scaling factor of the EJA. The change of variables µ = √ θ λ(x) and the positive homogeneity of the function dist[ • , bd(Q)] lead to (1.26). We now prove (c). Let x = inc(K), that is to say,

x ∈ K, x = 1, ρ(K) = dist[x, bd(K)]. Hence, λ(x) ∈ Q, √ θ λ(x) 2 = 1, ρ(Q) = √ θ dist[λ(x), bd(Q)].
We have proven in this way that

inc(Q) = √ θ λ(x).
(1.28)

The proper cone Q being permutation invariant, one knows (cf. [7,Proposition 2.19]) that

inc(Q) = 1 √ r 1 r if 1 r ∈ Q -1 √ r 1 r if 1 r / ∈ Q. (1.29)
There are two cases for consideration: if 1 r ∈ Q, then the combination of (1.28) and (1.29) yields

λ 1 (x) = . . . = λ r (x) = 1 √ rθ ,
and therefore x is a positive multiple of e. If 1 r / ∈ Q, then

λ 1 (x) = . . . = λ r (x) = - 1 √ rθ ,
and x is a negative multiple of e. This proves (1.27).

Example 1.13. For instance, the cone of squares

K V := {x 2 : x ∈ V} = {x ∈ V : λ(x) ∈ R r + }
of an scalarizable EJA fits into the framework of Corollary 1.12. One gets

ρ(K V ) = 1 √ r and inc(K V ) = e e .

Bibliography

Chapter 2

Complementarity problems with respect to Loewnerian cones1

Introduction

The main concern of this work is the analysis and numerical resolution of a class of nonlinear complementarity problems formulated in S n , the space of symmetric matrices of order n. As usual, S n is equipped with the trace inner product Y, X = tr(Y X) and the associated norm.

The first part of this work deals with a complementarity problem of the form

(SDCP) Φ(X, Y, λ) = 0 0 X ⊥ Y 0, (2.1)
where the nonnegativity constraints are expressed in terms of the Loewner ordering on S n . Following [START_REF] Nishimura | Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets[END_REF], we refer to the equilibrium model (2.1) as the Semi-Definite Complementarity Problem (SDCP). The symbol λ stands for an unknown parameter vector in a Euclidean space Λ and Φ is a continuously differentiable function from E := S n × S n × Λ to another Euclidean space F. The dimension of each bold marked zero vector 0 is understood from the context.

Although it is not strictly necessary, for simplicity in the exposition we assume that

dim(F) = dim(Λ) + dim(S n ). ( 2
  L(X) -λX -Y = 0 tr(X) -1 = 0 0 X ⊥ Y 0.
(2.

3)

The second equality in (2.3) is a normalization condition which ensures that X is a nonzero solution. In this example one has Λ = R and F = S n × R. Theorem 2.1 in [START_REF] Seeger | Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions[END_REF] ensures that the system (2.3) admits always a solution. The problem of finding Loewner-eigenvalues for some particular linear endomorphisms is addressed for instance in [START_REF] Zhou | On the finiteness of the cone spectrum of certain linear transformations on Euclidean Jordan algebras[END_REF].

Example 2.2. Consider an optimization problem of the form

minimize c(X) s.t. X 0, A(X) = b, (2.4)
where c : S n → R is a twice continuously differentiable convex function, A : S n → R m is a linear map, and b ∈ R m . A particular instance of (2.4) is the so-called nearest correlation matrix problem, see [6,17,19]. The KKT-optimality conditions for the minimization problem (2.4) are

     ∇c (X) -A T (λ) -Y = 0 A(X) -b = 0 0 X ⊥ Y 0,
where ∇c : S n → S n is the gradient map of c and A T is the adjoint map of A. In this example one has Λ = R m and F = S n × R m .

Remark 2.3. Other particular cases of (2.1) can be found in [7,13,[START_REF] Nishimura | Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets[END_REF]. Let Q ∈ S n and L ∈ End(S n ). The so-called semidefinite linear complementarity problem

L(X) + Q -Y = 0 0 X ⊥ Y 0
also fits into the model (2.1). Semidefinite LCPs have been analyzed by numerous authors, both from a theoretical and algorithmic point of view.

The second part of our work deals with a complementarity problem having the more general form

Φ(X, Y, λ) = 0 K ∋ X ⊥ Y ∈ K * . (2.5)
The nonnegativity constraints on X and Y are now expressed in terms a Loewnerian cone K and its positive dual cone K * . By definition, a Loewnerian cone is the image of the SDP cone S n + := {X ∈ S n : X 0} under some invertible linear endomorphism on S n . Loewnerian cones are not self-dual in general, but they share a number of properties of the SDP cone. For instance, a Loewnerian cone has a similar facial structure as the SDP cone.

Complementarity function approach for solving the SDCP

A natural strategy for solving (2.1) is to apply the Semismooth Newton Method (SNM) to the nonlinear system

Φ(X, Y, λ) = 0 κ(X, Y ) = 0, (2.6)
where κ : S n × S n → S n is a complementarity function for the SDP cone, i.e.,

κ(X, Y ) = 0 ⇔ 0 X ⊥ Y 0.
The function κ may not be differentiable. In order to apply the SNM one just needs to ensure that κ is globally Lipschitz and semismooth. This requirement is fulfilled if one chooses for instance the Fischer-Burmeister complementarity function

κ fb (X, Y ) := X + Y -(X 2 + Y 2 ) 1/2
or the minimum complementarity function

κ min (X, Y ) := X -Π S n + (X -Y ) .
The square root operation ( • ) 1/2 is understood in the usual matrix sense and Π S n + stands for the projection map onto S n + . The functions κ fb and κ min are known to be globally Lipschitz and strongly semismooth, see [START_REF] Sun | Semismooth matrix-valued functions[END_REF] and [START_REF] Sun | Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions[END_REF].

For notational convenience we write the nonlinear system (2.6) in the more compact form

Ψ(z) = 0, (2.7)
where Ψ : E → W is given by

z = (X, Y, λ) → Ψ(z) := (Φ(X, Y, λ), κ(X, Y )).
Thanks to the assumption (2.2), the space W := F × S n has the same dimension as E. In other words, the system (2.7) has the same number of equations and unknown variables. We solve the square system (2.7) with the following Semismooth Newton Method (SNM):

• Initialization. Choose an initial point z 0 and set t = 0.

• Iteration. One has a current point z t . Pick M t ∈ ∂Ψ(z t ), find ∆z such that

M t ∆z = -Ψ(z t ), (2.8)
and update z t+1 = z t + ∆z.

The symbol ∂Ψ(z) stands for the Clarke generalized Jacobian of Ψ at z (cf. [8]). Theoretical aspects concerning the rate of convergence of the SNM can be consulted in [START_REF] Qi | A nonsmooth version of Newton's method[END_REF].

Remark 2.4. We keep the SNM running until any of the following situations occur:

t = 1000 (lack of convergence), cond(M t ) ≥ 10 10 (ill-conditioning), Ψ(z t ) ≤ 10 -8
(a solution is found).

Here, cond(M ) refers to the condition number of a linear map M . All our numerical experiments are carried in Window 7 with a processor 3.40GHz Intel Xeon, Memory(RAM) 8.00 Gb. The codes were implemented with Matlab 7.12.

Numerical experiments

The numerical experiments reported in this section concern the problem of finding a Loewnereigenvalue of a given map L ∈ End(S n ). So, the problem at hand is to solve (2.7) with z = (X, Y, λ) and

Ψ(z) = (L(X) -λX -Y, tr(X) -1, κ(X, Y )).
(2.9)

The linearized system (2.8) takes here the particular form

L(∆X) -λ t ∆X -∆Y -(∆λ)X t = -[L(X t ) -λ t X t -Y t ]
(2.10)

tr(∆X) = -[tr(X t ) -1] (2.11) E t (∆X) + F t (∆Y ) = -κ(X t , Y t ) (2.12)
with (E t , F t ) ∈ ∂κ(X t , Y t ). A convenient way to initialize the SNM for finding a zero of the function (2.9) is to generate a random Gaussian matrix Ξ ∈ S n and set:

X 0 = [tr(Ξ)] -1 Ξ , λ 0 = X 0 -2 L(X 0 ), X 0 , Y 0 = L(X 0 ) -λ 0 X 0 .
That a random matrix Ξ ∈ S n is Gaussian means that the entries Ξ i,j (with i ≤ j) are random variables following a standard normal law.

Performance of κ fb

As a first choice, we let κ be the Fisher-Burmeister complementarity function. For the reader's convenience, we record below a useful lemma that can be found in [18].

Lemma 2.5. Let A, B ∈ S n be such that A 2 + B 2 is nonsingular. Then κ fb is continuously differentiable at (A, B) and the partial differentials (with respect to X and Y ) are given by

(D X κ fb )(A, B) = I S n -L -1 [A 2 +B 2 ] 1/2 • L A (2.13) (D Y κ fb )(A, B) = I S n -L -1 [A 2 +B 2 ] 1/2 • L B . (2.14)
Here, I S n is the identity map on S n and

U ∈ S n → L C (U ) = C • U := (CU + U C)/2
stands for the Lyapunov operator associated to C ∈ S n .

When κ is taken as the Fisher-Burmeister complementarity function, the equation (2.12) reads

E t (∆X) + F t (∆Y ) = -κ fb (X t , Y t ) (2.15)
with (E t , F t ) ∈ ∂κ fb (X t , Y t ). An explicit formula for computing the Clarke subdifferential of κ fb can be found in [START_REF] Zhang | Differential properties of the symmetric matrix-valued Fischer-Burmeister function[END_REF]. If the matrix X 2 t + Y 2 t is nonsingular, then Lemma 2.5 yields

E t = I S n -L -1 Ct • L Xt , F t = I S n -L -1 Ct • L Yt , where C t := [X 2 t + Y 2 t ] 1/2
. In such a case, (2.15) takes the form

∆X -L -1 Ct (L Xt (∆X)) + ∆Y -L -1 Ct (L Yt (∆Y )) = -κ fb (X t , Y t )
. By applying L Ct on each side of the above equality and rearranging terms, one gets

(X t -[X 2 t + Y 2 t ] 1/2 ) • ∆X + (Y t -[X 2 t + Y 2 t ] 1/2 ) • ∆Y = [X 2 t + Y 2 t ] 1/2 • κ fb (X t , Y t ). (2.16)
In our first two experiments (cf. Tables 2.1 and 2.2), the map L is generated by means of a random mechanism. To be more precise, we suppose that L is Gaussian, i.e., the entries of L are independent random variables distributed according to a standard normal law. The "entries" of L refer to the entries of the matrix representation of L with respect to the canonical basis {E i,j } 1≤i≤j≤n of S n . If {e i } n i=1 denotes the canonical basis of R n , then

E i,j := e i e T i if i = j, (e i e T j + e j e T i )/ √ 2 if i = j.
The dimension of the space End(S n ) is equal to t 2 n , where

t n := dim(S n ) = n(n + 1)/2.
So, one needs exactly t 2 n scalars for defining L. The percentages reported in The word "success" in Table 2.1 means that the selected random initial point z 0 has led to a solution, i.e., to a root of (2.9). Of course, as in any Newton type method, one can perfectly well encounter a situation of failure (divergence or ill-conditioning). As one can see from Table 2.1, the cases of ill-conditioning and divergence do not occur very often. We mention in passing that we never encountered a situation of nonsmoothness, i.e., at each visited point z t = (X t , Y t , λ t ), the matrix X 2 t + Y 2 t was always nonsingular.

In order to find a Loewner-eigenvalue of a given L, one initial point if often enough. On some occasions, however, one has to run the SNM with more than one initial point. Table 2.2 displays the expected Number of Initial Points (NIPs) needed for detecting a solution. These figures have been estimated by using a sample of 10 4 Gaussian random maps L, so they correspond to average values. The expected (or average) CPU time needed for detecting a solution increases of course with n. Remark 2.6. Note that (2.10)-(2.12) is a system of n 2 +n+1 equations in the same number of unknown variables. So, the order of the system increases quadratically with n. This explains somehow the rapid growth in CPU time reported in Table 2.2.

n = 3 n = 6 n = 9 n =
The results reported in Table 2.1 are extremely encouraging. However, one should not be overoptimistic when L belongs to some special subsets of the space End(S n ). We have found that the percentages of success of the SNM are significatively lower if L has for instance the special structure

L(X) = AXA + C, X B, (2.17)
where A, B, C ∈ S n .

Remark 2.7. By the way, as shown in the Appendix, it is possible to construct a triplet (A, B, C) for which the map (2.17) has infinitely many Loewner-eigenvalues. Such situation is however unlikely to occur if the matrices A, B, C are randomly generated. Two comments on Table 2.3 are in order.

i) Sometimes the current point

z t = (X t , Y t , λ t ) is such that X 2 t + Y 2 t is singular.
As shown in the last row of Table 2.3, such situation occurs but it is rather rare. In our opinion, it is not worthwhile to discuss in this paper the sophisticated issue of selecting a pair (E t , F t ) in ∂κ fb (X t , Y t ). Instead of bothering with the computation of the set ∂κ fb (X t , Y t ), we simply use the equation (2.16), which makes sense even if X 2 t + Y 2 t is singular. The fact of encountering a point of nonsmoothness does not lead necessarily to a situation of failure.

ii) The instances of failure are essentially due to ill-conditioning, and not to divergence.

This phenomenon is reinforced when n increases, see the last column of Table 2.3.

Fixing the ill-conditioning problem induced by the special map (2.17) is not however the main concern of this work.

In spite of the negative results reported in Table 2.3, one can still consider the SNM as a viable strategy for computing the Loewner-eigenvalues of the map (2.17). Of course, one must accept the possibility of initializing the SNM with a large number of initial points. As shown in Table 2.4, the expected NIPs needed for detecting a solution grow rapidly with n.

n = 3 n = 6 n = 9 n =

Performance of κ min

We now turn the attention to the minimum complementarity function. The equation (2.12) takes the form

E t (∆X) + F t (∆Y ) = -κ min (X t , Y t ) (2.18)
with (E t , F t ) ∈ ∂κ min (X t , Y t ). We shall need following differentiability lemma due to Malick and Sendov [START_REF] Malick | Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices[END_REF]. The notation O(n) stands for the set of orthogonal matrices of order n, λ(X) refers to the n-dimensional vector whose components are the eigenvalues of X ∈ S n arranged in nondecreasing order, Diag(x) is the diagonal matrix whose diagonal entries are the components of x ∈ R n , and ⊙ is used to indicate the Hadamard (or componentwise) product. For each x ∈ R n such that Π n i=1 x i = 0 and x 1 ≤ . . . ≤ x n , one defines B(x) ∈ S n by setting

(B(x)) i,j :=        0 if i ≤ q, j ≤ q, 1 if i > q, j > q, x j /(x j -x i ) if i ≤ q, j > q, x i /(x i -x j ) if i > q, j ≤ q,
where q is the number of negative components of x.

Lemma 2.8 [START_REF] Malick | Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices[END_REF]. The function M : S n → R, defined by

M(X) := min Y 0 1 2 X -Y 2 ,
is differentiable and its gradient at X is equal to Π S n + (X). Furthermore, M is twice differentiable at X if and only if X is nonsingular, in which case

D 2 M(X)(H 1 , H 2 ) = B(λ(X)), (U T H 1 U ) ⊙ (U T H 2 U ) , (2.19)
where

U ∈ O(n) is such that X = U Diag(λ(X))U T .
Thus, for all nonsingular X ∈ S n , one has

D 2 M(X)(H 1 , H 2 ) = DΠ S n + (X)(H 1 ), H 2 and computing DΠ S n + (X)(H)
is nothing but to find the Riesz representation of the linear functional D 2 M(X)(H, •). By using the formula (2.19), one gets

DΠ S n + (X)(H) = U B(λ(X)) ⊙ (U T HU ) U T = 1≤i,j≤n B(λ(X)), (U T HU ) ⊙ (U T E i,j U ) E i,j . (2.20)
For numerical purposes, we rely on the representation (2.20).

Lemma 2.9. Let A, B ∈ S n be such that A -B is nonsingular. The κ min is differentiable at (A, B) and the partial differentials (with respect to X and Y ) are given by

(D X κ min )(A, B) = I S n -DΠ S n + (A -B), (D Y κ min )(A, B) = DΠ S n + (A -B).
By exploiting the formulas established in Lemma 2.9, one sees that (2.18) takes the form As in Table 2.1, we never encountered a situation of nonsmoothness. Table 2.5 shows that, in terms of percentages of success, the performance of κ = κ min is of the same order as κ = κ fb . By contrast, Table 2.6 shows that the CPU time needed by κ = κ min is clearly higher than the CPU time needed by κ = κ fb . The reason is that the computational effort for determining (E t , F t ) in (2.18) is much higher than in (2.15).

[I S n -DΠ S n + (X t -Y t )](∆X) + DΠ S n + (X t -Y t )(∆Y ) = -κ min (X t , Y t ). whenever X t -Y t is
Remark 2.10. The performance of κ = κ min is similar to that of κ = κ fb , also when L has the special structure (2.17). For avoiding repetitions, we omit writing down the corresponding table.

A brief comment on the squaring technique

The squaring technique is based on the representability of the SDP cone as a cone of squares:

S n + = {U 2 : U ∈ S n }.
One can get rid of the constraints X 0 and Y 0 by writing X = U 2 and Y = V 2 . With such change of variables, the model (2.1) takes the form of a smooth system of equations:

Φ (U 2 , V 2 , λ) = 0, U 2 , V 2 = 0. (2.21)
Unfortunately, the last equality in (2.21) is at the origin of a certain ill-conditioning in the whole system. Besides, the system (2.21) is not square. By following a similar strategy as in [9,10], one may shift the attention to a certain "companion" system

Φ(U 2 , V 2 , λ) = 0, U • V = 0, (2.22)
which is smooth, square, and usually well-conditioned. It must be observed that (2.22) is related, but not equivalent, to the original problem (2.21). More precisely, U 2 , V 2 = 0 implies U • V = 0, but not conversely. The triplet (U, V, λ) is declared a fake solution to (2.21) if the system (2.22) holds, but U 2 , V 2 = 0.

Example 2.11. Consider the problem of finding a Loewner-eigenvalue of the map L given by L(X) = tr(X)I n , where I n is the identity matrix of order n.

The companion system (2.22) becomes    I n -λU 2 -V 2 = 0, U 2 -1 = 0, U • V = 0.
(2.23)

One can check that

(U, V, λ) = -e 1 e T 1 + e n e T n √ 2 , n i=1 e i e T n+1-i , 0 (2.24)
is a fake solution. Indeed, (2.24) solves the system (2.23), but

U 2 , V 2 = e 1 e T 1 + e n e T n 2 , I n = 1.
If one considers a map L ∈ End(S n ) that is randomly generated according to a Gaussian distribution and applies the classical Newton method to the companion system

   L(U 2 ) -λU 2 -V 2 = 0, U 2 -1 = 0, U • V = 0, (2.25)
then one observes experimentally that, in case of convergence, one always obtains a triplet (U, V, λ) that is not a fake solution, but a true one. In other words, the delivery of a fake solution is a rather exceptional event. Instances of ill-conditioning in (2.25) can be observed from time to time, but not frequently. On the negative side, our numerical tests show that Newton's method applied to (2.25) requires a very careful selection of the initial point in order to ensure convergence. In view of this observation, it is reasonable to introduce a suitable globalization technique as recommended by some authors.

On Loewnerian cones

In what follows, GL(S n ) stands for the group of invertible linear endomorphisms on S n , i.e.,

GL(S

n ) := {F ∈ End(S n ) : F is invertible}.
The next definition concerns a class of closed convex cones that are somewhat similar to S n + .

Definition 2.12.

A closed convex cone K in S n is Loewnerian if it representable as K = {F(U ) : U 0} (2.26)
for some F ∈ GL(S n ). One refers to (2.26) as the Loewnerian cone induced by F.

A Loewnerian cone is nothing but the image of S n + under some invertible linear endomorphism on S n . The map F in the representation formula (2.26) is not unique. In fact,

F 1 , F 2 ∈ GL(S n ) induce the same Loewnerian cone ⇔ (F -1 2 • F 1 )(S n + ) = S n + .
Since S n + is proper and nonpolyhedral, so is any Loewnerian cone. A closed convex cone is called proper if it is pointed and solid. A Loewnerian cone can also be represented in the "inverse image" form

K = {X ∈ S n : G(X) 0} (2.27)
for some G ∈ GL(S n ). One passes from (2.26) to the dual representation (2.27) by taking G as the inverse of F. Conversely, one passes from (2.27) to the primal representation (2.26) by taking F as the inverse of G. The dual of a Loewnerian cone is a Loewnerian cone. Indeed, for all F ∈ GL(S n ), one has

{F(U ) : U 0} * = {F -T (V ) : V 0} (2.28)
with F -T standing for the adjoint map of the inverse of F. The following proposition concerns the facial structure of Loewnerian cones.

Proposition 2.13. Let K be a Loewnerian cone induced by F ∈ GL(S n ).

(a) Each face of K is an exposed face. Furthermore, {dim(M) : M face of K} = {t 1 , . . . , t n } , where t k := k(k + 1)/2 stands for the k-th triangular number.

(b) M is a t k -dimensional face of K if and only if M = {F(U ) : U 0, Im U ⊆ L} for some linear subspace L ⊆ R n of dimension k.
Proof. As an application of [4, Theorem 5], one sees that the transformation

2 S n F ♯ -→ 2 S n F ♯ (E) := {F(U ) : U ∈ E}
is a bijection between the faces of S n + and the faces of K. One can also check that A proper cone K in S n is called rotund (cf. [START_REF] Stern | Invariant ellipsoidal cones[END_REF]) if every face of K, other than K itself and {0}, is a half-line. Rotund cones are often times referred to as strictly convex cones because they are characterized by the strict convexity condition

dim[F ♯ (E)] = dim(E)
X 1 , X 2 ∈ K not collinear =⇒ X 1 + X 2 ∈ int(K).
(2.29)

By definition, a proper cone K in S n is smooth if its dual is rotund.

Corollary 2.14. A Loewnerian cone in S n , with n ≥ 3, is neither rotund nor smooth.

Proof. Suppose that n ≥ 3. A rotund cone in S n does not have a face of dimension t 2 = 3.

Hence, it cannot be Loewnerian by Proposition 2.13(a). A smooth cone in S n cannot be Loewnerian either, because its dual is rotund.

Complementarity relative to Loewnerian cones

Consider the general complementarity problem (2.5) with K being a Loewnerian cone induced by F. Thanks to the duality formula (2.28) and the fact that

F(U ), F -T (V ) = U, V
for all U, V ∈ S n , the model (2.5) can be written in the equivalent form

Φ(F(U ), F -T (V ), λ) = 0, 0 U ⊥ V 0. (2.30)
The latter complementarity problem has of course the same structure as (2.1). We are then back to the context of Section 2.2. One can solve (2.30) by using for instance the complementarity function technique with the Fisher-Burmeister function κ fb . Another option is to use the complementarity function technique directly on (2.5). As complementarity function for the Loewnerian cone K one can use for instance

κ fb (X, Y ) := κ fb F -1 (X), F T (Y ) .
Example 2.15. Consider the problem of finding a real λ such that the system

K ∋ X ⊥ (L(X) -λX) ∈ K * has a nonzero solution X ∈ S n .
If K is a Loewnerian cone induced by F, then everything boils down to solve the nonlinear system

     L(F(U )) -λF(U ) -F -T (V ) = 0, tr(F(U )) -1 = 0, κ bf (U, V ) = 0.
Alternatively, one can work with the original variables X and Y :

     L(X) -λX -Y = 0, tr(X) -1 = 0, κ fb (X, Y ) = 0.

Examples of Loewnerian cones and counter-examples

We now address a short list of interesting proper cones that are Loewnerian. We do not claim that all these cones are relevant in the theory of complementarity problems, but it is reasonable to get acquainted with these examples just for the sake of academic knowledge. We start by stating a trivial but useful lemma.

Lemma 2.16. Let C, B ∈ S n be such that C, B = 1. Then the map G :

S n → S n defined by G(X) = C, X B -X (2.31)
is invertible and its inverse F : S n → S n is given by

F(U ) = C, U C, B -1 B -U.
Proof. For all U ∈ S n , the matrix equation C, X B -X = U admits a unique solution X ∈ S n . Indeed, by taking the inner product with respect to C one gets

C, X ( C, B -1) = C, U .
From here one derives C, X as a function of U and then one finds the solution X itself.

If X, B are symmetric matrices with B positive definite, then λ max (X, B) denotes the largest real λ for which det(X -λB) = 0. When B is the identity matrix one simply writes λ max (X).

Proposition 2.17. Let C, B ∈ S n with B positive definite. The condition C, B = 1 is necessary and sufficient for the closed convex cone

K = {X ∈ S n : λ max (X, B) ≤ C, X } (2.32)
to be Loewnerian.

Proof. Let G : S n → S n be given by (2.31). One has

G(X) 0 ⇔ C, X B X ⇔ u, Xu ≤ C, X u, Bu for all u ∈ R n ⇔ λ max (X, B) ≤ C, X .
In other words, K is representable as in (2.27). If C, B = 1, then G is invertible by Lemma 2.16, and therefore

K is Loewnerian. If C, B = 1, then R(B) = Ker(G) ⊆ K.
Hence, K is not pointed because it contains the line generated by B.

Remark 2.18. Suppose that C, B = 1. The Loewnerian cone (2.32) is not self-dual in general. However, its dual

K * = Y ∈ S n : λ max (Y, C) ≤ B, Y C, B -1 has the same structure as (2.32). Corollary 2.19. Let α ∈ R\{0, 1}. Then K = X ∈ S n : α λ max (X) ≤ n -1 tr(X) K * = Y ∈ S n : (1 -α)λ max (Y ) ≤ n -1 tr(Y )
are mutually dual Loewnerian cones.

Proof. One just needs to apply Proposition 2.17 with B = I n and C = (αn) -1 I n .

Recall that λ(X) = (λ 1 (X), . . . , λ n (X)) T is the vector whose components are the eigenvalues of X ∈ S n arranged in nondecreasing order. A spectral proper cone in S n is a set of the form

K = {X ∈ S n : λ(X) ∈ P } , (2.33)
where P is a permutation invariant proper cone in R n . An interesting family {K ↑ q } n q=1 of spectral proper cones arising in applications is given by

K ↑ q := X ∈ S n : q i=1 λ i (X) ≥ 0 .
These cones have been studied in [3] and in many other publications. For q = 1, one gets

K ↑ 1 = {X ∈ S n : λ min (X) ≥ 0} = S n + .
The choice q = n -1 leads to

K ↑ n-1 = {X ∈ S n : λ max (X) ≤ tr(X)} ,
which is also a Loewnerian cone (cf. Corollary 2. 19). The analysis of the case 2 ≤ q ≤ n -2 is more involved. The next proposition concerns the choice q = 2.

Proposition 2.20. Let n ≥ 4. The cone

K ↑ 2 = {X ∈ S n : λ 1 (X) + λ 2 (X) ≥ 0} (2.34)
is not Loewnerian.

Proof. The cone K ↑ 2 admits the representation (2.33) with

P = {x ∈ R n : x i + x j ≥ 0 for all 1 ≤ i < j ≤ n}.
Such set P is a permutation invariant proper cone. Note that P is also polyhedral. In view of [14, Lemma 2.1], the set

E = {x ∈ P : x i + x n-1 = 0 for all i = 1, . . . , n -2}
is a two-dimensional exposed face of P . By using such face E and Lewis's facial theorem [16,Theorem 5.1], one can construct a two-dimensional face for K ↑ 2 . This fact and Proposition 2.13(a) prove that K ↑ 2 is not Loewnerian.

The cone K ↑ n-2 is not Loewnerian either, because it is the image of K ↑ 2 under a nonsingular transformation. In fact, one has the following general result. Proposition 2.21. Let q ∈ {1, . . . , n -1}. Then the linear map

X ∈ S n → G(X) := tr(X) q I n -X is a bijection between K ↑ n-q and K ↑ q .
Proof. That G is invertible is clear from Lemma 2.16. Since

λ i (G(X)) = tr(X) q -λ n-i+1 (X)
for all i ∈ {1, . . . , n}, one has

q i=1 λ i (G(X)) = tr(X) - q i=1 λ n-i+1 (X) = n-q i=1 λ i (X).
Hence,

K ↑ n-q = X ∈ S n : n-q i=1 λ i (X) ≥ 0 = X ∈ S n : q i=1 λ i (G(X)) ≥ 0 = G -1 (K ↑ q ).
This completes the proof.

By a revolution cone in S n one understands a proper cone of the form

Rev(s, Y ) := {U ∈ S n : s U ≤ Y, U }, where 0 < s < 1 and Y ∈ S n is such that Y = 1.
A revolution cone is a particular instance of an ellipsoidal cone. By definition, an ellipsoidal cone in S n is a set representable as

E(D, B) := {X ∈ S n : D(X) ≤ B, X }, ( 2
E(D, B) = D -1 (U ) : U ∈ Rev 1 D -T B , D -T (B) D -T B ,
i.e., the action of D on the ellipsoidal cone (2.35) produces a revolution cone. So, it is enough to show that a suitable chain

S 2 L 1 -→ R 3 L 2 -→ R 3 L 3 -→ S 2
of linear isomorphisms allows us to pass from a revolution cone to S 2 + . One starts with the standard linear isometry

L 1 α β β γ :=   α √ 2β γ  
between S 2 and R 3 . The action of L 1 on a revolution cone Rev(s, Y ) in S 2 produces a revolution cone rev(s, y) := {u ∈ R 3 : s u ≤ y T u} in R 3 . Then one constructs a linear invertible map L 2 : R 3 → R 3 that converts rev(s, y) into the ice-cream cone Proposition 2.23. Consider a matrix A ∈ M n with possible complex eigenvalues µ 1 , . . . , µ n . Then

L 3 := {x ∈ R 3 : [x 2 1 + x 2 2 ] 1/2 ≤ x 3 }. Such an L 2 clearly exists.
K lyap := {X ∈ S n : AX + XA T 0}, (2.36)
K stein := {X ∈ S n : X A T XA} (2.37)
are Loewnerian cones under the respective assumptions

µ i + µ j = 0 for all i, j ∈ {1, . . . , n}, (2.38)
µ i µ j = 1 for all i, j ∈ {1, . . . ,
G lyap (X) := AX + XA T , G stein (X) := X -A T XA.
As established in [15], the spectral condition (

S m • := {X ∈ S m : diag(X) = 0}
, where diag(X) denotes the vector whose components are the diagonal entries of X. There is a rich literature devoted to the analysis and applications of the cone

E m := {A ∈ S m • : A is an EDM}.
The following proposition exploits the fact that S n+1

• has the same dimension as S n .

Proposition 2.24. Let φ be a linear isomorphism between S n+1

• and S n . Then

K = {φ(A) : A ∈ E n+1 } (2.40)
is a Loewnerian cone.

Proof. There exists a linear isomorphism L : S n → S n+1

• such that

E n+1 = {L(U ) : U 0}.
As shown in [1, Theorem 3.2], one may consider for instance

L(U ) := 0 [diag(U )] T diag(U ) B(U ) -2U ,
where

B(U ) := [diag(U )]1 T n + 1 n [diag(U )]
T and 1 n is the n-dimensional vector of ones. Hence, (2.40) is a Loewnerian cone induced by the composition F = φ • L.

Remark 2.25. The dual of (2.40) is the Loewnerian cone induced by φ -T • L -T . A matter of computation shows that L -T : S n → S n+1

• is given by

L -T (V ) = 1 2 0 (V 1 n ) T V 1 n -V ⋄ ,
where V ⋄ is derived from V by setting zero to the diagonal entries.

An interesting problem of numerical linear algebra addressed in [1,11,[START_REF] Qi | A semismooth Newton method for the nearest Euclidean distance matrix problem[END_REF] is this: Given a matrix C ∈ S n+1

• generated by a random mechanism or obtained as outcome of some physical experiment, one wishes to determine

Π E n+1 (C) := projection of C onto E n+1 .
This problem is handled in [1,11] by expressing E n+1 as intersection of two "simpler" cones and by applying an alternating projection algorithm. We use here a completely different approach:

-Firstly, we introduce a linear isometry φ : S n+1 • → S n and shift the attention to the Loewnerian cone K = φ(E n+1 ). Since φ is not merely a linear isomorphism, but also a linear isometry, one has

Π E n+1 (C) = φ T (Π K (A))
with A := φ(C). Indeed,

φ T (Π K (A)) -C = Π K (A) -A = min X∈K X -A = min W ∈E n+1 φ(W ) -A = min W ∈E n+1 W -C .
-Secondly, in order to find the projection of A onto K, we solve the complementarity problem K ∋ X ⊥ (X -A) ∈ K * (2.41) by using the SNM and a suitable complementarity function.

We now explain the details. As linear isometry φ : S n+1

• → S n we consider the map

φ 0 b T b M = M + √ 2 Diag(b),
whose adjoint is given by

φ T (Z) = 0 1 √ 2 [diag(Z)] T 1 √ 2 diag(Z) Z ⋄ .
Hence, K = φ(E n+1 ) is the Loewnerian cone induced by

F(U ) = B(U ) -2U + √ 2 Diag(diag(U )).
A matter of computation shows that

F -1 (X) = (1/ √ 8 ) B(X) -(1/2)X ⋄ , F T (Y ) = Diag √ 2 diag(Y ) + 2Y ⋄ 1 n -2Y ⋄ , F -T (V ) = (1/ √ 2 ) Diag(V 1 n ) -(1/2)V ⋄ .
One can solve the complementarity problem (2.41) by applying the SNM to the system

X -Y -A = 0, κ fb (X, Y ) = 0. (2.42)
We initialize the algorithm with a random Gaussian matrix X 0 and Y 0 = X 0 -A. The complementarity problem (2.41) can also be solved by applying the SNM to

F(U ) -F -T (V ) -A = 0, κ fb (U, V ) = 0. (2.43)
By way of initialization, we generate a random Gaussian matrix Ξ and set U 0 = F -1 (Ξ) and Remark 2.26. In a recent paper by Qi [START_REF] Qi | A semismooth Newton method for the nearest Euclidean distance matrix problem[END_REF], the nearest EDM problem is treated by passing to a certain dual optimization problem

V 0 = F T (Ξ -A).
minimize z∈R n+1 θ(z) := (1/2) Π Q n+1 [C + Diag(z)] 2 , (2.44)
where

Q n+1 := {A ∈ S n+1 : x, Ax ≥ 0 when 1 n+1 , x = 0}.
Note that the optimization problem (2.44) is unconstrained. The approach followed in [START_REF] Qi | A semismooth Newton method for the nearest Euclidean distance matrix problem[END_REF] consists in using the SNM to find a root of the gradient map

∇θ(z) := diag Π Q n+1 [C + Diag(z)] .
Once a root z has been found, then one evaluates

Π E n+1 (C) = Π Q n+1 (C + Diag(z)) .
Projecting onto Q n+1 offers no difficulty.

By way of conclusion

This work shows that the Semi-Definite Complementarity Problem (SDCP) can be solved efficiently by applying the Semismooth Newton Method (SNM) to the system (2.6). The best results in terms of CPU time are obtained with the help of the Fisher-Burmeister complementarity function κ fb . Some comments concerning the genesis of this work and the related literature are appropriate.

1. The idea of applying the SNM to a cone-constrained eigenvalue problem was considered for the first time by Adly and Seeger [2]. The specific problem treated in [2] is that of finding Pareto-eigenvalues in a given matrix A. This amounts to solve a complementarity problem

   Ax -λx -y = 0, 1 n , x -1 = 0, 0 ≤ x ⊥ y ≥ 0 (2.45)
involving the usual cone R n + . Although the model (2.3) looks similar to (2.45), there are important differences. To start with, (2.3) leads to a square system with n 2 + n + 1 equations, whereas (2.45) leads to a square system with only 2n + 1 equations. Hence, the involved dimensions are not of the same order. Secondly, the nonnegative orthant is a polyhedral cone, whereas the SDP cone is non-polyhedral. As a consequence of this fact, a matrix A has always a finite number of Pareto-eigenvalues, whereas a linear endomorphism L on S n may perfectly well have a continuum of Loewnereigenvalues (cf. Proposition 2.27). In other words, the solution sets to (2.3) and (2.45) are structurally different. Thirdly, the squaring technique x = u [2] := u ⊙ u, y = v [2] := v ⊙ v based on the Hadamard product leads to a companion system    Au [2] λu [2] v [2] = 0,

u 2 -1 = 0, u ⊙ v = 0, (2.46)
that is free of fake solutions. By contrast, the companion system (2.25) associated to (2.3) may well admit fake solutions. In short, a complementarity problem relative to the SDP cone differs substantially from a complementarity problems relative to the nonnegative orthant. We also mention that although we have given a list of proper cones that are Loewnerian, a complete characterization of proper cones which are Loewnerian remains as an open question.

Appendix

Let σ(L, S n + ) denote the set of Loewner-eigenvalues of a linear map L : S n → S n . Such set is called the Loewner-spectrum of L. The following proposition displays a map L whose Loewner-spectrum is a set of infinite cardinality. Proposition 2.27. Let L : S n → S n be given by L(X) = C, X I n , where C 0. Then

[λ min (C), λ max (C)] ⊆ σ(L, S n + ) = n r=1 [f r (C), g r (C)] , (2.47)
where f r (C) and g r (C) indicate respectively the sum of the r smallest and the sum of the r largest eigenvalues of C.

Proof. Assume that C = 0, otherwise (2.47) holds trivially. A scalar λ belongs to σ(L, S n + ) if and only if there exists

X ∈ S n such that      X 0, tr(X) = 1, C, X I n λX, C, X = λ X 2 .
Hence,

σ(L, S n + ) = X -2 C, X : X ∈ Ω , (2.48)
where Ω stands for the set of matrices X ∈ S n satisfying X 0, tr(X) = 1, (2.49)

C, X ( X 2λ max (X)) ≥ 0.

(2.50) Under (2.49), the inequality (2.50) can be written as an equality. The set on the right-hand side of (2.48) remains unchanged if one uses

Ω 0 := X ∈ S n : X 0, tr(X) = 1, λ max (X) = X 2
instead of Ω. On the other hand, one can check that

Ω 0 = n r=1 r -1 QQ T : Q ∈ O(n, r) ,
where

Q ∈ O(n, r) indicates that Q is matrix of size n × r such that Q T Q = I r . Hence, σ(L, S n + ) = n r=1 C, QQ T : Q ∈ O(n, r) .
Note that C, QQ T ranges over the interval [f r (C), g r (C)] as the variable Q ranges over O(n, r).

Chapter 3

Critical angles between two convex cones I. General theory Alberto Seeger1 and David Sossa2

Abstract. The concept of critical (or principal) angle between two linear subspaces has applications in statistics, numerical linear algebra, and other areas. Such concept has been abundantly studied in the literature, both from a theoretical and computational point of view. Part I of this work is an attempt to build a general theory of critical angles for a pair of closed convex cones. Part II focusses on the practical computation of the maximal angle between specially structured cones.

Introduction

This work is the merging point of two independent sources: the recent theory of critical angles for a closed convex cone, as developed in [6], and the old theory of principal angles for a pair of linear subspaces. Let (X, •, • ) be a Euclidian space3 of dimension at least two and let C(X) be the set of nontrivial closed convex cones in X. That a closed convex cone is nontrivial means that it is different from the zero cone and different from the whole space.

Computing the maximal angle of a closed convex cone is an issue of importance in a number of applications, see for instance [15]. By definition, the maximal angle of K ∈ C(X) is the number

θ max (K) := max u,v∈K∩S X arccos u, v , (3.1)
where S X is the unit sphere of X. By writing down the necessary optimality conditions for the nonconvex optimization problem (3.1), one gets

u, v ∈ K ∩ S X , v -u, v u ∈ K * , u -u, v v ∈ K * , (3.2)
where K * denotes the positive dual cone of K. If the system (3.2) holds, then (u, v) is called a critical pair of K and arccos u, v is called a critical angle of K. The study of critical angles in a convex cone was initiated in [6] and further continued in [5,7,8,9,11]. The purpose of the present work is to build a theory of critical angles for a pair of convex cones. The starting point of our analysis is the formulation of the optimization problem that defines the maximal angle between two convex cones.

Definition 3.1. Let P, Q ∈ C(X). The maximal angle of (P, Q) or, more precisely, the maximal angle between P and Q, is given by

Θ(P, Q) := max u∈P ∩S X , v∈Q∩S X arccos u, v . (3.3)
An antipodal pair of (P, Q) is any pair (u, v) ∈ X 2 solving the above maximization problem.

Antipodal pairs always exist, but they are not unique in general. The formulation of the maximization problem (3.3) is motivated by theoretical and practical considerations.

Example 3.2. Consider the space S n of symmetric matrices of order n equipped with the trace inner product A, B = tr(AB). An interesting question of linear algebra is to compute the maximal angle between the cones

S n + := {A ∈ S n : A is positive semidefinite}, N n := {B ∈ S n : B is nonnegative entrywise}.
One usually refers to S n + as the Loewner cone in S n . By relying on graph theory arguments, Goldberg and Shaker-Monderer [4] obtained a lower bound for the maximal angle Θ(S n + , N n ) and proved the asymptotic formula

lim n→∞ Θ(S n + , N n ) = π.
It remains an open question to compute the exact value of Θ(S n + , N n ).

In Section 3.4 we present additional motivations for the study of maximal angles of pairs of convex cones. Next, we write down the necessary optimality conditions for the nonconvex optimization problem (3.3). Proposition 3.3. Let P, Q ∈ C(X). A necessary condition for (u, v) ∈ X 2 to be an antipodal pair of (P,

Q) is that          u ∈ P ∩ S X , v ∈ Q ∩ S X , v -u, v u ∈ P * , u -u, v v ∈ Q * .
(3.4)

Proof. Let (u, v) be an antipodal pair of (P, Q). In particular, the component u minimizes the linear form •, v on P ∩ S X . Consider an arbitrary nonzero vector d ∈ P . Clearly,

u(t) := u + td -1 (u + td) ∈ P ∩ S X for all t in some interval [0, ε[. Furthermore, t = 0 is a minimum of the function t ∈ [0, ε[ → f (t) := u(t), v .
Hence, the right-derivative

lim t→0 + f (t) -f (0) t = v, d -u, v u, d
is nonnegative. This proves the third condition in (3.4). Analogously, the last condition in (3.4) is obtained by using the fact v minimizes u, • on Q ∩ S X .

In a similar way one can handle the angle minimization problem

   mimimize arccos u, v u ∈ P ∩ S X , v ∈ Q ∩ S X ,
which arises in a number of applications (cf. [14,19]). The necessary optimality conditions for angle minimization are similar to (3.4), but one must change dual cones by polar cones. In order to avoid repetitions in the exposition, this work focusses only on angle maximization.

Definition 3.4. Let P, Q ∈ C(X).

(i) A critical pair of (P, Q) is a pair (u, v) ∈ X 2 satisfying the system (3.4). The corresponding angle arccos u, v is called a critical angle of (P, Q).

(ii) A critical pair (u, v) of (P, Q) is called proper if u and v are not collinear. The corresponding angle is called a proper critical angle of (P, Q).

The main concern of this work is to provide rules for computing antipodal pairs and, more generally, critical pairs. We wish also to analyze the structure of Γ(P, Q) := {arccos u, v : (u, v) satisfies (3.4)}, a set called the angular spectrum of (P, Q). By convention, we write Γ(P, Q) := {0, π} if either P or Q is the whole space X. In general, Γ(P, Q) is a nonempty closed subset of the interval [0, π]. Beware, however, that the cardinality of Γ(P, Q) is not necessarily finite. In other words, a pair (P, Q) may have infinitely many critical angles.

Duality and boundary principles for critical pairs

Let Ω X denote the set of all pairs of unit vectors in X that are not collinear, i.e.,

Ω X := {(u, v) ∈ S 2 X : | u, v | = 1}. To each (u, v) ∈ Ω X , one can associate its conjugate pair g(u, v) = v -u, v u 1 -u, v 2 , u -u, v v 1 -u, v 2 .
It is not difficult to check that g : Ω X → Ω X is a bijection with g -1 = g. In other words, g is an involution on Ω X . The following duality principle is an extension of [11,Theorem 2].

Theorem 3.5. Let P, Q ∈ C(X). Let (u, v) ∈ Ω X and (y, z) ∈ Ω X be conjugate pairs. Then (u, v) is a critical pair of (P, Q) if and only if (y, z) is a critical of (P * , Q * ).

Proof. Theorem 2 in [11] takes care of the particular case in which P is equal to Q. The proof of the general case follows the same pattern. Assume that (u, v) is critical for (P, Q) and write λ := u, v . Clearly,

y = [1 -λ 2 ] -1/2 (v -λu) ∈ P * ∩ S X , z = [1 -λ 2 ] -1/2 (u -λv) ∈ Q * ∩ S X .
Furthermore, µ := y, z = -λ and

z -µy = [1 -µ 2 ] 1/2 u ∈ P, y -µz = [1 -µ 2 ] 1/2 v ∈ Q.
Hence, (y, z) is critical for (P * , Q * ). The reverse implication is proven in a similar way.

Corollary 3.6. Let P, Q ∈ C(X). Let θ, ψ ∈ ]0, π[ be conjugate angles, i.e., θ + ψ = π. Then θ is a critical angle of (P, Q) if and only if ψ is a critical angle of (P * , Q * ).

Proof. Suppose that θ is a critical angle of (P, Q). Let (u, v) be any proper critical pair of (P, Q) such that cos θ = u, v . Thanks to the duality principle established in Theorem 3.5, the conjugate pair (y, z) = g(u, v) is critical for

(P * , Q * ). Since y, z = -u, v = -cos θ = cos(π -θ) = cos ψ,
one deduces that ψ is a critical angle of (P * , Q * ). The proof of the reverse implication is similar.

Intuitively speaking, the components u and v of a proper critical pair of (P, Q) should be on the boundaries of P and Q, respectively. The next theorem clarifies this point. For a set C contained in a linear subspace L of X, the symbol bd L (C) refers to the boundary of C relative to L. Theorem 3.7. Let L ⊆ X be the smallest linear subspace containing both P ∈ C(X) and Q ∈ C(X). Suppose that (u, v) is a proper critical pair of (P, Q). Then u ∈ bd L (P ) and v ∈ bd L (Q).

Proof. Since (u, v) is proper, one has λ := u, v / ∈ {-1, 1}. Suppose, to the contrary, that u belongs to the interior of P relative to L, i.e., there exists a positive ε such that

u + ε(B X ∩ L) ⊆ P,
where B X is the closed unit ball of X. It follows that

0 ≤ v -λu, u + εw = ε v -λu, w for all w ∈ B X ∩ L. The particular choice w = λu -v -1 (λu -v) leads to 0 ≤ ε λu -v -1 v -λu, λu -v = -ε v -λu < 0, a clear contradiction. This shows that u ∈ bd L (P ). The proof of v ∈ bd L (Q) is similar.
The next corollary follows straightforwardly by combining the duality principle stated in Theorem 3.5 and the boundary principle stated in Theorem 3.7.

Corollary 3.8. Let P, Q ∈ C(X) and (u, v) be a proper critical pair of (P, Q). Then

v -u, v u ∈ bd M (P * ), u -u, v v ∈ bd M (Q * ),
where M ⊆ X is the smallest linear subspace containing both P * and Q * .

Further characterization of criticality and antipodality

Let Π C (x) denote the projection of a point x ∈ X onto a nonempty closed convex set C ⊆ X.

The next proposition expresses criticality for a pair (P, Q) in terms of the projection maps Π P and Π Q .

Proposition 3.9. Let P, Q ∈ C(X). Let u, v be distinct points on the sphere S X . Then (u, v) is a critical pair of (P, Q) if and only if

Π P (u -v) = (1 -u, v ) u, Π Q (v -u) = (1 -u, v ) v. (3.5)
In particular, a necessary condition for (u, v) to be a critical pair of (P, Q) is that

dist(u -v, P ) = dist(v -u, Q).
Proof. Let λ := u, v . Let N P (u) denote the normal cone to P at u. Note that

Π P (u -v) = (1 -λ)u ⇔ Π P ((1 -λ) -1 (u -v)) = u ⇔ (1 -λ) -1 (u -v) ∈ u + N P (u) ⇔ -(v -λu) ∈ N P (u) ⇔ u ∈ P, v -λu ∈ P * .
Similarly, the second condition in (3.5) amounts to saying that v ∈ Q and uλv ∈ Q * .

Sometimes it is helpful to write the angle maximization problem (3.3) in any of the following equivalent forms

cos[Θ(P, Q)] = min u∈P ∩S X , v∈Q∩S X u, v , (3.6)
κ(P, Q) := min u∈P ∩S X , v∈Q∩S X u + v 2 . ( 3.7)
The problems (3.3), (3.6), and (3.7) have clearly the same solution set. Furthermore,

κ(P, Q) = cos Θ(P, Q) 2 . (3.8)
The next theorem relates (3.3) to the minimization problem

χ(P, Q) := min z∈S X max{dist(z, P ), dist(z, -Q)}. (3.9)
Although it is not clear at first sight, it turns out that solving (3.3) is equivalent to solving (3.9).

Theorem 3.10. Let P, Q ∈ C(X). Then

Θ(P, Q) = 2 arccos[χ(P, Q)]. (3.10)
Suppose, in addition, that P, Q are not equal to a common ray. In such a case, the solution set A(P, Q) to the angle maximization problem (3.3) and the solution set R(P, Q) to the problem (3.9) are related as follows:

R(P, Q) = u -v u -v : (u, v) ∈ A(P, Q) , (3.11)
A(P, Q) = Π P (z) Π P (z) , Π Q (-z) Π Q (-z) : z ∈ R(P, Q) .
(3.12)

Proof. If P and Q are equal to a common ray, then both sides of (3.10) are equal to 0. Suppose now that P and Q are not equal to a common ray. Suppose also that P ∩-Q = {0}, otherwise both sides of (3.10) are equal to π and the proof of (3.11)-(3.12) is immediate. Let z 0 be a solution to (3.9). Hence,

dist(z 0 , P ) = dist(z 0 , -Q) = χ(P, Q), Π P (z 0 ) = Π Q (-z 0 ) = s, with s := (1 -[χ(P, Q)] 2 ) 1/2 belonging to ]0, 1[. The pair (u 0 , v 0 ) := Π P (z 0 ) -1 Π P (z 0 ) , Π Q (-z 0 ) -1 Π Q (-z 0 ) = (1/s) ( Π P (z 0 ) , Π Q (-z 0 ) )
is then well defined. We claim that

z 0 = u 0 -v 0 -1 (u 0 -v 0 ), (3.13)
κ(P, Q) ≤ u 0 + v 0 2 = χ(P, Q). (3.14)
The inequality in (3.14) is obvious, but it is added for convenience. Let c : X → R be the objective function of the minimization problem (3.9), i.e., c(z) := max{dist(z, P ), dist(z, -Q)}.

Since z 0 minimizes (1/2)c 2 (•) on S X , it satisfies the optimality condition

λ 1 (z 0 -Π P (z 0 )) + λ 2 (z 0 -Π -Q (z 0 )) + µz 0 = 0, (3.15)
where µ ∈ R is a Lagrange multiplier and λ 1 , λ 2 ∈ R are nonnegative scalars adding up to 1. Since z 0 -Π P (z 0 ) is orthogonal to Π P (z 0 ) and z 0 -

Π -Q (z 0 ) is orthogonal to Π -Q (z 0 ), one gets z 0 , Π P (z 0 ) = z 0 , Π -Q (z 0 ) = s 2 .
This and (3.15) yield µ + 1 = s 2 and λ 1 = λ 2 = 1/2. Hence,

z 0 = (1/2s 2 ) (Π P (z 0 ) + Π -Q (z 0 )) = (1/2s)(u 0 -v 0 ).
This proves (3.13) and shows that z 0 ∈ cone {Π P (z 0 ), Π -Q (z 0 )} ⊆ L := span{u 0 , v 0 }.

In the plane L, consider the rectangular triangles co{0, z 0 , Π P (z 0 )} and co{0, z 0 , Π -Q (z 0 )}. Both triangles have the same angle at the vertex 0, namely, ψ = arcsin[χ(P, Q)]. It is plain to see that u 0 , -v 0 = cos(2ψ) = 1 -2 sin 2 ψ = 1 -2[χ(P, Q)] 2 . This leads directly to the equality (3.14). Next, let (u 1 , v 1 ) be an antipodal pair of (P, Q).

Then z 1 := u 1 -v 1 -1 (u 1 -v 1
) is well defined. From Proposition 3.9 one knows that

Π P (z 1 ) = u 1 -v 1 -1 (1 -u 1 , v 1 ) u 1 , Π Q (-z 1 ) = u 1 -v 1 (1 -u 1 , v 1 ) v 1 . (3.16) Hence, dist(z 1 , P ) = z 1 -Π P (z 1 ) = v 1 -u 1 , v 1 u 1 u 1 -v 1 = u 1 + v 1 2 = κ(P, Q) and, similarly, dist(z 1 , -Q) = dist(-z 1 , Q) = κ(P, Q). It follows that χ(P, Q) ≤ c(z 1 ) = κ(P, Q). (3.17)
From (3.16) one deduces also that

(u 1 , v 1 ) = Π P (z 1 ) -1 Π P (z 1 ), Π Q (-z 1 ) -1 Π Q (-z 1 ) . (3.18)
The combination of (3.13)-(3.14) and (3.17)-(3.18) completes the proof of the theorem.

Proposition 3.13. Let P, Q ∈ C(X). The following conditions are equivalent and imply that P * + Q * is closed:

(a) (P, Q) is reproducing.

(b) There exists a positive constant α such that

αB X ⊆ co((P ∪ -Q) ∩ B X ). (3.20)
The notation "co" refers of course to the convex hull operation. One can see Proposition 3.13 as a sort of dual version of Proposition 3.11. The coefficient

α(P, Q) := max{α ∈ [0, 1] : α satisfies (3.20)}
measures to which extent the pair (P, Q) is reproducing. The next proposition shows that evaluating the reproducibility coefficient of (P, Q) amounts to compute the maximal angle of (P * , Q * ). Proposition 3.14. Let P, Q ∈ C(X). Then

α(P, Q) = cos Θ(P * , Q * ) 2 .
Proof. By using duality arguments (namely, calculus rules for polar sets) one can show that the inclusion (3.20) can be written in the equivalent form

α [(B X + P * ) ∩ (B X -Q * )] ⊆ B X .
Hence, α(P * , Q * ) is equal to the coefficient

ν(P, Q) := max{r ∈ [0, 1] : r [(B X + P ) ∩ (B X -Q)] ⊆ B X }.
By proceeding as in [10, Theorem 2], one can check that ν(P, Q) = χ(P, Q). Theorem 3.10 does the rest of the job.

Lipschitzness of the maximal angle function

Topological issues on C(X) are relative to the spherical metric δ, which is defined by

δ(K 1 , K 2 ) := haus(K 1 ∩ S X , K 2 ∩ S X ).
Here,

haus(C 1 , C 2 ) := max max x∈C 1 dist(x, C 2 ), max x∈C 2 dist(x, C 1 )
stands for the classical Pompeiu-Hausdorff distance between a pair C 1 , C 2 of nonempty compact subsets of X. Convergence with respect to the spherical metric is equivalent to convergence in the Painlevé -Kuratowski sense. Topological issues on the product space C 2 (X) := C(X) × C(X) refer to the metric

∆((P 1 , Q 1 ), (P 2 , Q 2 )) := max {δ(P 1 , P 2 ), δ(Q 1 , Q 2 )} .
The next proposition concerns the continuity behavior of the multivalued map Γ. Upper and lower-semicontinuity of multivalued maps between metric spaces are understood in the classical sense, cf. [1, Section 1.4].

Proposition 3.15. The multivalued map Γ : C 2 (X) ⇒ R is upper-semicontinuous, but not lower-semicontinuous.

Proof. The values of Γ are closed subsets of the compact interval [0, π]. For proving that Γ is upper-semicontinuous, it is enough to check that

gr Γ := {(P, Q, θ) ∈ C 2 (X) × R : θ ∈ Γ(P, Q)} is a closed set. Let {(P k , Q k , θ k )} k∈N be a sequence in gr Γ converging to some (P, Q, θ) ∈ C 2 (X) × R. For each k ∈ N, there exists a pair (u k , v k ) ∈ X 2 such that            θ k = arccos u k , v k , u k ∈ P k ∩ S X , v k ∈ Q k ∩ S X , v k -u k , v k u k ∈ P * k , u k -u k , v k v k ∈ Q * k . (3.21)
Let (u, v) be the limit of some subsequence {(u ϕ(k) , v ϕ(k) )} k∈N . We write (3.21) with ϕ(k) instead of k. By passing then to the limit, one deduces that (P, Q, θ) ∈ grΓ. We now prove that Γ is not lower-semicontinuous. Let e 1 , e 2 ∈ S X be orthogonal. For each integer k ≥ 1, let

u k := -k -1 e 1 + 1 -k -2 1/2 e 2 , P k = R + u k := {tu k : t ≥ 0}, Q k = H e 1 := {x ∈ X : e 1 , x ≥ 0}.
A matter of computation shows that (u k , -u k ) is the unique critical pair of (P k , Q k ). Thus,

Γ(P k , Q k ) = {π}. On the other hand, Γ lim k→∞ P k , lim k→∞ Q k = Γ(R + e 2 , H e 1 ) = {0, π}.
This proves that Γ is not lower-semicontinuous.

As shown in the next theorem, the maximal angle function Θ : C 2 (X) → R is not merely continuous, but it is also Lipschitzian. Theorem 3.16. There exists a constant ℓ X such that

|Θ(P 1 , Q 1 ) -Θ(P 2 , Q 2 )| ≤ ℓ X ∆((P 1 , Q 1 ), (P 2 , Q 2 )) for all (P 1 , Q 1 ), (P 2 , Q 2 ) ∈ C 2 (X).
Proof. One knows from (3.8) that Θ : C 2 (X) → R admits the characterization Θ(P, Q) = 2 arccos (κ(P, Q)) .

(3.22)

We claim that κ satisfies the Lipschitz condition

|κ(P 1 , Q 1 ) -κ(P 2 , Q 2 )| ≤ ∆((P 1 , Q 1 ), (P 2 , Q 2 )). (3.23)
The proof of (3.23) follows the same pattern as in [10, Lemma 1]. Let u 2 ∈ P 2 ∩ S X and

v 2 ∈ Q 2 ∩ S X be such that 2κ(P 2 , Q 2 ) = u 2 + v 2 .
Let u 1 , v 1 be the projections of u 2 , v 2 onto P 1 ∩ S X and Q 1 ∩ S X , respectively. Hence,

2(κ(P 1 , Q 1 ) -κ(P 2 , Q 2 )) ≤ u 1 + v 1 -u 2 + v 2 ≤ u 1 -u 2 + v 1 -v 2 = dist(u 2 , P 1 ∩ S X ) + dist(v 2 , Q 1 ∩ S X ) ≤ e(P 2 , P 1 ) + e(Q 2 , Q 1 ),
where one uses the notation e(K 2 , K 1 ) := sup

u∈K 2 ∩S X dist(u, K 1 ∩ S X ).
In a similar way one gets

2(κ(P 2 , Q 2 ) -κ(P 1 , Q 1 )) ≤ e(P 1 , P 2 ) + e(Q 1 , Q 2 ).
Thus,

2|κ(P 1 , Q 1 ) -κ(P 2 , Q 2 )| ≤ max{e(P 2 , P 1 ) + e(Q 2 , Q 1 ), e(P 1 , P 2 ) + e(Q 1 , Q 2 )}
≤ max{e(P 2 , P 1 ), e(P 1 , P 2 )} δ(P 1 ,P 2 )

+ max{e(Q 2 , Q 1 ), e(Q 1 , Q 2 )} δ(Q 1 ,Q 2 )
. This leads to (3.23). Next we observe that

Θ(P, Q) = arccos 1 -(1/2)[diam(P, Q)] 2 , (3.24)
where diam(P,

Q) := max u∈P ∩S X , v∈Q∩S X u -v .
It is not difficult to check that

|diam(P 1 , Q 1 ) -diam(P 2 , Q 2 )| ≤ δ(P 1 , P 2 ) + δ(Q 1 , Q 2 ) ≤ 2 ∆((P 1 , Q 1 ), (P 2 , Q 2 )). (3.25)
The Lipschitzness of Θ is obtained by combining (3.22), (3.23), (3.24), and (3.25). To see this, one can follow the same procedure as in [17,Theorem 2]. The details are omitted.

Critical angles in a pair of linear subspaces

Which is the minimal angle between a pair of linear subspaces? And which one is the maximal angle? Are they other interesting angles, besides the minimal and the maximal one? This sort of questions has lead to develop the classical theory of principal angles. Recall that the principal angles θ 1 , . . . , θ m of a pair (P, Q) of nontrivial linear subspaces of X are defined recursively by

cos θ k = max u∈P k ∩S X , v∈Q k ∩S X u, v , (3.26)
where m := min{dimP, dimQ} and

         P 1 := P, Q 1 := Q, P k+1 := {x ∈ P k : u k , x = 0}, Q k+1 := {x ∈ Q k : v k , x = 0}, (u k , v k ) solution to (3.26).
The vectors u k and v k are not uniquely defined, but the θ k are unique. Interesting material on principal angles can be found in the linear algebra book by Meyer [12, Section 5.15], see also the references [3,13,16]. When P and Q are nontrivial linear subspaces of X, the system (3.4) becomes

         u ∈ P ∩ S X , v ∈ Q ∩ S X , v -u, v u ∈ P ⊥ , u -u, v v ∈ Q ⊥ , (3.27)
where ⊥ indicates orthogonal complementation relative to X. In this special context, there is no distinction between criticality for angle maximization and criticality for angle minimization. As a first elementary observation, we mention the following conjugacy principle.

Proposition 3.17. Let P and Q be nontrivial linear subspaces of X. Let θ, ψ ∈ [0, π] be conjugate angles. Then θ is a critical angle of (P, Q) if and only if ψ is a critical angle of (P, Q).

Proof. Clearly, (u, v) satisfies (3.27) if and only if (u, -v) satisfies (3.27). It suffices now to observe that arccos u, -v and arccos u, v are conjugate angles.

By the way, the combination of Corollary 3.6 and Proposition 3.17 yields a duality result established by Miao and Ben-Israel [13,Theorem 3]. In view of Proposition 3.17, it is enough to compute the critical angles of (P, Q) that are in the subinterval [0, π/2]. The remaining critical angles are obtained by conjugation. The next theorem shows that the principal angles of (P, Q) are equal to the critical angles of (P, Q) that are in [0, π/2]. In what follows, we use the notation

O(R n , X) := {W ∈ L(R n , X) : W T W = I n },
where I n is the identity matrix of order n and L(R n , X) is the vector space of linear maps from R n to X. The symbol ImW refers to the image space of W .

Theorem 3.18. Let P = Im U and Q = ImV be nontrivial linear subspaces of X represented by U ∈ O(R p , X) and V ∈ O(R q , X), respectively. For θ ∈ [0, π/2], the following four conditions are equivalent:

(a) θ is a critical angle of (P, Q).

(b) θ is a principal angle of (P, Q).

(c) cos θ is a singular value of the rectangular matrix E := V T U .

(d) There are unit vectors x ∈ R p and y ∈ R q such that

0 E T E 0 x y = cos θ x y . (3.28)
Furthermore, if x and y are as in (d), then (U x, V y) is a critical pair of (P, Q) and cos θ = U x, V y .

Proof. (b) ⇔ (c). This equivalence is stated in [3, Theorem 1]. (a) ⇒ (d).
Let the angle θ be formed with some pair (u, v) satisfying the system (3.27). There are unit vectors x ∈ R p and y ∈ R q such that (u, v) = (U x, V y). Hence,

cos θ = u, v = U x, V y and V y -(cos θ)U x ∈ P ⊥ , U x -(cos θ)V y ∈ Q ⊥ .
Since P ⊥ = Ker(U T ) and Q ⊥ = Ker(V T ), one gets

E T y = (cos θ)x, Ex = (cos θ)y. (3.29)
which is an equivalent way of writing (3.28).

(d) ⇒ (c). By exchanging the roles of P and Q if necessary, one may suppose that min{p, q} = p. Let x and y be as in (d). From (3.29), one gets E T Ex = (cos θ) 2 x. Hence, (cos θ) 2 is an eigenvalue of E T E and cos θ is a singular value of E.

(c) ⇒ (a). One can write E = F ΣG T , where G = [g 1 . . . g p ] and F = [f 1 . . . f q ] are orthogonal matrices of order p and q, respectively, and Σ is a q × p diagonal matrix with the singular values of E placed on the diagonal entries. Let cos θ be a singular value of E. Suppose that cos θ is placed on k-th diagonal entry of Σ. One gets Eg k = (cos θ)f k and E T f k = (cos θ)g k . Hence, the system (3.28) holds with x = g k and y = f k . One deduces that (u, v) = (U g k , V f k ) is a critical pair of (P, Q) producing the angle θ.

Let P and Q be as in Theorem 3.18. By combining Theorem 3.18 and Proposition 3.17, one obtains

Γ(P, Q) = σ∈Σ(E) {arccos σ, π -arccos σ},
where Σ(E) is the set of singular values of E. In particular, the critical angles of (P, Q) are at most 2 min{p, q} and they come in conjugate pairs. Such upper bound can be sharpened as follows.

Proposition 3.19. Let P and Q be nontrivial linear subspaces of X of dimensions p and q, respectively. Let r be the dimension of P ∩ Q. Then card [Γ(P, Q)] ≤ 2 min {p, q} -2 max{0, r -1}.

(3.30)

Proof. We assume that 1 ≤ r < min {p, q}, otherwise we are done. One can represent P and Q as in Theorem 3.18, with the additional feature that U = [W, U 0 ] and V = [W, V 0 ] have a portion in common. The common part W ∈ O(R r , X) serves to represent the intersection of P and Q, i.e., P ∩ Q = ImW . One has

W T W = I r , U T 0 U 0 = I p-r , V T 0 V 0 = I q-r , W T U 0 = 0, U T 0 W = 0, W T V 0 = 0, V T 0 W = 0,
Let the angle θ be formed with some pair (u, v) satisfying the system (3.27). There are vectors ξ, η ∈ R r and x ∈ R p-r , y ∈ R q-r such that ξ 2 + x 2 = 1, η 2 + y 2 = 1, and

(u, v) = (W ξ + U 0 x, W η + V 0 y).
(3.31)

By substituting (3.31) into (3.27), one gets

         W T [W η + V 0 y -λ(W ξ + U 0 x)] = 0, U T 0 [W η + V 0 y -λ(W ξ + U 0 x)] = 0, W T [W ξ + U 0 x -λ(W η + V 0 y)] = 0, V T 0 [W ξ + U 0 x -λ(W η + V 0 y)] = 0, with λ = W ξ + U 0 x, W η + V 0 y .
After simplification, one obtains η = λξ, ξ = λη, and

U T 0 V 0 y = λx, V T 0 U 0 x = λy.
(3.32)

If λ / ∈ {-1, 1}, then ξ = 0, η = 0 and x ∈ R p-q , y ∈ R q-r are unit vectors satisfying (3.32). Hence, λ may take at most 2 min{pr, q -r} different values. To this count one should add the potential candidates λ = -1 and λ = 1. One gets in this way the upper estimate

card [Γ(P, Q)] ≤ 2 min{p -r, q -r} + 2.
This proves (3.30).

Critical angles in a pair of polyhedral cones

This section is devoted to the analysis of critical angles in a pair (P, Q) of polyhedral cones. We suppose that the reader is acquainted with the theory of faces of convex polyhedra. The notation that we use is as follows: F(P ) := {F ⊆ X : F is a nonzero face of P }, spanF := linear subspace spanned by F, riF := relative interior of F, dimF := dimension of spanF, Π F := orthogonal projector onto spanF.

For a nonzero vector u in a polyhedral cone P ∈ C(X), there exists a unique F ∈ F(P ) such that u ∈ riF . Such F is called the face associated to u.

Theorem 3.20. Let P, Q ∈ C(X) be polyhedral cones. If (u, v) is a critical pair of (P, Q), then

Π F v = u, v u, Π E u = u, v v, (3.33)
where F is the face of P associated to u and E is the face of Q associated to v. In particular,

Γ(P, Q) ⊆ F ∈F (P ) E∈F (Q) Γ(spanF, spanE). (3.34) Proof.
By assumption, u ∈ riF and v ∈ riE satisfy the criticality conditions stated in (3.4). By proceeding as [18,Theorem 3.4], one can check that

v -u, v u ∈ (spanF ) ⊥ , u -u, v v ∈ (spanE) ⊥ .
But this is clearly equivalent to (3.33).

By using the inclusion (3.34), one gets the upper bound Proof. Suppose that u 1 and u 2 have F ∈ F(P ) as common associated face. In such a case, Theorem 3.20 yields

card[Γ(P, Q)] ≤ F ∈F (P ) E∈F (Q) card[Γ(spanF, spanE)]. ( 3
u 1 , v u 1 = Π F v = u 2 , v u 2 .
By taking norms, one sees that u 1 , v and u 2 , v have the same absolute value. This proves that θ 1 and θ 2 are equal or conjugate.

We now concentrate on the numerical computation of the critical angles of a pair

(P, Q) = (G(R p + ), H(R q + )) (3.37) of polyhedral cones in R n .
Here, G = [g 1 , . . . , g p ] and H = [h 1 , . . . , h q ] are matrices of size n × p and n × q, respectively. Without loss of generality, we assume that g 1 , . . . , g p are conically independent unit vectors, h 1 , . . . , h q are conically independent unit vectors.

∈ R |I| , η ∈ R |J| such that 0 G T I H J H T J G I 0 ξ η = cos θ G T I G I 0 0 H T J H J ξ η , (3.39) g k , H J η -(cos θ)G I ξ ≥ 0 for all k / ∈ I, (3.40) h ℓ , G I ξ -(cos θ)H J η ≥ 0 for all ℓ / ∈ J, (3.41) ξ, G T I G I ξ = 1, ξ ∈ int(R |I| + ), (3.42) η, H T J H J η = 1, η ∈ int(R |J| + ). (3.43)
Furthermore, when these equivalent statements hold, the critical angle θ is formed with the critical pair (u, v) = (G I ξ, H J η).

Proof. We follow similar steps as in [9, Theorem 3], except that now the polyhedral cones P and Q are not necessarily equal. Besides, we do not restrict the attention to proper critical angles. For the sake of completeness, we give a sketch of the proof:

H J η -λG I ξ ∈ P * , G I ξ -λH J η ∈ Q * ,
or, equivalently, g k , H J η -λG I ξ ≥ 0 for all k = 1, . . . , p, h ℓ , G I ξ -λH J η ≥ 0 for all ℓ = 1, . . . , q.

This yields (3.40) and (3.41). Furthermore, since

0 = u, v -λu = ξ, G T I H J η -λG T I G I ξ , 0 = v, u -λv = η, H T J G I ξ -λH T J H J η , one gets G T I H J η -λG T I G I ξ = 0, H T J G I ξ -λH T J H J η = 0, which is nothing but (3.39). (b) ⇒ (a). If one sets (u, v) := (G I ξ, H J η), then one can check that (u, v) is a critical pair of (P, Q) with cos θ = u, v .
The index sets I, J and the vectors ξ, η in Theorem 3.22(b) are not necessarily unique. Anyway, one can write

Γ(P, Q) = I∈I(G) J∈J (H) Γ I,J (P, Q),
where Γ I,J (P, Q) captures the critical angles produced by (I, J), that is,

Γ I,J (P, Q) := {arccos G I ξ, H J η : (ξ, η) as in (3.39)-(3.43)}.
One refers to (I, J) as a successful configuration of index sets if Γ I,J (P, Q) is nonempty. For each pair (I, J), we construct Γ I,J (P, Q) by using the following algorithm:

-Step 1: Solve the generalized eigenvalue problem A I,J z = λ B I,J z, where

A I,J := 0 G T I H J H T J G I 0 , B I,J := G T I G I 0 0 H T J H J , z := ξ η .
-Step 2: Declare "acceptable" each eigenvalue that admits an associated eigenvector satisfying the conditions (3.40)- (3.43), where one identifies λ with cos θ. Take the arccosinus of each acceptable eigenvalue and put it in the set Γ I,J (P, Q).

Example 3.23. By way of example, consider the nonnegative orthant P = R n + and the Schur cone

Q = x ∈ R n : k i=1 x i ≥ 0 for k ∈ {1, . . . , n -1} and x 1 + . . . + x n = 0 .
In this case, G = I n and H is formed with the n-dimensional vectors

h 1 = 1 √ 2        1 -1 0 . . . 0        , . . . , h n-1 = 1 √ 2        0 . . . 0 1 -1        .
Table 3.1 concerns the particular case n = 5. It displays the successful configurations (I, J) and the critical angles produced by each one of these configurations. As one can see from Table 3.1, different configurations (I, J) may produce the same critical angle. There are 465 configurations (I, J) in all, but only 12 are successful.

I J cos θ θ {2, 3, 4, 5} {1, 2, 3, 4} -1/ √ 5 0.6476 π {2, 3, 4} {1, 2, 3} -1/2 0.6667 π {2, 3} {1, 2} -1/ √ 3 0.6959 π {2, 4, 5} {1, 2, 3, 4} - √ 2/ √ 5 0.7180 π {3, 4, 5} {1, 2, 3, 4} - √ 2/ √ 5 0.7180 π {2} {1} -1/ √ 2 0.7500 π {3, 4} {1, 2, 3} -1/ √ 2 0.7500 π {3, 5} {1, 2, 3, 4} - √ 3/ √ 5 0.7820 π {4, 5} {1, 2, 3, 4} - √ 3/ √ 5 0.7820 π {3} {1, 2} - √ 2/ √ 3 0.8041 π {4} {1, 2, 3} - √ 3/2 0.8333 π {5} {1, 2, 3, 4} -2/ √ 5 0.8524 π
Table 3.1: Critical angles between the nonnegative orthant and the Schur cone in R 5 .

Remark 3.24. It is not surprising that all the critical angles reported in Table 3.1 are obtuse. This corresponds to a general fact concerning critical angles between nonnegative orthants and Schur cones.

Uniform cardinality estimates for angular spectra

Let M n (p, q) denote the collection of all pairs (P, Q) as in (3.37)-(3.38). Theorem 3.22 yield the following uniform cardinality estimate.

Proposition 3.25. Fix the dimension n. The term c n (p, q) := max

(P,Q)∈Mn(p,q) card[Γ(P, Q)]
is majorized by a bivariate polynomial, of degree at most 2n, in the variables p and q. In particular, c n (p, q) grows at most polynomially in each argument separately.

Proof. The generalized eigenvalue problem (3.39) has at most |I| + |J| eigenvalues. If one defines

C p k := p! k!(p-k)! if k ≤ p, 0 if k > p, ( 3
C p k C q ℓ (k + ℓ)
for all (P, Q) ∈ M n (p, q). One gets in this way

c n (p, q) ≤ n k=1 kC p k n ℓ=1 C q ℓ + n ℓ=1 ℓC q ℓ n k=1 C p k . (3.45)
Note that each sum between parentheses defines a polynomial of degree at most n, either in the variable p or in the variable q. The term on the right-hand side of (3.45) is then a bivariate polynomial, of degree at most 2n, with respect to (p, q).

The term on the right-hand side of (3.45) is a rather coarse upper bound for c n (p, q). Lower bounds for c n (p, q) can be obtained experimentally by counting critical angles in randomly generated pairs of polyhedral cones. For each choice of (p, q), the lower bound displayed in Table 3.2 was obtained by working with a sample of 10 4 randomly generated pairs of polyhedral cones. The columns of G and the columns of H are random vectors uniformly distributed on the nonnegative orthant intersected with the unit sphere of R n . For instance, when q = p = n = 4, one can find a pair (P, Q) with as much as 41 critical angles. Experimentally, we found the pair (P, Q) described by the matrices

p = n = 3 p = n = 4 p = n = 5 p = n = 6 q=1 7

A polyhedral cone versus a ray

We now search for critical angles between a polyhedral cone P and a ray R + v := {tv : t ≥ 0} generated by some unit vector v ∈ R n . By adapting Theorem 3.22 to this special setting, one gets the following result. Proposition 3.26. Let P be as in (3.37)-(3.38) and v be a unit vector in R n . Then, θ ∈ Γ(P, R + v) if and only if there are an index set I ∈ I(G) and a vector ξ ∈ R |I| such that

(cos θ)ξ = (G T I G I ) -1 G T I v, (3.46)
g k , v -(cos θ)G I ξ ≥ 0 for all k / ∈ I, ξ, G T I G I ξ = 1, ξ ∈ int(R |I| + )
Furthermore, the critical pairs of (P, R + v) are exactly those of the form (G I ξ, v), with I and ξ as above.

Proof. The conditions (3.41) and (3.43) are here superfluous. The generalized eigenvalue problem (3.39) becomes

0 G T I v v T G I 0 ξ 1 = cos θ G T I G I 0 0 1 ξ 1 ,
but this is equivalent to (3.46).

The next corollary shows that, for each I ∈ I(G), the set Γ I (P, R + v) is empty or a singleton. The proof of such result is omitted, because it follows straightforwardly from Proposition 3.26.

Corollary 3.27. Let P be as in (3.37)-(3.38) and v be a unit vector in R n . For each I ∈ I(G), consider the condition

g k , v -v I ≥ 0 for all k / ∈ I, (3.47)
where v I := G I (G T I G I ) -1 G T I v is the orthogonal projection of v onto ImG I . Then Γ I (P, R + v) =        {π/2} if G T I v = 0 and (3.47) holds, arccos v I if (G T I G I ) -1 G T I v ∈ int(R |I| + ) and (3.47) holds, π -arccos v I if -(G T I G I ) -1 G T I v ∈ int(R |I| +
) and (3.47) holds, ∅ otherwise.

Since each index set I ∈ I(G) produces at most one critical angle, one gets the upper bound

card[Γ(P, R + v)] ≤ n k=1 C p k , (3.48)
where C p k is given by (3.44). The sum on the right-hand side of (3.48) is a polynomial, of degree at most n, in the variable p. By combining the bound (3.48) and the row q = 1 of Table 3.2, one sees that c n (n, 1) = 2 n -1, at least when n ∈ {3, 4, 5, 6}. In practice, the cardinality of Γ(P, R + v) is highly dependent on the orientation of v with respect to the cone P . Consider the random variable

x := card[Γ(P, R + v)],
where v and the columns of G are random vectors uniformly distributed on the unit sphere of R n . Table 3 Appendix4

Action of invertible linear transformations on angular spectra

What happens with Θ(P, Q) if the cones P, Q ∈ C(X) are subject to a common invertible linear transformation? Consistently with geometric intuition, one has

Γ (A(P ), A(Q)) = Γ(P, Q), Θ (A(P ), A(Q)) = Θ(P, Q)
for any orthogonal linear map A : X → X. The above formulas are a particular instance of the next proposition. In what follows, L(X) denotes the vector space of linear endomorphisms on X and GL(X) is the set of invertible linear endomorphisms on X. The superscript " T " stands for transposition or adjunction.

Proposition 3.28. Let P, Q ∈ C(X). Let A, B ∈ GL(X) be such that A T A = B T B. Then

Γ (A(P ), A(Q)) = Γ (B(P ), B(Q)) , Θ (A(P ), A(Q)) = Θ (B(P ), B(Q)) .
Proof. Let θ ∈ Γ (A(P ), A(Q)) and λ := cos θ. There are vectors ξ ∈ P and

η ∈ Q such that        λ = Aξ, Aη , Aξ = 1, Aη = 1, Aη -λAξ ∈ [A(P )] * , Aξ -λAη ∈ [A(Q)] * .
(3.49)

The above system can be written in the equivalent form

       λ = ξ, A T Aη , ξ, A T Aξ = 1, η, A T Aη = 1, A T Aη -λA T Aξ ∈ P * , A T Aξ -λA T Aη ∈ Q * .
But A T A can be changed by B T B. Hence, (3.49) can be written with B in the place of A. This proves that θ ∈ Γ (B(P ), B(Q)) .

With the help of a suitable non-orthogonal transformation A ∈ GL(X), it is possible to increase (cf. Theorem 3.30) or decrease (cf. Theorem 3.32) arbitrarily the maximal angle of a given pair (P, Q). Before proving this fact, we state a useful lemma.

Lemma 3.29. Let (u, v) ∈ Ω X and ϑ ∈]0, π[. Then Bu = 1, Bv = 1, Bu, Bv = cos ϑ (3.50)
for some self-adjoint positive definite B ∈ L(X).

Proof. Let n := dimX. The subspace L := span{u, v} has dimension 2. Let λ := u, v and

e 1 := (1 -λ 2 ) -1/2 (u -λv), e 2 := v.
Let {e 3 , . . . , e n } be an orthonormal basis of the orthogonal complement of L. Let G ∈ L(X) be given by

Gx := a, x e 1 + b, x e 2 + n k=3 e k , x e k ,
where a, b ∈ L are not collinear. Such a map G is clearly invertible. The particular choice

a = (1 -λ 2 ) -1/2 (sin θ)e 1 , b = (1 -λ 2 ) -1/2 (cos θ -λ)e 1 + e 2
yields Gu = (sin ϑ)e 1 + (cos ϑ)e 2 , Gv = e 2 , and Gu, Gv = cos ϑ. Since G satisfies the conditions stipulated in (3.50), so does the self-adjoint positive definite linear map B :=

G T G 1/2 .
Theorem 3.30. Let P, Q ∈ C(X) and θ be such that 0 < Θ(P, Q) < θ < π. Then

Θ (A(P ), A(Q)) = θ (3.51)
for some A ∈ GL(X).

Proof. Let u ∈ P ∩ S X and v ∈ Q ∩ S X be non-collinear. Take any ϑ ∈]θ, π[ and construct B as in Lemma 3.29. There exists a continuous function

A : [0, 1] → L(X) such that A(0) = I X , A (1)
= B, and A(t) ∈ GL(X) for all t ∈ [0, 1]. To see this, just consider the obvious choice

A(t) := (1 -t)I X + tB. (3.52)
The real-valued function

t ∈ [0, 1] → f (t) := Θ (A(t)(P ), A(t)(Q)) (3.53) is continuous, because Θ : C 2 (X) → R is continuous and t → (A(t)(P ), A(t)(Q)) is continuous as function from [0, 1] to C 2 (X).
On the other hand, f (0) = Θ(P, Q) and

f (1) = Θ (B(P ), B(Q)) ≥ arccos Bu, Bv = ϑ.
The Intermediate Value Theorem ensures the existence of t * ∈ [0, 1] such that f (t * ) = θ. Hence, (3.51) holds with A = A(t * ).

We now explain how to construct a non-orthogonal transformation A ∈ GL(X) that decreases arbitrarily the maximal angle of a pair (P, Q). Again, a preliminary lemma is in order. Lemma 3.31. Let K ∈ C(X) be such that 0 < θ(K) < π. Then, for all ψ ∈]0, π[, there exists A ∈ GL(X) such that θ max (A(K)) = ψ.

Proof. When ψ = θ max (K), one takes A = I X . When ψ > θ max (K), one applies Theorem 3.30 with P = Q = K. Suppose now that ψ < θ max (K). Pick any ϑ such that 0 < ϑ < min{ψ, π/2}. Let n := dimX. The assumption θ max (K) < π implies that K * contains a basis {f 1 , . . . , f n } of X. Hence,

K ⊆ S := {x ∈ X : f 1 , x ≥ 0, . . . , f n , x ≥ 0}.
Note that S is a simplicial cone in X. It can be represented in the form

S = G R n + = n i=1 ξ i g i : ξ ∈ R n + ,
where {g 1 , . . . , g n } is another basis of X and G : R n → X is given by Gξ := n i=1 ξ i g i . Consider a matrix C = [c 1 , . . . , c n ] of order n whose columns are linearly independent unit vectors satisfying c i , c j ≥ cos ϑ for all i = j.

Thanks to [6, Proposition 6.2], one has θ max C(R n + ) ≤ ϑ. Let H : X → R n be the linear map given by Hx := CG -1 x. Since

H(K) ⊆ H(S) = C R n + ,
one gets θ max (H(K)) ≤ ϑ. Proposition 3.28 yields θ max (B(K)) ≤ ϑ with B := (H T H) 1/2 . Next, one considers A given by (3.52) and applies the Intermediate Value Theorem to f (t

) := θ max (A(t)(K)) . Since f (0) = θ max (K) and f (1) ≤ ϑ, there exists t * ∈ [0, 1] such that θ max (A(t * )(K)) = ψ.
Theorem 3.32. Let P, Q ∈ C(X) and θ be such that 0 < θ < Θ(P, Q) < π. In addition, suppose that P and Q are pointed separately. Then there exists A ∈ GL(X) such that

Θ (A(P ), A(Q)) = θ.
Proof. Pick any ϑ ∈]0, θ[. Under the hypotheses of the theorem, the convex cone

K := P + Q is closed, pointed,

Bibliography

Chapter 4

Critical angles between two convex cones II. Special cases Alberto Seeger 1 and David Sossa 2

Abstract. The concept of critical angle between two linear subspaces has applications in statistics, numerical linear algebra, and other areas. Such concept has been abundantly studied in the literature. Part I of this work is an attempt to build up a theory of critical angles for a pair of closed convex cones. Part II focusses on the practical computation of the maximal angle between specially structured cones.

Mathematics Subject Classification: 15A18, 15A48, 52A40, 90C26, 90C33. Key words: Maximal angle, critical angle, convex cones, topheavy cones, ellipsoidal cones, cones of matrices.

Introduction

Let (X, •, • ) be a Euclidian space of dimension at least two and let C(X) be the set of nontrivial closed convex cones in X. That a closed convex cone is nontrivial means that it is different from the zero cone and different from the whole space. The maximal angle of a pair (P, Q) of nontrivial closed convex cones in X is defined by

Θ(P, Q) := max u∈P ∩S X , v∈Q∩S X arccos u, v , (4.1)
where S X stands for the unit sphere of X. A pair (u, v) ∈ X 2 solving the angle maximization problem (4.1) is called an antipodal pair of (P, Q). Antipodal pairs always exist, but they are not unique in general. A necessary condition for (u, v) to be an antipodal pair of (P, Q)

is that          u ∈ P ∩ S X , v ∈ Q ∩ S X , v -u, v u ∈ P * , u -u, v v ∈ Q * , (4.2)
where P * and Q * are the positive dual cones of P and Q, respectively. If the system (4.2) holds, then (u, v) is called a critical pair of (P, Q) and arccos u, v is called a critical angle of (P, Q). The adjective proper is added to a critical pair (u, v) and the corresponding critical angle if u and v are not collinear. One refers to the set

Γ(P, Q) := {arccos u, v : (u, v) satisfies (4.2)}
as the angular spectrum of (P, Q). Angular spectra have usually a finite cardinality, but not always.

In a similar way one can treat the angle minimization problem

Ψ(P, Q) := min u∈P ∩S X , v∈Q∩S X arccos u, v . (4.3)
Angle minimization problems like (4.3) arise in a number of applications, for instance in the theory of exponential dichotomies for linear ODEs (cf. [5]) and in regression analysis of ordinal data (cf. [9]). One readily sees that

cos[Ψ(P, Q)] = -cos[Θ(P, -Q)], Ψ(P, Q) = π -Θ(P, -Q). (4.4)
So, there is no loss of generality in focussing the attention just on angle maximization.

Part I of this work (cf. [8]) establishes various geometric and analytic results concerning antipodality, criticality, and angular spectra. The present paper focusses on the computation of the maximal angle between specially structured cones. The organization of the paper is as follows.

-Section 4.2 discusses the case in which P and Q are revolution cones. We give explicit formulas for computing all the critical angles.

-Section 4.3 discusses the case in which P and Q are topheavy cones. The class of topheavy cones is quite large and include in particular the ℓ p -cones and the ellipsoidal cones.

-Section 4.4 concerns the computation of the maximal angle between two cones of matrices. A large portion of this section is devoted to a difficult question arising in numerical linear algebra: how large can be the angle between a positive semidefinite symmetric matrix and a symmetric matrix that is nonnegative entrywise?

Preliminary material

A critical pair of (P, Q) may not solve the angle maximization problem (4.1). For instance, if we take P = R + u and Q = P * , with u ∈ S X , then (u, u) is a critical pair of (P, Q) but it does not solve the problem (4.1) (cf. Proposition 4.2). However, each component of a critical pair is a solution to a certain optimization problem. The details are explained below.

Proposition 4.1. Let P, Q ∈ C(X). Then (u, v) is a critical pair of (P, Q) if and only if

u minimizes •, v -u, v u on P ∩ S X , v minimizes u -u, v v, • on Q ∩ S X . (4.5)
Proof. The proof is immediate. The key observation is that u is orthogonal to vu, v u and that v is orthogonal to uu, v v.

There are many alternative characterizations of criticality. The characterization (4.5) will be used later in a number of occasions. Beware that (4.5) is a weaker than

u minimizes •, v on P ∩ S X , v minimizes u, • on Q ∩ S X . (4.6)
A pair (u, v) as in (4.6) is said to be a Nash antipodal pair of (P, Q). Nash antipodality is a property that lies between criticality and antipodality.

The following easy result is recorded just for convenience. It concerns the maximal angle between a convex cone and its dual.

Proposition 4.2. Let K ∈ C(X). Then Θ(K, K * ) = π/2. Proof. Since u, v ≥ 0 for all u ∈ K and v ∈ K * , it is clear that Θ(K, K * ) ≤ π/2. (4.7)
Since K ∪ -K * is not the whole space X, there exists a nonzero vector z / ∈ K ∪ -K * . Let Π K (z) denote the projection of z onto K. Moreau's orthogonal decomposition theorem implies that Π K (z) and Π K * (-z) are nonzero orthogonal vectors. Hence,

u := Π K (z) Π K (z) ∈ K, v := Π * K (-z) Π * K (-z) ∈ K *
are orthogonal unit vectors. This proves that (4.7) is in fact an equality.

Γ(P, Q) =        {0, α 1 , π} if α 1 ≥ 0, α 2 ≥ π, {0, α 1 , α 2 } if α 1 ≥ 0, α 2 < π, {π} if α 1 < 0, α 2 ≥ π, {α 2 } if α 1 < 0, α 2 < π, (4.8)
where

α 1 := φ 1 + φ 2 -arccos b 1 , b 2 , α 2 := φ 1 + φ 2 + arccos b 1 , b 2 .
Proof. If X is a two dimensional space, then (4.8) is obtained by arguments of planar geometry. Suppose that X is of dimension at least three. The improper critical angles of (P, Q) are easy to identify. Indeed,

0 ∈ Γ(P, Q) ⇔ P ∩ Q = {0} ⇔ α 1 ≥ 0, π ∈ Γ(P, Q) ⇔ P ∩ -Q = {0} ⇔ α 2 ≥ π.
So, one just needs to detect the proper critical angles of (P, Q). We claim that if (u, v) is a proper critical pair of (P, Q), then L := span{u, v} contains b 1 and b 2 . (4.9)

This claim will be shown in a moment. As a consequence of (4.9), one gets the following planar reduction principle:

(u, v) is a proper critical pair of (P, Q) if and only if (u, v) is a proper critical pair of (P ∩ L, Q ∩ L),

where

P ∩ L := {x ∈ L : b 1 , x ≥ x cos φ 1 }, Q ∩ L := {x ∈ L : b 2 , x ≥ x cos φ 2 },
are viewed as revolution cones in the two dimensional space L. In other words, one is back to a planar setting. We now prove (4.9). Consider a proper critical pair (u, v) of (P, Q) and set λ := u, v . We distinguish between two cases: Case 1: φ

v -λu = γ 1 b 1 + µ 1 u, (4.12
)

u -λv = γ 2 b 2 + µ 2 v. (4.13)
The multiplication of (4.12) by u and (4.13) by v yields

µ 1 + γ 1 cos φ 1 = 0, µ 2 + γ 2 cos φ 2 = 0,
respectively. Hence,

(γ 1 cos φ 1 -λ)u + v = γ 1 b 1 , u + (γ 2 cos φ 2 -λ)v = γ 2 b 2 . (4.14)
Observe that γ 1 = 0 and γ 2 = 0, because (u, v) is proper. This proves that b 1 , b 2 ∈ L.

2 + φ 1 + φ 2 }, (4.15)
Ψ(P, Q) := max{0, arccos b 1 , b 2 -φ 1 -φ 2 }. (4.16)
Proof. Formula (4.15) is a direct consequence of Theorem 4.3. Formula (4.16) is obtained by combining (4.4) and (4.15).

Maximal angle between two topheavy cones

A topheavy cone in R n+1 is a closed convex cone of the form

epif := {(ξ, t) ∈ R n+1 : f (ξ) ≤ t},
where f is a norm on R n . Topheavy cones are pointed, have nonempty interior, and enjoy some remarkable properties that make them particularly appealing in many applications.

Topheavy cones have been studied under various points of view in the literature, see for instance [1,4,7]. The next proposition explains how to compute the maximal angle between two topheavy cones.

Proposition 4.5. Let f and g be norms on R n . Then cos [Θ(epif, epi g)] is equal to the optimal value of the minimization problem

   minimize ξ ⊙ η ξ 2 + [f (ξ)] 2 = 1 η 2 + [g(η)] 2 = 1, (4.17)
where ⊙ stands for the "product" operation given by

ξ ⊙ η := ξ, η + [1 -ξ 2 ] 1/2 [1 -η 2 ] 1/2 .
Proof. The cones epif and epi g have nonempty interior. The first and second components of an antipodal pair must be sough on the boundary of epif and on the boundary of epi g, respectively. Hence, cos[Θ(epif, epi g)] is equal to the optimal value of the minimization problem

           minimize ξ, η + ts f (ξ) = t, g(η) = s, ξ 2 + t 2 = 1, η 2 + s 2 = 1.
It suffices now to get rid of the variables t and s.

In order to derive an explicit solution to the problem (4.17), one needs of course a bit more information on the norms f and g. The following definition proves to be useful. Definition 4.6. Two norms f, g on R n are lower correlated if the minimization problems

α f := min{f (x) : x = 1}, (4.18)
α g := min{g(x) : x = 1}, (4.19)
have a solution in common.

For instance, a positive multiple of • is lower correlated to any norm on R n . Without further ado we state: Theorem 4.7. Let f, g be lower correlated norms on R n . Then

Θ(epif, epi g) = arccos α f [1 + α 2 f ] 1/2 + arccos α g [1 + α 2 g ] 1/2 .
(4.20)

The above maximal angle is attained for instance with the unit vectors

(ξ 0 , t 0 ) := w [1 + α 2 f ] 1/2 , α f [1 + α 2 f ] 1/2 ∈ epif, (η 0 , s 0 ) := -w [1 + α 2 g ] 1/2 , α g [1 + α 2 g ] 1/2 ∈ epig,
where w is any vector taken from the set S(f, g) := argmin x =1 f (x) argmin x =1 g(x) .

Proof. Let w ∈ S(f, g). Since w is a solution to (4.18) and -w is a solution to (4.19), the vectors

ξ 0 := w [1 + α 2 f ] 1/2 , η 0 := -w [1 + α 2 g ] 1/2 solve respectively γ f := max{ ξ : ξ 2 + [f (ξ)] 2 = 1}, γ g := max{ η : η 2 + [g(η)] 2 = 1}.
Let (ξ, η) be any pair satisfying the equality constraints in (4.17). Then

ξ ≤ ξ 0 = γ f = (1 + α 2 f ) -1/2 , η ≤ η 0 = γ g = (1 + α 2 g ) -1/2 , and ξ -1 ξ, η -1 η ≥ ξ 0 -1 ξ 0 , η 0 -1 η 0 = -1.
Hence,

ξ ⊙ η ≥ ξ 0 ⊙ η 0 = -[1 + α 2 f ] -1/2 [1 + α 2 g ] -1/2 + [1 -γ 2 f ] 1/2 [1 -γ 2 g ] 1/2 .
In other words, (ξ 0 , η 0 ) solves (4.17) and

cos [Θ(epif, epi g)] = α f α g -1 [1 + α 2 f ] 1/2 [1 + α 2 g ] 1/2
. The last equality is an equivalent way of writing (4.20).

Remark 4.8. In view of [7,Theorem 5.2], formula (4.20) can be rewritten as

Θ(epif, epi g) = θ max (epif ) + θ max (epi g) 2 , (4.21)
where θ max (K) denotes the maximal angle of K ∈ C(X). Formula (4.21) is consistent with geometric intuition, but one must remember that f and g are assumed to be lower correlated. Indeed, formula (4.21) may fail if one drops the lower correlation assumption.

As particular example of topheavy cone, one may consider the ℓ p -cone

L p := {(ξ, t) ∈ R n+1 : ξ p ≤ t}.
Here, p ∈ [1, ∞] and • p stands for the ℓ p -norm in R n . Of special interest are the cases p = 1, p = 2, and p = ∞. One gets

Θ(L 1 , L 1 ) = π/2, Θ(L 2 , L 2 ) = π/2, Θ(L 1 , L 2 ) = π/2, Θ(L 1 , L ∞ ) = π/2, Θ(L ∞ , L ∞ ) = 2 arccos [1 + n] -1/2 , Θ(L 2 , L ∞ ) = arccos [1 + n] -1/2 + π/4.
These formulas are obtained by using the proposition stated below.

Proposition 4.9. The following statements holds:

(a) Let p, q ∈ [2, ∞]. Then Θ(L p , L q ) = arccos 1 + n (p-2)/p -1/2 + arccos 1 + n (q-2)/q -1/2 .

(b) Let p ∈ [1, ∞] and q ∈ [1, p * ], where p * is given by p -1 + p -1 * = 1. Then

Θ(L p , L q ) = π/2.
Proof. Part (a). If p and q are both in [2, ∞], then the norms f (x) := x p and g(x) := x q are lower correlated. Indeed,

1 n := 1 √ n (1, . . . , 1) T ∈ argmin x =1 x p argmin x =1 x q .
So, it suffices to substitute α f = 1 n p and α g = 1 n q into (4. Of course, in (4.22) one uses the fact that the family {L p } p≥1 is nondecreasing with respect to set inclusion.

Maximal angle between two ellipsoidal cones

An ellipsoidal cone in R n+1 is a closed convex cone of the form

E A := {(ξ, t) ∈ R n+1 : ξ, Aξ ≤ t},
where A is a positive definite symmetric matrix of order n. Hence, an ellipsoidal cone is a particular instance of a topheavy cone. It is easy to see that the norms Furthermore, if the eigenspaces E min (A) and E min (B) have nonzero vector in common, then x, Ax = λ 1 (A).

f (x) = x, Ax , g(x) = x, Bx (4
Θ(E A , E B ) = arccos λ 1 (A) 1 + λ 1 (A) 1/2 + arccos λ 1 (B) 1 + λ 1 (B)
Similarly, α 2 g = λ 1 (B).

An ellipsoidal cone versus a nonnegative orthant

The next proposition gives a formula for computing the maximal angle between an ellipsoidal cone and a nonnegative orthant. We use the notation µ min (C) to indicate the smallest Pareto eigenvalue of a square matrix C (cf. [6]). From the general theory of Pareto eigenvalues one knows that µ min (C) = min Furthermore, ((ξ, t), (η, s)) is an antipodal pair of

(E A , R n+1 + ) if and only if        η is a solution to (4.24), s = 0, ξ = [-η, Cη ] -1/2 Cη, t = 1 + [µ min (C)] -1 Cη 2 .
Proof. The term c := cos[Θ(E A , R n+1

+ )] corresponds to the optimal value of the minimization problem (I n + A) -1/2 η, γ .

           minimize ξ, η + ts ξ, Aξ 1/2 = t, ξ 2 + t 2 = 1, η 2 + s 2 = 1, η ≥ 0, s ≥ 0.
Since the inner minimization problem is solved by

γ = -(I n + A) -1/2 η -1 (I n + A) -1/2 η, one gets -c = max η =1 η≥0 (I n + A) -1/2 η = max η =1 η≥0 η, (I n + A) -1 η 1/2 = -min η =1 η≥0 η, Cη 1/2 = [-µ min (C)] 1/2 .
This completes the proof of the proposition.

An ellipsoidal cone versus a ray

The next proposition explains how to compute the maximal angle between an ellipsoidal cone E A and a ray R + v.

Proposition 4.12. Let A be a positive definite symmetric matrix of order n and v := (η, s) be a unit vector in R n+1 . Then (a) cos[Θ(E A , R + v)] is equal to the optimal value of the nonconvex minimization problem

minimize ξ, η + s[1 -ξ 2 ] 1/2 ξ 2 + ξ, Aξ = 1.
(b) Under the additional assumption η, A -1 η 1/2 > s > 0, one can write

cos[Θ(E A , R + v)] = -s min{ x -b : x, M x ≤ 1}, (4.26)
where b := (1/s)(I n + A) -1/2 η and M := (

I n + A) 1/2 A -1 (I n + A) 1/2 .
Proof. The proof of (a) is as in Proposition 4.5, so we concentrate on (b). For notational convenience, we write

f (ξ) := ξ, Aξ 1/2 = A 1/2 ξ , F (ξ) := ξ, (I n + A)ξ 1/2 = (I n + A) 1/2 ξ .
Note that f and F are norms on R n . Let γ

:= cos[Θ(E A , R + v)]. One has γ = min (ξ,t)∈E A ξ 2 +t 2 =1 { ξ, η + ts} = min f (ξ)= t ξ 2 +t 2 =1 { ξ, η + ts} (4.27) = min F (ξ)=1 { ξ, η + sf (ξ)}, (4.28)
where (4.27) is a consequence of [8,Theorem 2.3]. Since E * A = E A -1 , the condition η, A -1 η 1/2 > s amounts to saying that (η, s) does not belong to dual cone of E A , i.e., there exists a unit vector ( ξ, t) ∈ E A such that ξ, η + ts < 0. Hence, γ < 0 and, by a positive homogeneity argument, the equality constraint in (4.28) can be written as an inequality constraint. In other words, one has γ = min

F (ξ)≤1 { ξ, η + sf (ξ)}. (4.29)
Observe that (4.29) is a convex minimization problem. By using standard rules of convex analysis, one can show that

γ = -s min f • (z) ≤1 F • (z -s -1 η), (4.30)
where

f • (µ) = µ, A -1 µ 1/2 = A -1/2 µ , F • (µ) = µ, (I n + A) -1 µ 1/2 = (I n + A) -1/2 µ
are the polar norms of f and F , respectively. One can view the minimization problem in (4.30) as a dual version of (4.29). In order to complete the proof of (b), it remains to introduce in (4.30) the change of variables x = (I n + A) -1/2 z.

The minimization problem on the right-hand side of (4.26) is about finding the minimal distance from a point to an ellipsoid. The numerical resolution of such a projection problem offers no difficulty.

Critical angles between two cones of matrices

Let the space S n of symmetric matrices of order n be equipped with the trace inner product A, B = tr(AB). This section concerns the analysis of critical angles in a pair of convex cones in S n . We introduce the symbol O n to indicate the set of orthogonal matrices of order n. A nonempty set P in the space S n is said to be orthogonally invariant if

A ∈ P ⇒ U T AU ∈ P for all U ∈ O n .
For instance, the SDP cone S n + := {A ∈ S n : A is positive semidefinite} is orthogonally invariant. Proposition 4.13. Suppose that at least one of the cones P, Q ∈ C(S n ) is orthogonally invariant. Let (A, B) be a critical pair of (P, Q). Then A and B commute, i.e., AB = BA.

Proof. Suppose, for instance, that P is orthogonally invariant. Write λ := A, B . By Proposition 4.1 one knows that A minimizes the linear form B -λA, • on P ⋄ := {X ∈ P : X = 1}.

Since P ⋄ is an orthogonally invariant set, the commutation principle stated in [3, Lemma 4] implies that A(B -λA) = (B -λA)A. This leads to AB = BA.

There is a rich literature devoted to the analysis of orthogonally invariant sets. One knows, for instance, that P ∈ C(S n ) is orthogonally invariant if and only if there exists a permutation invariant cone P ∈ C(R n ) such that

P = λ -1 (P ) := {A ∈ S n : λ(A) ∈ P }. (4.31)
Here and in the sequel, the notation λ(A) stands for the vector of eigenvalues of A arranged in nondecreasing order, i.e., λ 1 (A) ≤ . . . ≤ λ n (A).

The cone P in the representation formula (4.31) is unique and given by

P = {x ∈ R n : Diag(x) ∈ P},
where Diag(x) is the diagonal matrix whose entries on the diagonal are the components of x. One refers to P as the permutation invariant cone associated to P.

Theorem 4.14. Let P, Q ∈ C(S n ) be orthogonally invariant and P, Q ∈ C(R n ) be the associated permutation invariant cones. Then

Γ(P, Q) = Γ(P, Q), Θ(P, Q) = Θ(P, Q).
Furthermore, the following statements are equivalent:

(a) (A, B) is a critical (respectively, antipodal) pair of (P, Q), (b) there exist a critical (respectively, antipodal) pair (u, v) of (P, Q) and a matrix U ∈ O n such that A = U Diag(u)U T and B = U Diag(v)U T .

Proof. The proof follows similar steps as in [3,Theorem 5].

Example 4.15. By way of example, consider the problem of finding the critical angles between SDP cone S n + and the cone

D n := {A ∈ S n : λ n (A) ≤ tr(A)}. n cos θ θ 3 1 0 -1/ √ 3 0.6959π 4 1 0 -1/ √ 5 0.6476π -2/ √ 7 0.7728π 5 1 0 -1/ √ 7 0.6234π - √ 2/ √ 5 0.7180π -3/ √ 13 0.8128π

The SDP cone versus the cone of nonnegative matrices

We now address the difficult problem of estimating the maximal angle between the SDP cone S n + and the cone N n := {B ∈ S n : B is nonnegative entrywise}. Such problem was raised in a recent paper by Goldberg and Shaked-Monderer [2]. The following facts are known, see [2] for the asymptotic formula stated in Proposition 4.17(c). Proposition 4.17. One has: (a) Θ(S 2 + , N 2 ) = (3/4)π. Furthermore, the pair of matrices achieving this maximal angle is unique and given by

(A, B) = 1/2 -1/2 -1/2 1/2 , 0 1/ √ 2 1/ √ 2 0 .
Proof. Part (a). This is because the angle between A and B is at least (3/4)π.

Part (b). Note that B solves the minimization problem

f (A) := min { A, Y : Y ∈ N n , Y = 1}.
This problem has clearly a unique solution, namely, the matrix Y = A Nn whose entries are

Y i,j = -(1/c) min{0, A i,j } with c := Π Nn (-A) = n i,j=1 (min{0, A i,j }) 2 1/2
.

Part (c). Similarly, A solves the minimization problem

g(B) := min { X, B : X ∈ S n + , X = 1}. (4.34)
We claim that B S n + is the unique solution to (4.34). Since A and B commute, there exist an orthonormal basis {x 1 , . . . , x n } of R n and a unit vector γ ∈ R n + such that Hence, γ solves the minimization problem (4.36). But such problem admits a unique solution, which can be computed explicitly in terms of the λ i (B)'s. One gets

A = n i=1 γ i x i x T i , B = n i=1 λ i (B)x i x T i . ( 4
γ i = -(1/d) min{0, λ i (B)}, (4.37)
with

d := n i=1 (min{0, λ i (B)}) 2 1/2
.

By combining (4.35) and (4.37) one sees that, up to normalization, A is the projection of -B onto S n + . Part (d). This is a consequence of (b). Part (e). This is a consequence of Proposition 4.13. Part (f). As a consequence of (d), at least two eigenvalues of B are different from 0. Part (g). Let r be the number of negative eigenvalues of B. Then, thanks to (4.35) and (4.37), one has

A = -(1/d) r i=1 λ i (B)x i x T i with d = [ r k=1 λ 2 k (B)] 1/2 .
In particular, the rank(A) = r. In the remaining part of the proof, we use the notation λ i := λ i (B). One has rank(A) ≤ n -1, because A must be on the boundary of S n + . Suppose that rank(A) = n -1. We must arrive to a contradiction. From the proof of (c), one sees that λ i < 0 for all i ∈ {1, . . . , n -1} and

A, B = -λ 2 1 + . . . + λ 2 n-1 1/2 .
On the other hand, one has

λ 1 + . . . + λ n = 0, λ 2 1 + . . . + λ 2 n = 1, λ n > 0.

One gets in this way

λ n = 1 √ 2 1 + 2 1≤i<j≤n-1 λ i λ j 1/2 > 1 √ 2 (4.38) and A, B = -[1 -λ 2 n ] 1/2 > -1/ √ 2, contradicting the inequality Θ(S n + , N n ) ≥ (3/4)π.
The next corollary fully settles the case n = 3.

Corollary 4.20. One has Θ(S 3 + , N 3 ) = (3/4)π. Furthermore, (A, B) is an antipodal pair of (S 3 + , N 3 ) if and only if

A = xx T , B = 1 √ 2 (yy T -xx T )
with x, y ∈ R 3 such that x = 1, y = 1, x, y = 0, y i y j ≥ x i x j for 1 ≤ i ≤ j ≤ 3.

(4.39)

Proof. Let (A, B) be an antipodal pair of (S 3 + , N 3 ). Theorem 4.19(g) implies that rank(A) = 1. Hence, A = xx T with x = 1. By using Lemma 4.18 one gets

cos[Θ(S 3 + , N 3 )] = min u =1 min B∈N 3 B =1 uu T , B = min B∈N 3 B =1 λ 1 (B) = -1/ √ 2.
The second part of the corollary is obtained by using (4.33).

Remark 4.21. If t, s are nonnegative reals such that t 2 + s 2 = 1, then

x = (1/ √ 2) (t, s, -1) T , y = (1/ √
2) (t, s, 1) T satisfy (4.39) and lead to the antipodal pair

(A, B) =   1 2   t 2 ts -t ts s 2 -s -t -s 1   , 1 √ 2   0 0 t 0 0 s t s 0     .
Hence, the number of antipodal pairs of (S 3 + , N 3 ) is not finite, not even countable.

From the proof of Theorem 4.19 one sees that

cos Θ(S n + , N n ) = min{f (A) : A ∈ S n + , A = 1} (4.40) = min{g(B) : B ∈ N n , B = 1} (4.41) with f (A) = - n i,j=1 (min{0, A i,j }) 2 1/2 , g(B) = - n i=1 (min{0, λ i (B)})
B = 1 √ 10       0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0      
has unit norm and its eigenvalues are

λ 1 (B) = λ 2 (B) = -1 - √ 5 2 √ 10 , λ 3 (B) = λ 4 (B) = -1 + √ 5 2 √ 10 , λ 5 (B) = 2 √ 10 . Hence g(B) = -   -1 - √ 5 2 √ 10 2 + -1 - √ 5 2 √ 10 2   1/2 = - 1 + √ 5 2 √ 5 and
Θ(S 5 + , N 5 ) ≥ arccos - 1 + √ 5 2 √ 5 ≈ 0.7575π.
The next proposition is a complement to Theorem 4.19. It applies to the case n ≥ 5 only.

Proposition 4.23. Suppose that n ≥ 5. Let (A, B) be an antipodal pair of (S n + , N n ). Then,

λ 2 (B) < 0 < λ n-1 (B).
In particular, rank(B) ≥ 4 and rank(A) ≥ 2. For the sake of completeness, we record below a recent result due to Goldberg and Shaked-Monderer [2]. Proposition 4.24. Consider a dimension n of the form n = (q + 1)(q 3 + 1), with q being a prime power. Then

Θ(S n + , N n ) ≥ arccos - q 2 + 1 q + 1 . (4.43)
The lower bound (4.43) has the merit of being easily computable, but it applies only to special choices of n and it is not optimal in general. Consider for instance the choice q = 2, which corresponds to the first prime power.

Bibliography

Introduction

The concept of the central path plays a fundamental role in the study of interior point algorithms. This subject has been widely studied in the context of Semidefinite Programming (SDP). For instance, it is known that the central path always converge and that the limit point lies on the relative interior of the optimal set (cf. [9,6]). Furthermore, it was shown in [9] that under the strictly complementarity assumption the central path converges to the analytic center of the optimal set. In the general case the result it is not true, but the limit point can be still characterized by mean of an optimization problem (cf. [7]).

In this paper we consider the central path in a more general problem known as Symmetric Cone Linear Programming (SCLP). The SCLP not only includes the SDP, but also Linear and Second Order Cone Programming. As in SDP, the importance of the central path in SCLP lies in the study of interior point algorithms for solving the SCLP. We refer the papers [11,12] of Nesterov and Todd where the interior point algorithms were designed for the first time for solving SCLP. In [3,4], Faybusovich shows that Jordan algebra techniques can be used to describe Nesterov-Todd's method and some others interior point algorithms in a clear way. After this, important efforts were focused on the development of new algorithms for solving SCLP (e.g. [13,14,15]).

The aim of this paper is to extend some basic results of the central path of SDP to the central path of SCLP. Our analysis focuses on the convergence and the limiting behavior of the central path of SCLP under some standard assumptions.

The outline of this paper is as follows. In Section 2 we provide some preliminary materials concerning to Euclidean Jordan algebras and we introduce the central path in SCLP. In Section 3 we study the convergence of the central path. Finally, the limiting behavior is analyzed in Section 4.

Preliminaries

Euclidean Jordan algebras

Throughout this paper one assumes that (V, •, •, • ) is a Euclidean Jordan algebra (EJA) with unit element e ∈ V. This means that V is a finite dimensional real vector space equipped with an inner product •, • and a bilinear function • : V × V → V satisfying the axioms:

         x • y = y • x
for all x, y ∈ V,

x • (x 2 • y) = x 2 • (x • y) for all x, y ∈ V, x • y, z = y, x • z for all x, y, z ∈ V, e • x = x for all x ∈ V.

Here and in the sequel one uses the notation x 2 = x • x. Higher order powers are defined recursively by x k+1 = x • x k . We list below some definitions and properties concerning to the general theory of Euclidean Jordan algebras that we use throughout this work.

-The rank of V is declared to be r = max{deg(x) : x ∈ V}, where deg(x) is the smallest positive integer k such that {e, x, x 2 , . . . , x k } is linearly dependent.

-An ideal of the EJA algebra V is a subalgebra I ⊆ V such that x • u ∈ I whenever x ∈ V and u ∈ I. An EJA is simple if it does not contain any nontrivial ideal.

Preliminaries

-The set of square elements of V defined as

K := {x 2 : x ∈ V},
is a symmetric cone (cf. [2, Theorem III.2.1]). This mean that K is a self-dual closed convex cone with nonempty interior and for any two elements x, y ∈ intK, there exists an invertible linear transformation Γ : V → V such that Γ(K) = K and Γ(x) = y.

-An element c ∈ V is an idempotent if c 2 = c.

-An idempotent c is primitive if it is nonzero and cannot be written as a sum of two nonzero idempotents.

-A Jordan frame is a collection {c 1 , . . . , c r } of primitive idempotents satisfying The λ i 's are uniquely determined by x and they are called the eigenvalues of x.

-Let x ∈ V with eigenvalues λ 1 , . . . , λ r . We define:

trace of x : tr(x) = λ 1 + . . . + λ r , determinant of x : det(x) = Π r i=1 λ i , rank of x : rank(x) = number of nonzero eigenvalues of x.

-For x ∈ V the Lyapunov operator associated with a given x is the linear map L x : V → V given by L x y = x • y and the quadratic representation of x is the linear map P : V → V given by P x = 2L 2 x -L x 2 .

-One says that two elements a, b ∈ V operator commute if

a • (b • z) = b • (a • z) for all z ∈ V.
From [13,Theorem 27], this is equivalent to the existence of a Jordan frame {c 1 , . . . , c r } and real numbers λ 1 , . . . , λ r and µ 1 , . . . , µ r such that a = λ 1 c 1 + . . . + λ r c r b = µ 1 c 1 + . . . + µ r c r .

-An element x ∈ V is said to be invertible if there exists an element y ∈ V such that it is a linear combination of powers of x and satisfies x • y = e. The element y is unique. It is called the inverse of x and is denoted by y = x -1 . Note that if an invertible element x admits the spectral decomposition x = r i=1 λ i c i then its inverse admits the spectral decomposition x -1 = r i=1 (1/λ i )c i . In particular, x and x -1 operator commute. -Let c ∈ V be an idempotent element. The EJA V can be decomposed into three mutually orthogonal subspaces: Here S n denotes the space of symmetric matrices of order n, S n + stands for the cone of positive semidefinite symmetric matrices in S n and "Tr" denotes the trace of a matrix. In this setting, the identity matrix I ∈ S n is the unit element e.

V = V(c,
We study the solution of problem (P ) by using a penalization scheme with respect to the logarithmic barrier function. The assumption (A2) and the fact that the functionln det(•) is strictly convex over intK (cf. [11]) imply that for every µ > 0 problem (P µ ) admits a unique solution x(µ) and the problem (D µ ) admits a unique solution (y(µ), s(µ)) (cf. [4]). By using the KKT optimality conditions one gets that for every µ > 0, the triplet (x(µ), y(µ), s(µ)) can be characterized as the unique solution of the system Ax = b, x ∈ intK, A * y + s = c, s ∈ intK, s = (µ/ρ)x -1 .

(5.4)

It is well-known (cf. [3]) that this set of condition is equivalent to

Ax = b, x ∈ intK, (5.5)
A * y + s = c, s ∈ intK, (

x • s = (µ/ρ)e, (

The relation (5.7) is known as the centering condition of the central path. We refer to the trajectory {(x(µ), y(µ), s(µ)) : µ > 0} as the primal-dual central path (or simply central path) in SCLP.

Convergence of the central path

We start by recalling a trivial but useful lemma that is known as the orthogonality relation and it is obtained from the feasibility conditions of (P ) and (D). Lemma 5.6. Given μ > 0, the set {(x(µ), y(µ), s(µ)) : 0 < µ ≤ μ} is bounded and all its limit points are in S P × S D .

Proof. Let μ > 0. Note that y(µ) = (AA * ) -1 A(cs(µ)). Therefore, it is enough to prove that {(x(µ), s(µ)) : 0 < µ ≤ μ} is bounded. Let x 0 ∈ F P and (y 0 , s 0 ) ∈ F D be such that x 0 , s 0 ∈ intK. The orthogonality relation (5.8) implies that x(µ), s 0 + x 0 , s(µ) = x(µ), s(µ) + x 0 , s 0 .

(5.9)

From the centering condition (5.7) one has that x(µ), s(µ) = ρrµ. Hence, for every µ ≤ μ from (5.9) one gets

x(µ), s 0 + x 0 , s(µ) ≤ γ := ρr μ + x 0 , s 0 .

This implies that {(x(µ), s(µ)) : 0 < µ ≤ μ} ⊆ {(x, s) ∈ K × K : (x, s), γ -1 (x 0 , s 0 ) ≤ 1}.

Then from [2, Corollary I.1.6] one concludes that {(x(µ), y(µ), s(µ)) : 0 < µ ≤ μ} is bounded.

Next, we prove that all the limit points are in S P × S D . Let (x * , y * , s * ) be a limit point of the central path. It is possible to construct a sequence (µ k ) such that (µ k , x(µ k ), y(µ k ), s(µ k )) → (0, x * , y * , s * ), when k → +∞. We define the map Φ : R × V × R m × V → R m × V × V as Φ(µ, x, y, s) = (Axb, A * y + sc, x • s -(µ/ρ)e).

Observe that Φ(µ k , x(µ k ), y(µ k ), s(µ k )) = (0, 0, 0) for every k. Hence, by continuity of Φ we conclude that Φ(0, x * , y * , s * ) = (0, 0, 0). It means (x * , y * , s * ) ∈ S P × S D .

In the following proposition we show the convergence of the central path. The arguments are similar to those used by Halická et al. [6] for the case of SDP. Definition 5.7. A subset V ⊂ R ℓ is called an algebraic set if V is described as V = {z ∈ R ℓ : p 1 (z) = 0, . . . , p r (z) = 0}, where p i are polynomial functions on R ℓ .

We known that a matrix in S n is positive definite if and only if their leading principal minors are positive. We explain how this propertie is extended to the general context of EJA (cf. [2, Section VI.3]). Let {c 1 , . . . , c r } be any Jordan frame. We set V (k) := V(c 1 +. . .+c k , 1), k ∈ {1, . . . , r} which are subalgebras. One can see that

V (1) ⊂ V (2) ⊂ . . . ⊂ V (r) = V.
Let P k be the orthogonal projection onto V (k) . The principal minor ∆ k is the polynomial function defined on V by ∆ k (x) = det (k) (P k (x)),

where det (k) denotes the determinant with respect to the subalgebra V (k) . It is known that

x ∈ intK ⇔ ∆ k (x) > 0, for all k = 1, . . . , r, Proposition 5.8. The central path in symmetric cone linear programming always converges.

Proof. Let (x * , y * , s * ) be the limit point of the primal-dual central path. We define the sets Let n := dimV. Note that, for a fixed basis of V, the set V can be seen as the locus of common zeros of a collection of polynomial functions on R n+m+n+1 . That is V is an algebraic set. Analogously, the set U can be seen as defined by inequalities of polynomial functions on R n+m+n+1 . The set V ∩ U corresponds to the point (x, ȳ, s, µ) such that x(µ) = x + x * and s(µ) = s + s * , for all µ > 0. Moreover the zero element is in the closure of V ∩ U, by construction. Hence, we can use the curve selection lemma [6,Lemma A.2] in order to conclude the result as in [6,Theorem A.3]. The details are omitted.

V :=    (x,

Limiting behavior of the central path

In this section we study some properties of the limit point of the central path in SCLP. This is done by using the Peirce decomposition of V with respect to a particular idempotent element.

In what follows, we suppose that (x * , y * , s * ) is the limit point of the central path in SCLP. Note that the relation (5.4) implies that for every µ > 0, x(µ) and s(µ) operator commute. Hence, they admit a simultaneous spectral decomposition, namely, (5.10)

x(µ) =
On the other hand, from the optimality conditions (5.1)-(5.3) one gets

x * ∈ K, s * ∈ K, x * • s * = 0 which implies that x * and s * operator commute (cf. [5,Proposition 6]). Therefore, they also admit a simultaneous spectral decomposition. The next lemma relates the simultaneous spectral decomposition (5.10) with the simultaneous spectral decomposition of x * and s * .

Conclusions and further work

Hence, a i , x = P B,1 (a i ), x and the relation (5.26) becomes S P = {x ∈ K B,1 : P B,1 (a i ), x = b i , i = 1, . . . , m} .

Analogously, in order to show the characterization of S D , we decompose a i and c with respect to the dual Peirce decomposition (5.16):

a i = P N,1 (a i ) + P N,1/2 (a i ) + P N,0 (a i ), c = P N,1 (c) + P N,1/2 (c) + P N,0 (c).

Taking into account the above decompositions and the fact that s ∈ V(c * N , 0) imply that the condition m i=1 y i a i + sc = 0 is equivalent to The above result allows us to describe the relative interior of the primal and dual optimal sets in SCLP.

Corollary 5.16. The relative interior of the primal and dual optimal sets in SCLP are give, respectively, by ri(S P ) = {x ∈ S P : x ∈ int B,1 K B,1 }, ri(S D ) = {(y, s) ∈ S P : s ∈ int N,0 K N,0 }.

In particular, the limit point of the central path in SCLP lies in the relative interior of S P ×S D .

Conclusions and further work

The results presented in this paper extend known results on the central path in semidefinite programming. We think that this unifying approach enlights known results for particular EJA. For instance, the Peirce decomposition helps us to clarify the block notation that are present in some results of SDP (cf. Example 5.10).

Introduction 1 1 9 1. 1 9 1. 2 12 1. 3 16 1. 4 18 1. 4 . 1 19 1. 4 . 2 19 1. 4 . 3 22 2

 1919212316418411942194322 Commutation principle for variational problems on EJA Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminary material on Euclidean Jordan algebras . . . . . . . . . . . . . . 11 1.2.1 The tangent space to the set of ordered Jordan frames . . . . . . . . Proof of the general commutation principle . . . . . . . . . . . . . . . . . . . Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Variational inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . Distance to a spectral set . . . . . . . . . . . . . . . . . . . . . . . . Inradius of a spectral cone . . . . . . . . . . . . . . . . . . . . . . . . 21 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Complementarity problems with respect to Loewnerian cones 25 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 xiii

Remark 1 . 8 .

 18 A special case of Theorem 1.7 is obtained when Φ is the zero function. It reads as follows: If b is local extremum of x ∈ Ω → E(x), then b and ∇E(b) operator commute.

  is a spectral function. Under these assumptions, if b is a solution to the variational inequality (1.20), then b and G(b) operator commute. Proof. If b solves (1.20), then b ∈ Ω and

  a spectral function on V. Hence, a and b operator commute by Theorem 1.2. Thanks to Theorem 1.5, there exists c ∈ O V and μ ∈ R r such that a = r i=1 λ i (a)c i and b = r i=1 μi c i .

  Finally, one constructs a linear isomorphism L 3 : R 3 → S 2 that converts L 3 into S 2 + . The explicit form of L 3 can be found in [12, Section 2.6] or in [22, Chapter 2.5]. The next proposition concerns two classes of closed convex cones arising in the stability analysis of dynamical systems.

Corollary 3 . 21 .

 321 .35) The above inequality becomes an equality, for instance, if P and Q are nontrivial linear subspaces. Since the double sum in (3.35) is finite, any pair of polyhedral cones has finitely many critical angles. By combining (3.35) and the estimate card[Γ(spanF, spanE)] ≤ 2 min{dimF, dimE}, one gets in particularcard [Γ(P, Q)] ≤ 2 dimP k=1 dimQ ℓ=1 c P (k)c Q (ℓ) min{k, ℓ},(3.36)where c P (k) stands for the number of k-dimensional faces of P . The upper bound (3.36) is coarse in general, so we shall not elaborate further on the practical evaluation of such an expression. Let P, Q ∈ C(X) be polyhedral cones. Let (u 1 , v) and (u 2 , v) be critical pairs of (P, Q). If u 1 and u 2 have the same associated face, then the critical angles θ 1 := arccos u 1 , v and θ 2 := arccos u 2 , v are equal or conjugate.

  of vectors is conically independent simply means that no element from the collection can be expressed as positive linear combination of those remaining. For notational convenience, we introduce the index setsI(G) := {I ⊆ {1, . . . , p} : I = ∅ and {g i : i ∈ I} is linearly independent} , J(H) := {J ⊆ {1, . . . , q} : J = ∅ and {h j : j ∈ J} is linearly independent} . The cardinality of an index set, say I, is denoted by |I|. We write G I to indicate the submatrix of G with columns indexed by I. The definition of H J is similar. Without further ado, we state the next theorem. Theorem 3.22. Let (P, Q) be as in (3.37)-(3.38). Then the following statements are equivalent: (a) θ ∈ Γ(P, Q), (b) there are index sets I ∈ I(G), J ∈ J (H) and vectors ξ

  (a) ⇒ (b). Let (u, v) be a critical pair of (P, Q) such that λ := u, v = cos θ. The cone version of Caratheodory's theorem ensures the existence of index sets I ∈ I(G), J ∈ J (H), and vectors ξ ∈ R |I| , η ∈ R |J| with positive components, such that u = G I ξ and v = H J η. The normalization conditions in (3.42)-(3.43) are obtained from the fact that u and v are unit vectors. Criticality of (u, v) leads to the system

  .44) then Theorem 3.22 shows that card[Γ(P, Q)] ≤

  and contains a pair of non-collinear vectors. By applying Lemma 3.31 one obtains Θ (G(P ), G(Q)) ≤ θ max (G(K)) = ϑ (3.54) for a suitable G ∈ GL(X). Of course, one can write (3.54) with B := G T G 1/2 instead of G. It remains now to apply the Intermediate Value Theorem to the function (3.53), with A given by (3.52).

4. 2 Theorem 4 . 3 .

 243 Critical angles in a pair of revolution cones Revolutions cones, also called circular cones, are amongst the simplest and most common non-polyhedral convex cones used in mathematics. By definition, a revolution cone in X is a closed convex cone of the form Rev(φ, b) := {x ∈ X : b, x ≥ x cos φ}, where b ∈ S X defines the revolution axis and φ ∈ [0, π/2] corresponds to the half-aperture angle. The next theorem shows that a pair of revolution cones has at most three critical angles. It provides also explicit formulas for computing each critical angle. Let P = Rev(φ 1 , b 1 ) and Q = Rev(φ 2 , b 2 ), with b 1 , b 2 ∈ S X and φ 1 , φ 2 ∈ [0, π/2]. Then

Case 2 :

 2 φ 1 = 0, φ 2 > 0. In this case, P = R + b 1 . Hence, u = b 1 and b 1 ∈ L. That b 2 ∈ L follows from (4.14) and the fact that γ 2 = 0. Corollary 4.4. Let P, Q be two revolution cones as in Theorem 4.3. Then Θ(P, Q) := min{π, arccos b 1 , b

  20). Part (b). For all p ∈ [1, ∞], one has the duality formula L * p = L p * (cf. [4, Proposition 3.1]). Hence, Proposition 4.2 yields Θ(L p , L p * ) = π/2. On the other hand, by applying Theorem 4.7 one gets Θ(L 1 , L 1 ) = π/2. Hence, for q ∈ [1, p * ], one obtains π/2 = Θ(L 1 , L 1 ) ≤ Θ(L p , L q ) ≤ Θ(L p , L p * ) = π/2. (4.22)

. 23 )

 23 are lower correlated if the eigenspacesE min (A) := {x ∈ R n : Ax = λ 1 (A)x} E min (B) := {x ∈ R n : Bx = λ 1 (B)x}have a nonzero vector in common. Here, λ 1 (A) stands for the smallest eigenvalue of A. Proposition 4.10. Let A, B be positive definite symmetric matrices of order n. Then cos[Θ(E A , E B )] is equal to the optimal value of the minimization problem    minimize ξ ⊙ η ξ 2 + ξ, Aξ = 1 η 2 + η, Bη = 1.

  C is symmetric. The notation η ≥ 0 indicates that each component of η ∈ R n is nonnegative. Proposition 4.11. Let A be a positive definite symmetric matrix of order n. Let C := -(I n + A) -1 with I n denoting the identity matrix of order n. Then Θ(E A , R n+1 + ) = arccos --µ min (C) .

( 4 . 25 )

 425 Clearly, s = 0 at the minimum. By getting rid of the variable t, the problem (4.25) is converted into    minimize ξ, η ξ 2 + ξ, Aξ = 1, η 2 = 1, η ≥ 0The change of variables γ = (I n + A) 1/2 ξ leads to

cTheorem 5 . 1 .

 51 i = e and c i • c j = 0 when i = j.We recall below a spectral decomposition theorem taken from [2, Theorem III.1.2]. Let (V, •, •, • ) be an EJA with rank r. Then, for every x ∈ V, there exists a Jordan frame {c 1 , . . . , c r } and real numbers λ 1 , . . . , λ r such that x = λ 1 c 1 + . . . + λ r c r .

1 )Example 5 . 2 .

 152 ⊕ V(c, 1/2) ⊕ V(c, 0), where V(c, ℓ) := {x ∈ V : c • x = ℓx} with ℓ = 1, 1/2, 0. This decomposition is called the Peirce decomposition of V with respect to c. The projections in the Peirce decomposition are the following: onto V(c, 1) : P c , onto V(c, 1/2) : I -P c -P e-c , onto V(c, 0) : P e-c , where I stands for the identity operator in V (cf. [2, Chapter IV]). Typical examples of Euclidean Jordan algebras are:(a) Euclidean Jordan algebra of n-dimensional vectors:V = R n , x • y = x ⊙ y, x, y = n i=1 x i y i , r = n, K = R n + ,where "⊙" denotes the componentwise (Hadamard) product of vectors x and y. Here, the unitary element is e = (1, . . . , 1) ∈ R n .(b) Euclidean Jordan algebra of quadratic forms:V = R n , x • y = ( x, y , x 1 ȳ + y 1 x), x, y = n i=1 x i y i , r = 2, K = L n , where x = (x 2 . . . , x n ) ∈ R n-1 and L n := {x ∈ R n : x ≤ x 1 } is the second-order cone in R n .Here the unit element is e = (1, 0 . . . , 0) ∈ R n .(c) Euclidean Jordan algebra of n-dimensional symmetric matrices:V = S n , X • Y = (XY + Y X)/2, X, Y = Tr(XY ), r = n, K = S n + .

(

  P µ ) min x∈V { c, xµ ln det x : Ax = b, x ∈ intK}, µ > 0.One can show that the dual problem associated with (P µ ) is given by(D µ ) max (y,s)∈R m ×V { b, y + µ ln det s : A * y + s = c, s ∈ intK}

Lemma 5 . 5 .5. 3 .

 553 Let (x, y, s), (x, ỹ, s) ∈ F P × F D . Then the following orthogonality relation is satisfied:xx, ss = 0.(5.8)Proof. Let (x, y, s), (x, ỹ, s) ∈ F P × F D . That is, they satisfy Ax = b A * y + s = c , Ax = b A * ỹ + s = c. Hence, xx, ss = xx, A * (ỹy) = Ax -Ax, ỹy = 0Convergence of the central path The next lemma shows the boundeness of the central path. It is a generalization of [9, Lemma 3.1].

  ȳ, s, µ) Ax = 0 A * ȳ + s = 0 (x + x * ) • (s + s * )µe = 0    U := {(x, ȳ, s, µ) : ∆ k (x + x * ) > 0, ∆ k (s + s * ) > 0, µ > 0, k = 1, . . . , r} .

  µ)c i (µ).

y

  i P N,1 (a i ) -P N,1 (c) + m i=1 y i P N,1/2 (a i ) -P N,1/2 (c) + m i=1 y i P N,0 (a i ) + s -P N,0 (c) = 0.This is equivalent tom i=1 y i P N,α (a i ) = P N,α (c), α = 1/2, 1, and m i=1 y i P N,0 (a i ) + s = P N,0 (c). Hence, the relation (5.27) becomes S D = (y, s) ∈ R m × K N,0 : m i=1 y i P N,0 (a i ) + s = P N,0 (c), m i=1 y i P N,α (a i ) = P N,α (c), α = 1/2, 1

Table 2

 2 .1 are estimated by working with a sample of 10 4 Gaussian random maps L. Figures are rounded to one decimal place.

		n = 3	n = 6	n = 9	n = 12
	success	96.7%	99.5%	99.2%	97.4%
	divergence	2.3%	0.4%	0.5%	2.0%
	ill-conditioning	1.0%	0.1%	0.3%	0.6%

Table 2 .

 2

1: SNM applied to (2.9) with κ = κ fb . Percentages of success and failure.

Table 2 .

 2

	12

2: SNM applied to (2.9) with κ = κ fb . Average NIPs and average CPU times needed for detecting a solution.

Table 2 .

 2 3 has been constructed in the same way as Table2.1, except that now L has the special form (2.17), where A, B, C ∈ S n are random Gaussian matrices.

		n = 3	n = 6	n = 9	n = 12
	success	89.9%	23.9%	4.3%	0.5%
	divergence	6.6%	0.8%	0.1%	0.0%
	ill-conditioning	3.5%	75.3%	95.6%	99.5%
	nonsmoothness	3.5%	4.0%	2.4%	1.0%

Table 2 .

 2

3: SNM applied to (2.9) with κ = κ fb . The map L has the special form (2.17).

Table 2 . 4 :

 24 SNM applied to (2.9) with κ = κ fb . The map L has the special form (2.17).

	12

  nonsingular. Tables 2.5 and 2.6 have been constructed in the same way as Tables 2.1 and 2.2, respectively, except that now κ is the minimum complementarity function. The map L is Gaussianly generated and has no special structure.

		n = 3	n = 6	n = 9	n = 12
	success	86.7%	97.6%	99.3%	98.6%
	divergence	12.9%	2.4%	0.6%	1.0%
	ill-conditioning	0.4%	0.0%	0.1%	0.4%

Table 2 .

 2

		n = 3	n = 6	n = 9	n = 12
	NIP	1.23	1.04	1.01	1.04
	CPU	0.9	2.6	13.7	67.0

5: SNM applied to (2.9) with κ = κ min .

Table 2 .

 2

6: SNM applied to (2.9) with κ = κ min .

  The latter inequality ensures that (2.35) is a proper cone. Whether an ellipsoidal cone in S n is Loewnerian or not depends on the dimension n. The case n = 2 is somewhat special. One easily sees that (2.35) satisfies the strict convexity condition (2.29). Hence, (b) is a consequence of Corollary 2.14. Consider now the particular case n = 2. Note that

.35) where B ∈ S n and D ∈ GL(S n ) are such that D -T (B) > 1. Proposition 2.22. One has: (a) A proper cone in S 2 is Loewnerian if and only if it is an ellipsoidal cone. (b) Any ellipsoidal cone in S n , with n ≥ 3, is not Loewnerian.

Proof.

  By way of application: Finding the nearest Euclidean distance matrix A square matrix A of order m is an Euclidean distance matrix (EDM) if there are points {p i } m i=1 in some Euclidean space R d such that a ij = p ip j 2 2 for all i, j ∈ {1, . . . , m}, where • 2 is the usual Euclidean norm on R d . The EDMs of order m form a proper cone in the space

2.38

) implies the invertibility of the Lyapunov operator G lyap : S n → S n , whereas (2.39) implies the invertibility of the Stein operator G stein : S n → S n .

2.4

Table 2 . 7 :

 27 Tables 2.7 and 2.8 report the performance of the SNM applied to (2.42) and (2.43), respectively. The figures displayed in these tables are average values obtained by working with a sample of 10 2 random Gaussian matrices C. SNM applied to (2.42).

		n = 25	n = 50	n = 75	n = 100
	success	100%	100%	100%	100%
	divergence	0%	0%	0%	0%
	ill-conditioning	0%	0%	0%	0%
	CPU	5.9	79.6	217.6	839.1
		n = 25	n = 50	n = 75	n = 100
	success	100%	100%	100%	100%
	divergence	0%	0%	0%	0%
	ill-conditioning	0%	0%	0%	0%
	CPU	6.2	81.1	222.5	840.6

Table 2 . 8

 28

: SNM applied to (2.43).

  2. The numerical resolution of Example 2.1 is treated here for the first time. Example 2.1 has been the driving motivation behind our work. By contrast, Example 2.2 is mentioned just to illustrate that the SDCP model (2.1) covers a wide variety of applications.

The literature dealing with the optimization problem (2.4) is quite extense and comparing different methods for solving (2.4) is beyond the scope of this work.

Table 3 .

 3

			15	31	63
	q=2	11	31	53	99
	q=3	13	37	77	151
	q=4	-	41	87	185
	q=5	-	-	105	217
	q=6	-	-	-	247

2: Lower bounds for c n (p, q).

Table 3 . 3 :

 33 Conditional expectations of x with respect to different orientations of v.

		n = p = 3	n = p = 4	n = p = 5	n = p = 6
	E[x| v ∈ P ]	4.66	6.46	8.06	9.24
	E[x| v ∈ -P ]	1	1	1	1
	E[x| v / ∈ P ∪ -P ]	1.40	1.64	1.78	1.86

.3 displays the conditional expectations of x with respect to different orientations of v. Figures are rounded to two decimal places.

  1 , φ 2 > 0. This case is the most interesting one. By combining Proposition 4.1 and the boundary principle for proper critical pairs (cf. [8, Theorem 2.3]), one knows that that u Hence, there exist Lagrange multipliers µ 1 , γ 1 for the problem (4.10) and Lagrange multipliers µ 2 , γ 2 for the problem (4.11), such that

	and v solve	  	x 2 = 1 minimize x, v -λu b 1 , x = cos φ 1	(4.10)
	and	  	y 2 = 1, minimize u -λv, y b 2 , y = cos φ 2	(4.11)
	respectively.

  It suffices to apply Proposition 4.5 and Theorem 4.7 to the norms mentioned in (4.23).

	1/2
	.
	Proof. Note that
	α 2 f = min x =1

Table 4 . 1 :

 41 Critical angles between S n + and D n . Both cones are orthogonally invariant. The associated permutation invariant cones are R n are simplicial cones in R n . Table 4.1 is filled with the help of [8, Theorem 7.3]. Remark 4.16. It is possible to derive an explicit formula for the maximal angle between S n

	+

+

and

D n := {x ∈ R n : max{x 1 , . . . , x n } ≤ x 1 + . . . + x n },

respectively. Beware that S n + and D n are non-polyhedral cones in S n , so a direct computation of Γ(S n + , D n ) could be difficult. Computing Γ(R n + , D n ) is much easier, because R n + and D n (2n, 1, . . . , 1) T .

Table 4 . 2 :

 42 Lower bound for Θ(S n

	n	Θ(S n + , Nn)	n	Θ(S n + , Nn)	n	Θ(S n + , Nn)
	4	0.7500 π	13	0.7649 π	22	0.7719 π
	5	0.7575 π	14	0.7658 π	23	0.7722 π
	6	0.7575 π	15	0.7677 π	24	0.7735 π
	7	0.7575 π	16	0.7699 π	25	0.7735 π
	8	0.7607 π	17	0.7699 π	26	0.7735 π
	9	0.7607 π	18	0.7699 π	27	0.7739 π
	10	0.7609 π	19	0.7703 π	28	0.7750 π
	11	0.7626 π	20	0.7719 π	29	0.7750 π
	12	0.7649 π	21	0.7719 π	30	0.7753 π

+ , N n ).

A shortened version of this chapter was published on SIAM Journal on Optimization, see[13].

Departamento de Ingeniería Matemática, Centro de Modelamiento Matemático (CNRS UMI 2807), FCFM, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile (E-mail: hramirez@dim.uchile.cl). This author is supported by FONDECYT project No. 1110888 and BASAL Project (Centro de Modelamiento Matemático, Universidad de Chile).

University of Avignon, Department of Mathematics, 33 rue Louis Pasteur, 84000 Avignon, France (E-mail: alberto.seeger@univ-avignon.fr).

Departamento de Ingeniería Matemática, Centro de Modelamiento Matemático (CNRS UMI 2807), FCFM, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile (E-mail: dsossa@dim.uchile.cl). This author is supported by CONICYT (Chile).

The paper corresponding to this chapter was accepted for publication on Journal of Global Optimization, see[START_REF] Seeger | Complementarity problem with respect to Loewnerian cones[END_REF].

University of Avignon, Department of Mathematics,

rue Louis Pasteur, 84000 Avignon, France (E-mail: alberto.seeger@univ-avignon.fr).3 Departamento de Ingeniería Matemática, Centro de Modelamiento Matemático (CNRS UMI 2807), FCFM, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile (E-mail: dsossa@dim.uchile.cl). This author is supported by CONICYT (Chile).

Université d'Avignon, Département de Mathématiques, 33 rue Louis Pasteur, 84000 Avignon, France (alberto.seeger@univ-avignon.fr)

Departamento de Ingeniería Matemática, Centro de Modelamiento Matemático (CNRS UMI 2807), FCFM, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile (dsossa@dim.uchile.cl). This author is supported by CONICYT, Chile.

It means a finite dimensional inner product space.

This material is not included in the paper submitted for publication

Universidad de Chile, Center of Mathematical Modeling, Casilla 170-3, Santiago, Chile. E-mail: hramirez@dim.uchile.cl.

Universidad de Chile, Department of Mathematical Engineering, Casilla 170-3, Santiago, Chile. E-mail: dsossa@dim.uchile.cl.

Acknowledgments

I thank God for blessing me much more than I deserve and for his wonderful promise expressed in John 3:16 "For God so loved the world, that he gave his only begotten Son, that whosoever believeth in him should not perish, but have everlasting life." I would like to thank my two advisors, Prof. Héctor Ramírez and Prof. Alberto Seeger. Their patience, encouragement, and immense knowledge were key motivations throughout my PhD. It is a real honor for me to have worked with them. Special thanks for the friendship and the hospitality received during my stay in Santiago and Avignon.

I would like to thank Prof. Aris Daniilidis and Prof. Seetharama Gowda for review the earlier version of this thesis and for several suggestions that improved the presentation. I am also grateful to my oral committee members: Prof. Pedro Gajardo, Prof. Dinh The Luc and Prof. Michel Volle for their time, interest, helpful comments and insightful questions.

I would also like to express my gratitude to all my friends I made during this period of time at the DIM-UCH and at the LMA-UAPV. Special thanks to the couples Paola and César, Ying and Huyuan. Thank you for all of your support and sincere friendship. Special thanks to Caroline for her help and warm hospitality offered during my stay in Avignon.

Acknowledgement. Both authors would like to thank the referees for meticulous reading of the manuscript and for several suggestions that improved the presentation.

I gratefully acknowledge the funding sources that made my Ph.D. work possible. My studies in Chile were funded by CONICYT (Comisión Nacional de Investigación Científica y Tecnológica de Chile) and during my stay in France I was funded by the grants for short research stays from the Universidad de Chile, from the Center for Mathematical Modeling (CMM) and from the Embassy of France in Chile.

Last but not least, I thank to my family. Thanks to my beloved wife Liz Fabiola and my beloved daughter Flor Daliz. Thank you for being there every step of the way with me.

Antipodality, pointedness and reproducibility

The sum of two closed convex cones may not be closed. The next proposition is part of the folklore on convex cones, cf. [2,Theorem 3.2]. A pair (P, Q) of elements in C(X) is said to be pointed if P ∩ -Q = {0}. A single cone K ∈ C(X) is declared pointed if the pair (K, K) is pointed.

Proposition 3.11. Let P, Q ∈ C(X). The following conditions are equivalent and imply that P + Q is closed:

(a) (P, Q) is pointed.

(b) There exists a positive constant β such that

The reverse triangular inequality (3.19) holds of course with β = 0, but such choice is useless. What is interesting to know is the best constant

Such a coefficient measures to which extent the pair (P, Q) is pointed. The next proposition relates β(P, Q) to the maximal angle of (P, Q). Proposition 3.12. Let P, Q ∈ C(X). Then

Proof. We need to prove that β(P, Q) = κ(P, Q). Assume that P and Q are not equal to a common ray, otherwise we are done. Clearly,

But the Dunkl-Williams inequality implies that

whenever u, v ∈ X are nonzero vectors. Hence, β(P, Q) is greater than or equal to κ(P, Q). The reverse inequality is obvious.

A pair (P, Q) of elements in C(X) is said to be

The next theorem lists various conditions that are necessary for antipodality in (S n + , N n ). We start by writing a linear algebra result concerning the smallest eigenvalue of a nonnegative symmetric matrix.

Proof. In order to alleviate the notation, we write λ i := λ i (B) for all i ∈ {1, . . . , n}. Since B is nonnegative entrywise, the spectral radius

On the other hand,

It follows that

This completes the proof of the lemma.

Theorem 4.19. Let n ≥ 3. The following conditions are necessary for (A, B) to be an antipodal pair of (S n + , N n ):

Proof. Let λ i := λ i (B) for all i ∈ {1, . . . , n}. Suppose that λ n-1 ≤ 0. We must arrive to a contradiction. One has λ i ≤ 0 for all i ∈ {1, . . . , n -1}. The inequality in (4.38) is not strict, but holds in the form " ≥ ′′ . One gets in such a case

contradicting the fact that λ n = ρ(B).

where t n denotes the optimal value of the nonlinear program

The gradients of f 0 , f 1 , f 2 , and f 3 , are all easily computable. For instance, the partial gradients of f 1 and f 2 with respect to Z are given by

Projecting onto S n + and N n offers no difficulty. Table 4.2 has been filled by solving (4.42) with the help of the package "fmincon" of MATLAB. This is done for each n ∈ {4, . . . , 30}. Since (4.42) is a nonconvex optimization problem, we are not sure if "fmincon" is yielding a global solution or just a local solution. For this reason we are rather conservative and consider the figures in Table 4.2 only as lower bounds for Θ(S n + , N n ). These figures have been rounded down to four decimal places.

Chapter 5

On the central path in symmetric cone linear programming

Abstract. In this paper we study the convergence and the limiting behavior of the central path in symmetric cone linear programming.

Symmetric cone linear programming

The primal SCLP is formulated as

a linear map. The dual problem associated with (P ) is given by (D) max

where A * is the adjoint map of A and the superscript "T " stands for the transpose of a vector. Consequently, b T y = m i=1 b i y i . The primal and dual feasible sets are denoted by F P and F D , respectively, whereas S P and S D denote their respective optimal sets. Remark 5.3. Without loss of generality, we can think that the space (V, •, • ) on problem (P ) is an arbitrary Euclidean space and the cone K is an arbitrary symmetric cone on V. This follows from [2, Theorem III.3.1] which establishes that it is possible to construct a Jordan product " • " such that (V, •, •, • ) is a Euclidean Jordan algebra and K coincides with the cone of square elements on V.

Example 5.4. Linear programming, second order cone programming and semidefinite programming are particular cases of SCLP. In fact, this is obtained by taking, respectively, K = R n + , K = L n and K = S n + with their corresponding spaces as in Example 5.2.

Throughout this paper, we take the following standard assumptions:

(A1) A is a surjective linear map;

(A2)

Assumption (A1) ensures that the dual variables y and s are in one-to-one correspondence. Assumption (A2) implies that S P and S D are nonempty and bounded and there is no duality gap between (P ) and (D). Assumption (A3) ensures that the set of primitive idempotents elements of V is compact (cf. [8]) and that the EJA is scalarizable (cf. [2, Proposition III.4.1]), i.e., there exists a positive constant ρ such that

The KKT optimality conditions state that (x, y, s) ∈ S P × S D if and only if it solves the following system of equations

x • s = 0.

(5.3) Lemma 5.9. Consider the simultaneous decomposition of x(µ) and s(µ) given by (5.10).

Then, there exist a simultaneous spectral decomposition of x * and s * , namely,

and a sequence {µ k } ⊂ intR + satisfying µ k ↓ 0 when k → ∞ such that for every i ∈ {1, . . . , r} one has

when k → ∞.

Proof. The continuity of the Jordan product and the fact that the set of all primitive idempotents in a simple EJA is compact (cf. [8]) lead us to conclude that the set of Jordan frames is compact. Since the central path is bounded, we also have that the eigenvalues of x(µ) and s(µ) are bounded. Hence, the set {c 1 (µ), . . . , c r (µ), γ 1 (µ), . . . , γ r (µ), δ 1 (µ), . . . , δ r (µ) : µ > 0} (5.13) is bounded. Therefore, there exist sequences given by (5.12) whose limit point satisfy the simultaneous spectral decomposition given in (5.11).

Let u ∈ V be such that it admits the spectral decomposition u = r i=1 λ i d i . We introduce the following index notation I := {1, . . . , r}, I + (u) := {i ∈ I : λ i > 0}, I 0 (u) := {i ∈ I : λ i = 0}.

The Jordan frame in (5.11) can be partitioned as

We define c * B :=

The Peirce decompositions of V with respect to the idempotents c * B and c * N are given, respectively, by

We use the words primal and dual Peirce decomposition of V to refer the decomposition (5.15) and (5.16), respectively.

Example 5.10. We illustrate the case V = S n (semidefinite programming). Let (X * , y * , S * ) be the limit point of the central path. We denote |B| := rank(X * ) and |N | := rank(S * ).

Note that in general |B| + |N | ≤ n. Without loss of generality (applying an orthonormal transformation of problem data, if necessary) we can assume that

where Λ * B and Λ * N are positive definite diagonal matrices of order |B| and |N |, respectively. Hence, we can choose as common Jordan frame the set {e 1 e T 1 , . . . , e n e T n } where {e 1 , . . . , e n } is the canonical basis of R n . Therefore, the idempotents defined in (5.14) becomes

where I |B| and I n-|N | are the identity matrices of order |B| and n -|N |, respectively. Furthermore, we have that

The next proposition shows that the partitions (5.15) and (5.16) are optimal in the sense that V(c * B , 1) and V(c * N , 0) are subalgebras of V with the smallest rank containing the primal and dual optimal sets, respectively. Proposition 5.11. We have that

Proof. Let us consider the simultaneous spectral decompositions of x * and s * and the sequence {µ k } given by Lemma 5.9. Let (x, y, s) ∈ S P × S D . We get from the orthogonality relation (5.8) that x(µ k )x, s(µ k )s = 0.

(5.17)

By using the fact that x • s = 0 and

Observe that the two terms of the left hand of the last equation are nonnegative. This implies that x, x(µ k ) -1 ≤ ρr, s, s(µ k ) -1 ≤ ρr.

(5.19)

By using the spectral decomposition of x(µ k ) one obtains that x(µ k ) -1 = r i=1 (1/γ i (µ k ))c i (µ k ). Hence, the first inequality of (5.19) becomes

Since each term of the left hand side of (5.20) is nonnegative, we deduce that

Letting k → +∞, this implies that

Therefore, one obtains x, c * i = 0, ∀i ∈ I 0 (x * ).

(5.21)

From [5,Proposition 6], and the fact that x, c * i ∈ K it follows that (5.21) is equivalent to

Finally, since c * B + i∈I 0 (x * ) c * i = e, one gets

That is x ∈ V(c * B , 1). We have thus proved that S P ⊆ V(c * B , 1). The proof of S D ⊆ R m × V(c * N , 0) is analogous. Definition 5.12. We say that (x, ȳ, s) ∈ S P × S D is a maximally complementary solution if it maximizes rank(x) + rank(s) over S P × S D . Recall that rank(x) stands for the number of nonzeros eigenvalues of x.

Corollary 5.13. The limit point of the central path is a maximally complementary solution.

Proof. The result follows from Proposition 5.11 since it implies the following stronger relation rank(x) ≤ rank(x * ), ∀x ∈ S P , rank(s) ≤ rank(s * ), ∀(y, s) ∈ S D

The next proposition characterizes of the primal and dual optimal sets in SCLP.

Proposition 5.14. The primal and dual optimal sets in SCLP can be characterized, respectively, as Since s ∈ V(c * N , 0) we have that

This together with (5.24) implies

[2, Proposition IV.1.1]), we conclude that x • c * T = 0, which leads to x, s = 0. We have thus proved that (x, y, s) satisfies the optimality conditions (5.1)-(5.3), i.e., x ∈ S P .

For τ ∈ {B, N } and α ∈ {0, 1/2, 1}, we introduce the following notations

Note that, there exists a collection {a 1 , . . . , a m } ⊂ V such that the linear map A : V → R m can be expressed as Ax = ( a 1 , x , . . . a m , x ) T .

(5.25)

By using the projections onto the primal and dual Peirce decomposition, Proposition 5.14 can be written in the following way: Proposition 5.15. The primal and dual optimal sets in SCLP can be characterized, respectively, as

Proof. Taking the representation (5.25) for the linear map A and noting that V(c * τ , α) ∩ K = K τ,α (τ ∈ {B, N }, α ∈ {0, 1}), the result of Proposition 5.14 can be expressed as We show the characterization of S P . For every i ∈ {1, . . . , m}, the decomposition of a i with respect to the primal Peirce decomposition (5.16) is given by a i = P B,1 (a i ) + P B,1/2 (a i ) + P B,0 (a i ).

The fact that x ∈ V(c * B , 1) implies that P B,1/2 (a i ), x = P B,0 (a i ), x = 0.

A full characterization of the limit points of the central path is still an open question. We believe that, as occurs in SDP, under the strictly complementarity assumption the limit point should coincide with the analytic center of the primal-dual optimal set.

Our future works will intend to characterize this limit point by following the approach presented in [7,Theorem 3.2]. It was shown therein that the limit point of the central path in SDP is the analytic center of some subset of the primal-dual optimal set. We also expect to study the central path in symmetric cone convex programming associated with a larger class of penalty-barrier functions as it was carried out in [10] for the SDP case.

Bibliography