How to project onto an isotone projection cone

The solution of the complementarity problem defined by a mapping f:Rⁿ→Rⁿ and a cone K⊂Rⁿ consists of finding the fixed points of the operator P_K°(I-f), where P_K is the projection onto the cone K and I stands for the identity mapping. For the class of isotone projection cones (cones admitting projections isotone with respect to the order relation they generate) and f satisfying certain monotonicity properties, the solution can be obtained by iterative processes (see G. Isac, A.B. Németh, Projection methods, isotone projection cones, and the complementarity problem, J. Math. Anal. Appl. 153(1) (1990) 258-275 and S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350(1) (2009) 340-347). These algorithms require computing at each step the projection onto the cone K. In general, computing the projection mapping onto a cone K is a difficult and computationally expensive problem. In this note it is shown that the projection of an arbitrary point onto an isotone projection cone in Rⁿ can be obtained by projecting recursively at most n-1 times into subspaces of decreasing dimension. This emphasizes the efficiency of the algorithms mentioned above and furnishes a handy tool for some problems involving special isotone projection cones, as for example the non-negative monotone cones occurring in reconstruction problems (see e.g. Section 5.13 in J. Dattorro, Convex Optimization and Euclidean Distance Geometry, Meboo, 2005, v2009.04.11).     

Approximations in the l∞ norm and the generalized inverse

We introduce the concept of a strict l_∞-metric projector, based in the definition of strict approximation, to prove that for each matrix A of order m×n with coefficients in the field R of real numbers there exists a set of operators G: R^m → Rⁿ homogeneous and continuous, but not necessarily linear (strict generalized inverse) such that AGA = A and 6AGy?y6 is minimized for all y, when the norm is the l_∞ norm. We investigate the properties of these operators and prove that there are two distinguished operators A^-1_{∞, β} and A^-1_∞ which are extensions of the generalized inverse introduced by Newman and Odell in the case of a strictly convex norm.     

Maximal exponents of polyhedral cones (II)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rⁿ. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that the maximum value of γ(K) as K runs through all n-dimensional minimal cones (i.e., cones having n+1 extreme rays) is n²-n+1 if n is odd, and is n²-n if n is even, the maximum value of the exponent being attained by a minimal cone with a balanced relation for its extreme vectors. The K-primitive matrices A such that γ(A) attain the maximum value are identified up to cone-equivalence modulo positive scalar multiplication.     

Theory of cones

This survey deals with the aspects of archimedian partially ordered finite-dimensional real vector spaces and order preserving linear maps which do not involve spectral theory. The first section sketches some of the background of entrywise nonnegative matrices and of systems of inequalities which motivate much of the current investigations. The study of inequalities resulted in the definition of a polyhedral cone K and its face lattice F(K). In Section II.A the face lattice of a not necessarily polyhedral cone K in a vector space V is investigated. In particular the interplay between the lattice properties of $\text{F}$(K) and geometric properties of K is emphasized. Section II.B turns to the cones Π(K) in the space of linear maps on V. Recall that Π(K) is the cone of all order preserving linear maps. Of particular interest are the algebraic structure of Π(K) as a semiring and the nature of the group Aut(K) of nonsingular elements A?Π(K) for which A^-1?Π(K) as well. In a short final section the cone P_n of n×n positive semidefinite matrices is discussed. A characterization of the set of completely positive linear maps is stated. The proofs will appear in a forthcoming paper.     

On the semiring of cone preserving maps

If K is a proper cone in Rⁿ, then the cone of all linear operators that preserve K, denoted by π(K), forms a semiring under usual operator addition and multiplication. Recently J.G. Horne examined the ideals of this semiring. He proved that if K₁, K₂ are polyhedral cones such that π(K₁) and π(K₂) are isomorphic as semirings, then K₁ and K₂ are linearly isomorphic. The study of this semiring is continued in this paper. In Sec. 3 ideals of π(K) which are also faces are characterized. In Sec. 4 it is shown that π(K) has a unique minimal two-sided ideal, namely, the dual cone of π(K¹), where K¹ is the dual cone of K. Extending Horne's result, it is also proved that the cone K is characterized by this unique minimal two-sided ideal of π(K). The set of all faces of π(K) inherits a quotient semiring structure from π(K). Properties of this face-semiring are given in Sec. 5. In particular, it is proved that this face-semiring admits no nontrivial congruence relation iff the duality operator of π(K) is injective. In Sec. 6 the maximal one-sided and two-sided ideals of π(K) are identified. In Sec. 8 it is shown that π(K) never satisfies the ascending-chain condition on principal one-sided ideals. Some partial results on the question of topological closedness of principal one-sided ideals of π(K) are also given.     

Indecomposable cones

We study some relations between a reproducing cone K in a linear space V over a fully ordered field F and the cone Γ(K) in Hom (V,V) consisting of all operators A such that AK ? K. In particular, indecomposable cones are considered.     

Cones and error bounds for linear iterations

Consider an ordered Banach space with a cone of positive elementsK and a norm ∥·∥. Let [a,b] denote an order-interval; under mild conditions, ifx*∈[a,b] then $$||x * - \tfrac{1}{2}(a + b)|| \leqslant \tfrac{1}{2}||b - a||.$$ This inequality is used to generate error bounds in norm, which provide on-line exit criteria, for iterations of the type $$x_r = Ax_{r - 1} + a,A = A^ + + A^ - ,$$ whereA ⁺ andA ^? are bounded linear operators, withA ⁺ K ?K andA ^? K ? ?K. Under certain conditions, the error bounds have the form $$\begin{gathered} ||x * - x_r || \leqslant ||y_r ||,y_r = (A^ + - A^ - )y_{r - 1} , \hfill \\ ||x * - x_r || \leqslant \alpha ||\nabla x_r ||, \hfill \\ ||x * - \tfrac{1}{2}(x_r + x_{r - 1} )|| \leqslant \tfrac{1}{2}||\nabla x_r ||. \hfill \\ \end{gathered} $$ These bounds can be used on iterative methods which result from proper splittings of rectangular matrices. Specific applications with respect to certain polyhedral cones are given to the classical Jacobi and Gauss-Seidel splittings.     

Fourier transforms of smooth functions on certain nilpotent Lie groups

The authors consider irreducible representations $\text{π ?}\text{N}\text{?}$ of a nilpotent Lie group and define a Fourier transform for Schwartz class (and other) functions φ on N by forming the kernels K_φ(x, y) of the trace class operations π_φ = ∝_Nφ(n)π_ndn, regarding the π as modeled in L²(R^k) for all π in general position. For a special class of groups they show that the models, and parameters λ labeling the representations in general position, can be chosen so the joint behavior of the kernels K_φ(x, y, λ) can be interpreted in a useful way. The variables (x, y, λ) run through a Zariski open set in Rⁿ, n = dim N. The authors show there is a polynomial map u = A(x, y, λ) that is a birational isomorphism A: Rⁿ → Rⁿ with the following properties. The Fourier transforms F₁φ = K_φ(x, y, λ) all factor through A to give “rationalized” Fourier transforms Fφ(u) such that Fφ ° A = F₁φ. On the rationalized parameter space a function f(u) is of the form F_φ = f ? f is Schwartz class on Rⁿ. If polynomial operators T?P(N) are transferred to operators $\text{T}\text{?}$ on Rⁿ such that $\text{F(Tφ) =}\text{T}\text{?}\text{(Fφ), P(N)}$ is transformed isomorphically to P(Rⁿ).     

Row-ordering schemes for sparse givens transformations. I. bipartite graph model

Let A be an m-by-n matrix, m?n, and let P_r and P_c be permutation matrices of order m and n respectively. Suppose P_rAP_c is reduced to upper trapezoidal form $\text{(}\text{R}\text{O}\text{)}$ using Givens rotations, where R is n by n and upper triangular. The sparsity structure of R depends only on P_c. For a fixed P_c, the number of arithmetic operations required to compute R depends on P_r. In this paper, we consider row-ordering strategies which are appropriate when P_c is obtained from nested-dissection orderings of A^TA. Recently, it was shown that so-called “width-2” nested-dissection orderings of A^TA could be used to simultaneously obtain good row and column orderings for A. In this series of papers, we show that the conventional (width-1) nested-dissection orderings can also be used to induce good row orderings. In this first paper, we analyze the application of Givens rotations to a sparse matrix A using a bipartite-graph model.     

The degree of an integral point in Ps minus a hypersurface

Let K be a number field of degree m with ring of integers R and absolute discriminant d_K. Given a hypersurface Z_K of degree d in the projective space P_K^us over K with Zariski closure Z in P_R^s, we give an explicit function of m, d_K, s,d, a Hermitian metric on R^s+1 ⊗_z C, and a projective height of Z defined in [1], 4.1, such that there exists an integral point in P_R^s Z of degree bounded by this function.     

The variety of the asymptotic values of a real polynomial etale map

A polynomial map F: R² → R² is said to satisfy the Jacobian condition if ∀(X, Y)ϵ R², J(F)(X, Y) ≠ 0. The real Jacobian conjecture was the assertion that such a map is a global diffeomorphism. Recently the conjecture was shown to be false by S. Pinchuk. According to a theorem of J. Hadamard any counterexample to the conjecture must have asymptotic values. We give the structure of the variety of all the asymptotic values of a polynomial map F: R² → R² that satisfies the Jacobian condition. We prove that the study of the asymptotic values of such maps can be reduced to those maps that have only X- or Y-finite asymptotic values. We prove that a Y-finite asymptotic value can be realized by F along a rational curve of the type (X^{− k}, A₀ + A₁ X + … + A_{N − 1} X^{N − 1} + YX^N), where X → 0, Y is fixed and K, N > 0 are integers. More precisely we prove that the coordinate polynomials P(U, V) of F(U, V) satisfy finitely many asymptotic identities, namely, identities of the following type, P(X^{− k}, A₀ + A₁ X + … + A_{N − 1} X^{N − 1} + YX^N) = A(X, Y)ϵ R[X, Y], which ‘capture’ the whole set of asymptotic values of F.     

Conjugate cone characterization of positive definite and semidefinite matrices

Positive definite and semidefinite matrices are characterized in terms of positive definiteness and semidefiniteness on arbitrary closed convex cones in Rⁿ. These results are obtained by generalizing Moreau's polar decomposition to a conjugate decomposition. Some typical results are: The matrix A is positive definite if and only if for some closed convex cone K, A is positive definite on K and (A+A^T)^?1 exists and is semidefinite on the polar cone K°. The matrix A is positive semidefinite if and only if for some closed convex cone K such that either K is polyhedral or (A+A^T)(K) is closed, A is positive semidefinite on both K and the conjugate cone K^A={s∣x^T(A+ A^T)s?0?x∈K}, and (A+A^T)x=0 for all x in K such that x^TAx=0.     

Injectivity and operator spaces

Let B(H) be the bounded operators on a Hilbert space H. A linear subspace R ? B(H) is said to be an operator system if 1 ?R and R is self-adjoint. Consider the category $\text{b}$ of operator systems and completely positive linear maps. R ∈ $\text{C}$ is said to be injective if given A ? B, A, B ∈ $\text{C}$, each map A → R extends to B. Then each injective operator system is isomorphic to a conditionally complete C¹-algebra. Injective von Neumann algebras R are characterized by any one of the following: (1) a relative interpolation property, (2) a finite “projectivity” property, (3) letting M_m = B(C^m), each map R → N ? M_m has approximate factorizations R → M_n → N, (4) letting K be the orthogonal complement of an operator system N ? M_m, each map $\text{M}{}_{\mathrm{m}}\text{K}\text{→ R}$ has approximate factorizations $\text{M}{}_{\mathrm{m}}\text{K}\text{→ M}{}_{\mathrm{n}}\text{→ R}$. Analogous characterizations are found for certain classes of C¹-algebras.     

The Samelson product and rational homotopy for gauge groups

This paper is on the connecting homomorphism in the long exact homotopy sequence of the evaluation fibration ev_p0 :C(P, K) ^K →K, whereC(P, K) ^K is the gauge group of a continuous principalK-bundle. We show that in the case of a bundle over a sphere or a orientable surface the connecting homomorphism is given in terms of the Samelson product. As applications we get an explicit formula for π₂(C(P _k ,K) ^K ), whereP _k denotes the principal S³-bundle over S⁴ of Chern numberk and derive explicit formulae for the rational homotopy groups π _n (C(P,K) ^K )??.     

Remarks on frequency domain methods for Volterra integral equations

The equation u(t) = ? ∫₀^tA(t ? τ) g(u(τ)) dτ + h(t), t ? 0 is studied on a Hilbert space H. A(t) is a family of bounded linear operators and g can be unbounded and nonlinear. Stability and asymptotic stability of solutions are studied. Frequency domain conditions are statements about the Laplace transform of A. An extension of the frequency domain method of Popov for H = R¹ is given. Here it is assumed that g is the gradient of a functional G. The frequency domain conditions are related to monotonicity and convexity conditions on A thus connecting Popov's result with work of Levin and London on equations in R¹. A second result is given in which g is not assumed to be a gradient. This extends a result of Levin in R¹. The ideas are illustrated by an example of a nonlinear partial differential functional equation.     

Degenerate complementary cones induced by aK 0-matrix

In this paper we prove two results concerning the unionC of all the degenerate complementary cones associated with the linear complementarity problem (M, q) whereM is aK ₀-matrix.

1. C is the same as the set of allq ∈R ⁿ for which (M, q) has infinitely many solutions.
2. C is the same as the boundary of the set of allq ∈ R ⁿ for which (M, q) has a solution, an easily observable geometric result for a 2 × 2K ₀-matrix.

     

Les operateurs quasi Fredholm: Une generalisation des operateurs semi Fredholm

The present paper is concerned with the study of a new class of linear operators on a Hilbert space: the class of quasi-Fredholm operators, which contains many operators already studied in the litterature (in particular semi-Fredholm operators). An operatorA is said to be quasi-Fredholm of degreed, if the following conditions are satisfied:

1. For alln greater thand, R(A ⁿ )∩N(A)=R(A ^d )∩N(A);
2. N(A)∩R(A ^d ) is closed inH;
3. R(A)+N(A ^d ) is closed inH.

Two characterisations of quasi-Fredholm operators are given:

1. A is quasi-Fredholm iff there exists a direct decomposition ofH into the sum of two subspacesH ₁ andH ₂ which are invariant underA and such that the restriction ofA toH ₁ is quasi-Fredholm of degree 0 and the restriction ofA toH ₂ is nilpotent (Kato decomposition).
2. A is quasi-Fredholm iff there exists a neighborhoodD of 0 in C such that for all λ≠0 in that neighborhoodA?λI has a generalized inverse which is meromorphic inD?{0} (The generalized inverse is holomorphic inD iffA is of degree 0).

The bulk of the paper is devoted to the proofs of these characterizations and of related results, making use of the theory of operators ranges and of generalized inverses. Most of the results extend easily to the Banach case. The rest of the paper deals with the class of quasi-normal operators, which is closely related to the class of spectral operators. Some applications of the first part of the paper are given in this context.