Exact Matrix Completion via High-Rank Matrices in Sum-of-Squares Relaxations

We study exact matrix completion from partially available data with hidden connectivity patterns. Exact matrix completion was shown to be possible recently by Cosse and Demanet in 2021 with Lasserre’s relaxation using the trace of the variable matrix as the objective function with given data structured in a chain format. In this study, we introduce … Read more

Semidefinite programming by Projective Cutting-Planes

\(\) Seeking tighter relaxations of combinatorial optimization problems, semidefinite programming is a generalization of linear programming that offers better bounds and is still polynomially solvable. Yet, in practice, a semidefinite program is still significantly harder to solve than a similar-size Linear Program (LP). It is well-known that a semidefinite program can be written as an … Read more

Higher-Order Newton Methods with Polynomial Work per Iteration

\(\) We present generalizations of Newton’s method that incorporate derivatives of an arbitrary order \(d\) but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our \(d^{\text{th}}\)-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the \(d^{\text{th}}\)-order Taylor expansion of the function we wish … Read more

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method

\(\) The simplified Wasserstein barycenter problem consists in selecting one point from \(k\) given sets, each set consisting of \(n\) points, with the aim of minimizing the sum of distances to the barycenter of the \(k\) points chosen. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance … Read more

Geometry of exactness of moment-SOS relaxations for polynomial optimization

The moment-SOS (sum of squares) hierarchy is a powerful approach for solving globally non-convex polynomial optimization problems (POPs) at the price of solving a family of convex semidefinite optimization problems (called moment-SOS relaxations) of increasing size, controlled by an integer, the relaxation order. We say that a relaxation of a given order is exact if … Read more

On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

Affine FR : an effective facial reduction algorithm for semidefinite relaxations of combinatorial problems

\(\) We develop a new method called \emph{affine FR} for recovering Slater’s condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing … Read more

A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients

This paper proposes a real moment-HSOS hierarchy for complex polynomial optimization problems with real coefficients. We show that this hierarchy provides the same sequence of lower bounds as the complex analogue, yet is much cheaper to solve. In addition, we prove that global optimality is achieved when the ranks of the moment matrix and certain … Read more

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems with application to linear matrix inequalities

In the literature, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual and the NT direction, to solve semi-definite programs (SDPs) can be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms [10], or (ii) considering special classes of SDPs, such … Read more

AI Hilbert: A New Paradigm for Scientific Discovery by Unifying Data and Background Knowledge

The discovery of scientific formulae that parsimoniously explain natural phenomena and align with existing background theory is a key goal in science. Historically, scientists have derived natural laws by manipulating equations based on existing¬†knowledge, forming new equations, and verifying them experimentally. In recent years, data-driven scientific discovery has emerged as a viable competitor in settings¬†with … Read more