We consider a recent hierarchy of upper approximations proposed by Lasserre (arXiv:1907.097784, 2019) for the minimization of a polynomial f over a compact set K⊆ℝn. This hierarchy relies on using the push-forward measure of the Lebesgue measure on K by the polynomial f and involves univariate sums of squares of polynomials with growing degrees 2r. … Read more
This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood … Read more
We consider quadratic optimization in variables (x,y), 0
While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k times k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, … Read more
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such … Read more
The maximum $k$-colorable subgraph (M$k$CS) problem is to find an induced $k$-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the M$k$CS problem that considers various semidefinite programming relaxations including their theoretical and numerical comparisons. To simplify these relaxations we exploit the symmetry arising from permuting the colors, … Read more
In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are … Read more
We consider both facial and symmetry reduction techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. The combination of facial and symmetry reduction leads to a significant improvement in both numerical stability and running time for both the ADMM and interior … Read more
The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$. In this paper, we show that this method can solve SDPs in polynomial … Read more
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show … Read more