We propose to approximate a (possibly discontinuous) multivariate function f(x) on a compact set by the partial minimizer arg min_y p(x,y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when … Read more
In this paper, we study the facial structure of the linear image of a cone. We define the singularity degree of a face of a cone to be the minimum number of steps it takes to expose it using exposing vectors from the dual cone. We show that the singularity degree of the linear image … Read more
Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then … Read more
Motivated by encouraging numerical results in the literature, in this note we consider two specific variants of the trust-region subproblem and provide exact semidefinite representable reformulations. The first is over the intersection of two balls; the second is over the intersection of a ball and a special second-order conic representable set. Different from the technique … Read more
In the literature, superlinear convergence of implementable polynomial-time interior point algorithms to solve semi-definite programs (SDPs) can only be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms, or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems, when a suitable initial iterate is … Read more
A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone, i.e., for every pair of points in the interior of the cone, there exists a cone automorphism that maps one point to the other. Cones that are homogeneous and self-dual are called symmetric. The symmetric cones include the … Read more
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more
Sparse Principal Component Analysis is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. At its heart, this involves solving a sparsity and orthogonality constrained convex maximization problem, which is extremely computationally challenging. Most existing work address sparse PCA via heuristics … Read more
We study semidefinite programming (SDP) relaxations for the NP-hard problem of globally optimizing a quadratic function over the Stiefel manifold. We introduce a strengthened relaxation based on two recent ideas in the literature: (i) a tailored SDP for objectives with a block-diagonal Hessian; (ii) and the use of the Kronecker matrix product to construct SDP relaxations. Using synthetic instances on … Read more
We report the experimental results on certifying 1% global optimality of solutions of AC-OPF instances from PGLiB via the CS-TSSOS hierarchy — a moment-SOS based hierarchy that exploits both correlative and term sparsity, which can provide tighter SDP relaxations than Shor’s relaxation. Our numerical experiments demonstrate that the CS-TSSOS hierarchy scales well with the problem … Read more