Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R ₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

The Compression Property for Affine Variational Inequalities

In 1965, Gale and Nikaidô showed that for any n × n P-matrix A, the only nonnegative vector that A sends into a nonpositive vector is the origin. They applied that result to derive various results including univalence properties of certain nonlinear functions. In this article, we show that an extension of their result holds with the nonnegative orthant replaced by any nonempty polyhedral convex cone. In place of the P-matrix condition, we require a determinantal condition that we call the compression property. When the polyhedral convex cone is the nonnegative orthant, the compression property reduces to the property of being a P-matrix and we recover the Gale-Nikaidô result. We apply the extended theorem to derive tools useful in the analysis of affine variational inequalities over polyhedral convex cones.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

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.     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.     

Integral type linear functionals on ordered cones

We introduce linear functionals on an ordered cone that are minimal with respect to a given subcone. Using concepts developed for Choquet theory we observe that the properties of these functionals resemble those of positive Radon measures on locally compact spaces. Other applications include monotone functionals on cones of convex sets, H-integrals on H-cones in abstract potential theory, and classical Choquet theory itself.

     

Maximal Quadratic Modules on ∗-rings

We generalize the notion of and results on maximal proper quadratic modules from commutative unital rings to ?-rings and discuss the relation of this generalization to recent developments in noncommutative real algebraic geometry. The simplest example of a maximal proper quadratic module is the cone of all positive semidefinite complex matrices of a fixed dimension. We show that the support of a maximal proper quadratic module is the symmetric part of a prime ?-ideal, that every maximal proper quadratic module in a Noetherian ?-ring comes from a maximal proper quadratic module in a simple artinian ring with involution and that maximal proper quadratic modules satisfy an intersection theorem. As an application we obtain the following extension of Schmüdgen’s Strict Positivstellensatz for the Weyl algebra: Let c be an element of the Weyl algebra \(\mathcal{W}(d)\) which is not negative semidefinite in the Schrödinger representation. It is shown that under some conditions there exists an integer k and elements \(r_1,\ldots,r_k \in \mathcal{W}(d)\) such that ∑ _j=1 ^k r _j c r _j ^? is a finite sum of hermitian squares. This result is not a proper generalization however because we don’t have the bound k ≤d.     

Semidefinite Representation of Convex Hulls of Rational Varieties

Using elementary duality properties of positive semidefinite moment matrices and polynomial sum-of-squares decompositions, we prove that the convex hull of rationally parameterized algebraic varieties is semidefinite representable (that is, it can be represented as a projection of an affine section of the cone of positive semidefinite matrices) in the case of (a) curves; (b) hypersurfaces parameterized by quadratics; and (c) hypersurfaces parameterized by bivariate quartics; all in an ambient space of arbitrary dimension.     

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.     

A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope

For a convex body B in a vector space V, we construct its approximation P_k, k =1 , 2, . . ., using an intersection of a cone of positive semidefinite quadratic forms with an affine subspace. We show that P_k is contained in B for each k. When B is the Symmetric Traveling Salesman Polytope on n cities T_n, we show that the scaling of P_k by n/k + O(1/n) contains T_n for . Membership for P_k is computable in time polynomial in n (of degree linear in k). We also discuss facets of T_n that lie on the boundary of P_k and we use eigenvalues to evaluate our bounds.     

A regularized strong duality for nonsymmetric semidefinite least squares problem

The nonsymmetric semidefinite least squares problem (NSDLS) is to find a nonsymmetric semidefinite matrix which is closest to a given matrix in Frobenius norm. It is an extension of the semidefinite least squares problem (SDLS) and has important application in the area of robotics and automation. In this note, by developing the minimal representation of the underlying cone with the linear constraints, we obtain a regularized strong duality with low-dimensional projection for NSDLS. Further, we study the generalized differential properties and nonsingularity of the first order optimality system about the dual problem. These theoretical results demonstrate that we can solve NSDLS as good as the current Lagrangian dual approaches to SDLS.     

A characterization of positive semidefinite operators on a Hilbert space

In this paper, we show that, under certain conditions, a Hilbert space operator is positive semidefinite whenever it is positive semidefinite plus on a closed convex cone and positive semidefinite on the polar cone (with respect to the operator). This result is a generalization of a result by Han and Mangasarian on matrices.This paper was presented at the 90th Annual Meeting of the American Mathematical Society, Louisville, Kentucky, January 25–28, 1984.     

Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones. We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming.     

Proximal point algorithm with Schur decomposition on the cone of symmetric semidefinite positive matrices

In this work, we propose a proximal algorithm for unconstrained optimization on the cone of symmetric semidefinite positive matrices. It appears to be the first in the proximal class on the set of methods that convert a Symmetric Definite Positive Optimization in Nonlinear Optimization. It replaces the main iteration of the conceptual proximal point algorithm by a sequence of nonlinear programming problems on the cone of diagonal definite positive matrices that has the structure of the positive orthant of the Euclidian vector space. We are motivated by results of the classical proximal algorithm extended to Riemannian manifolds with nonpositive sectional curvature. An important example of such a manifold is the space of symmetric definite positive matrices, where the metrics is given by the Hessian of the standard barrier function −lndet(X). Observing the obvious fact that proximal algorithms do not depend on the geodesics, we apply those ideas to develop a proximal point algorithm for convex functions in this Riemannian metric.     

Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.     

Some characterizations for SOC-monotone and SOC-convex functions

We provide some characterizations for SOC-monotone and SOC-convex functions by using differential analysis. From these characterizations, we particularly obtain that a continuously differentiable function defined in an open interval is SOC-monotone (SOC-convex) of order n ≥ 3 if and only if it is 2-matrix monotone (matrix convex), and furthermore, such a function is also SOC-monotone (SOC-convex) of order n ≤ 2 if it is 2-matrix monotone (matrix convex). In addition, we also prove that Conjecture 4.2 proposed in Chen (Optimization 55:363–385, 2006) does not hold in general. Some examples are included to illustrate that these characterizations open convenient ways to verify the SOC-monotonicity and the SOC-convexity of a continuously differentiable function defined on an open interval, which are often involved in the solution methods of the convex second-order cone optimization.     

On the Semismoothness of Projection Mappings and Maximum Eigenvalue Functions

This paper analyses the properties of the projection mapping over a set defined by a constraint function whose image is possibly a nonpolyhedral convex set. Under some nondegeneracy assumptions, we prove the (strong) semismoothness of the projection mapping. In particular, we derive the strong semismoothness of the projection mapping when the nonpolyhedral convex set under consideration is taken to be the second-order cone or the semidefinite cone. We also derive the semismoothness of the solution to the Moreau–Yosida regularization of the maximum eigenvalue function.     

Subdirect sums of P(P0)-matrices and totally nonnegative matrices

In this paper, the problem of when the sub-direct sum of two strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix is studied. In particular, it is shown that the subdirect sum of overlapping principal submatrices of strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix. It is also established that the 2-subdirect sum of two totally nonnegative matrices is a totally nonnegative matrix under some conditions. It is obtained that a partial totally nonnegative matrix, whose graph of the specified entries is a monotonically labeled 2-chordal graph, has a totally nonnegative completion. Finally, a positive answer to the question (IV) in Fallat and Johnson [Shaun M. Fallat, C.R. Johnson, J.R. Torregrosa, A.M. Urbano, P-matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312 (2000) 73-91] is given for P₀-matrices.     

On Some Properties of Convex Matrix Sets Characterized by P -Matrices and Block P -Matrices

In this paper, we consider convex sets of real matrices and establish criteria characterizing these sets with respect to certain matrix properties of their elements. In particular, we deal with convex sets of P-matrices, block P-matrices and M-matrices, nonsingular and full rank matrices, as well as stable and Schur stable matrices. Our results are essentially based on the notion of a block P-matrix and extend and generalize some recently published results on this topic.