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

Tractable semi-algebraic approximation using Christoffel-Darboux kernel

We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy … Read more

Exploiting Sparsity for Semi-Algebraic Set Volume Computation

We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is … Read more

Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more