This paper addresses the following three topics: positive semidefinite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidefinite programming as unifying theme. Our main contribution is a sufficient condition for constructing partial psd matrices which admit a unique completion to a … Read more
VSDP is a software package that is designed for the computation of verified results in conic programming. The current version of VSDP supports the constraint cone consisting of the product of semidefinite cones, second-order cones and the nonnegative orthant. It provides functions for computing rigorous error bounds of the true optimal value, verified enclosures of … Read more
Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more
We apply theta body relaxations to the $K_i$ cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all $K_i$-$p$-hole facets are valid, addressing an open question of Conforti et al \cite{conforti}. For the triangle free problem, we show for $K_n$ that … Read more
Triangulation of a three-dimensional point from $n\ge 2$ two-dimensional images can be formulated as a quadratically constrained quadratic program. We propose an algorithm to extract candidate solutions to this problem from its semidefinite programming relaxations. We then describe a sufficient condition and a polynomial time test for certifying when such a solution is optimal. This … Read more
In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for … Read more
We give theorems that can be used to upper bound the densities of packings of different spherical caps in the unit sphere and of translates of different convex bodies in Euclidean space. These theorems extend the linear programming bounds for packings of spherical caps and of convex bodies through the use of semidefinite programming. We … Read more
The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more
We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of … Read more
We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more