- Award ID(s):
- 1816608
- NSF-PAR ID:
- 10291404
- Date Published:
- Journal Name:
- Springer optimization and its applications
- ISSN:
- 1931-6836
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. This is a continuous and nonconvex reformulation of the rank minimization problem. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal solution is a KKT point. We develop a penalty formulation of the problem. We present calmness results for locally optimal solutions to the penalty formulation. We also develop a proximal alternating linearized minimization (PALM) scheme for the penalty formulation, and investigate the incorporation of a momentum term into the algorithm. Computational results are presented.more » « less
-
Abstract We present a generalization of the notion of neighborliness to non-polyhedral convex cones. Although a definition of neighborliness is available in the non-polyhedral case in the literature, it is fairly restrictive as it requires all the low-dimensional faces to be polyhedral. Our approach is more flexible and includes, for example, the cone of positive-semidefinite matrices as a special case (this cone is not neighborly in general). We term our generalization Terracini convexity due to its conceptual similarity with the conclusion of Terracini’s lemma from algebraic geometry. Polyhedral cones are Terracini convex if and only if they are neighborly. More broadly, we derive many families of non-polyhedral Terracini convex cones based on neighborly cones, linear images of cones of positive-semidefinite matrices, and derivative relaxations of Terracini convex hyperbolicity cones. As a demonstration of the utility of our framework in the non-polyhedral case, we give a characterization based on Terracini convexity of the tightness of semidefinite relaxations for certain inverse problems.
-
We investigate the problem of finding tight inner approximations of large dimensional positive semidefinite (PSD) cones. To solve this problem, we develop a novel decomposition framework of the PSD cone by means of conical combinations of smaller dimensional sub-cones. We show that many inner approximation techniques could be summarized within this framework, including the set of (scaled) diagonally dominant matrices, Factor-width k matrices, and Chordal Sparse matrices. Furthermore, we provide a more flexible family of inner approximations of the PSD cone, where we aim to arrange the sub-cones so that they are maximally separated from each other. In doing so, these approximations tend to occupy large fractions of the volume of the PSD cone. The proposed approach is connected to a classical packing problem in Riemannian Geometry. Precisely, we show that the problem of finding maximally distant sub-cones in an ambient PSD cone is equivalent to the problem of packing sub-spaces in a Grassmannian Manifold. We further leverage the existing computational methods for constructing packings in Grassmannian manifolds to build tighter approximations of the PSD cone. Numerical experiments show how the proposed framework can balance accuracy and computational complexity, to efficiently solve positive-semidefinite programs.more » « less
-
Abstract We present a new variant of the Chambolle–Pock primal–dual algorithm with Bregman distances, analyze its convergence, and apply it to the centering problem in sparse semidefinite programming. The novelty in the method is a line search procedure for selecting suitable step sizes. The line search obviates the need for estimating the norm of the constraint matrix and the strong convexity constant of the Bregman kernel. As an application, we discuss the centering problem in large-scale semidefinite programming with sparse coefficient matrices. The logarithmic barrier function for the cone of positive semidefinite completable sparse matrices is used as the distance-generating kernel. For this distance, the complexity of evaluating the Bregman proximal operator is shown to be roughly proportional to the cost of a sparse Cholesky factorization. This is much cheaper than the standard proximal operator with Euclidean distances, which requires an eigenvalue decomposition.
-
Summary We propose two decompositions that help to summarize and describe high-dimensional tail dependence within the framework of regular variation. We use a transformation to define a vector space on the positive orthant and show that transformed-linear operations applied to regularly-varying random vectors preserve regular variation. We summarize tail dependence via a matrix of pairwise tail dependence metrics that is positive semidefinite; eigendecomposition allows one to interpret tail dependence in terms of the resulting eigenbasis. This matrix is completely positive, and one can easily construct regularly-varying random vectors that share the same pairwise tail dependencies. We illustrate our methods with Swiss rainfall and financial returns data.