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.     

Cone complementarity problems with finite solution sets

We introduce the notion of a complementary cone and a nondegenerate linear transformation and characterize the finiteness of the solution set of a linear complementarity problem over a closed convex cone in a finite dimensional real inner product space. In addition to the above, other geometrical properties of complementary cones have been explored.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

Optimization over structured subsets of positive semidefinite matrices via column generation

We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

The solution set structure of monotone linear complementarity problems over second-order cone

The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique.     

Semidefinite programming and arithmetic circuit evaluation

We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm.We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP—an old open problem in the field of mathematical programming.     

On the Analyticity of Underlying HKM Paths for Monotone Semidefinite Linear Complementarity Problems

An interior point method (IPM) defines a search direction at an interior point of the feasible region. These search directions form a direction field, which in turn defines a system of ordinary differential equations (ODEs). The solutions of the system of ODEs are called off-central paths, underlying paths lying in the interior of the feasible region. It is known that not all off-central paths are analytic, whether w.r.t. μ or , where μ represents the duality gap, at a solution of a given semidefinite linear complementarity problem, SDLCP (Sim and Zhao, Math. Program. 110:475–499, 2007). In Sim and Zhao (J. Optim. Theory Appl. 137:11–25, 2008), we give a necessary and sufficient condition for when an off-central path is analytic as a function of at a solution of a general SDLCP. It is then natural to ask about the analyticity of a SDLCP off-central path at a solution, as a function of μ. We investigate this in the current paper. Again, we work under the assumption that the given SDLCP satisfies strict complementarity condition.     

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.     

Analyticity of weighted central paths and error bounds for semidefinite programming

The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual solutions to converge linearly with their duality gaps. This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC.     

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.     

Characterizations for solidness of dual cones with applications

In this paper, some characterizations for the solidness of dual cones are established. As applications, we prove that a Banach space is reflexive if it contains a solid pointed closed convex cone having a weakly compact base, and prove an analogue of a Karamardian’s result for the linear complementarity problem in reflexive Banach spaces. The uniqueness of the solution of the linear complementarity problem is also discussed.     

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.     

Asymptotic Behavior of Helmberg-Kojima-Monteiro (HKM) Paths in Interior-Point Methods for Monotone Semidefinite Linear Complementarity Problems: General Theory

An interior-point method (IPM) defines a search direction at each interior point of the feasible region. These search directions form a direction field, which in turn gives rise to a system of ordinary differential equations (ODEs). Thus, it is natural to define the underlying paths of the IPM as the solutions of the system of ODEs. In Sim and Zhao (Math. Program. Ser. A, [2007], to appear), these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to the given monotone semidefinite linear complementarity problem (SDLCP). Off-central paths for a simple example are also studied in Sim and Zhao (Math. Program. Ser. A, [2007], to appear) and their asymptotic behavior near the solution of the example is analyzed. In this paper, which is an extension of Sim and Zhao (Math. Program. Ser. A, [2007], to appear), we study the asymptotic behavior of the off-central paths for general SDLCPs using the dual HKM direction. We give a necessary and sufficient condition for when an off-central path is analytic as a function of at a solution of the SDLCP. Then, we show that, if the given SDLCP has a unique solution, the first derivative of its off-central path, as a function of , is bounded. We work under the assumption that the given SDLCP satisfies the strict complementarity condition. This research was done during the first author’s Ph.D. study at the Department of Mathematics, National University of Singapore, and as a Research Engineer at the NUS Business School. The second author’s work was supported in part by NUS Academic Research Grant R-146-000-084-112. For technical details of the paper, please refer to The Logistics Institute—Asia Pacific Internal Report. See also .     

Iterative methods for nonlinear complementarity problems on isotone projection cones

In this paper we present a recursion related to a nonlinear complementarity problem defined by a closed convex cone in a Hilbert space and a continuous mapping defined on the cone. If the recursion is convergent, then its limit is a solution of the nonlinear complementarity problem. In the case of isotone projection cones sufficient conditions are given for the mapping so that the recursion to be convergent.     

Cartesian P-property and Its Applications to the Semidefinite Linear Complementarity Problem

We introduce a Cartesian P-property for linear transformations between the space of symmetric matrices and present its applications to the semidefinite linear complementarity problem (SDLCP). With this Cartesian P-property, we show that the SDLCP has GUS-property (i.e., globally unique solvability), and the solution map of the SDLCP is locally Lipschitzian with respect to input data. Our Cartesian P-property strengthens the corresponding P-properties of Gowda and Song [15] and allows us to extend several numerical approaches for monotone SDLCPs to solve more general SDLCPs, namely SDLCPs with the Cartesian P-property. In particular, we address important theoretical issues encountered in those numerical approaches, such as issues related to the stationary points in the merit function approach, and the existence of Newton directions and boundedness of iterates in the non-interior continuation method of Chen and Tseng [6]. This work is supported by the annual grant A2004/23 of University of Southampton.