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

Occupation measure relaxations in variational problems: the role of convexity

This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming reformulation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving … Read more

Polynomial argmin for recovery and approximation of multivariate discontinuous functions

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

Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives

In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more

Time-Varying Semidefinite Programming: Geometry of the Trajectory of Solutions

In many applications, solutions of convex optimization problems must be updated on-line, as functions of time. In this paper, we consider time-varying semidefinite programs (TV-SDP), which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on time. We are interested in the geometry of the solution (output data) trajectory, defined as … Read more

Moment-SOS hierarchy and exit time of stochastic processes

The moment sum of squares (moment-SOS) hierarchy produces sequences of upper and lower bounds on functionals of the exit time solution of a polynomial stochastic differential equation with polynomial constraints, at the price of solving semidefinite optimization problems of increasing size. In this note we use standard results from elliptic partial differential equation analysis to … Read more

Graph Recovery From Incomplete Moment Information

We investigate a class of moment problems, namely recovering a measure supported on the graph of a function from partial knowledge of its moments, as for instance in some problems of optimal transport or density estimation. We show that the sole knowledge of first degree moments of the function, namely linear measurements, is sufficient to … Read more

Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy

The design of minimum-compliance bending-resistant structures with continuous cross-section parameters is a challenging task because of its inherent non-convexity. Our contribution develops a strategy that facilitates computing all guaranteed globally optimal solutions for frame and shell structures under multiple load cases and self-weight. To this purpose, we exploit the fact that the stiffness matrix is … Read more

Stokes, Gibbs and volume computation of semi-algebraic sets

We consider the problem of computing the Lebesgue volume of compact basic semi-algebraic sets. In full generality, it can be approximated as closely as desired by a converging hierarchy of upper bounds obtained by applying the Moment-SOS (sums of squares) methodology to a certain infinite-dimensional linear program (LP). At each step one solves a semidefinite … Read more

Dual optimal design and the Christoffel-Darboux polynomial

The purpose of this short note is to show that the Christoffel-Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Article Download View Dual optimal design and the Christoffel-Darboux polynomial