Search

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 around the convexity of the data, are simple and apply in very general settings that may be of arbitrary dimensions and may include pointwise and integral constraints, thereby considerably strengthening the existing results. Our conditions are also extended to optimal control problems. In addition, we demonstrate how these results can be applied in nonconvex settings, showing that the occupation measure relaxation is at least as strong as the convexification using the convex envelope; in doing so, we prove that a certain weakening of the occupation measure relaxation is equivalent to the convex envelope. This opens the way to application of the occupation measure relaxation in situations where the convex envelope relaxation is known to be equivalent to the original problem, which includes problems in magnetism and elasticity. [ABSTRACT FROM AUTHOR]

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 hierarchy of Lasserre to obtain bounds on the range of the possible prices. A complementary approach (also from Lasserre) is employed for comparison. We present several numerical examples to demonstrate the viability of our approach. The framework we consider makes it possible to incorporate different kinds of observable data, such as moment information, as well as observable prices of options on the assets of interest. History: Accepted by Antonio Frangioni, area editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the European Union's Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement [Grant 813211 (POEMA)]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1220] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at [http://dx.doi.org/10.5281/zenodo.6602361]. [ABSTRACT FROM AUTHOR]

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 relaxation of the LP which involves pseudo-moments up to a certain degree. Its dual computes a polynomial of same degree which approximates from above the discontinuous indicator function of the set, hence with a typical Gibbs phenomenon which results in a slow convergence of the associated numerical scheme. Drastic improvements have been observed by introducing in the initial LP additional linear moment constraints obtained from a certain application of Stokes' theorem for integration on the set. However and so far there was no rationale to explain this behavior. We provide a refined version of this extended LP formulation. When the set is the smooth super-level set of a single polynomial, we show that the dual of this refined LP has an optimal solution which is a continuous function. Therefore in this dual one now approximates a continuous function by a polynomial, hence with no Gibbs phenomenon, which explains and improves the already observed drastic acceleration of the convergence of the hierarchy. Interestingly, the technique of proof involves recent results on Poisson's partial differential equation (PDE). [ABSTRACT FROM AUTHOR]

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 obtain asymptotically all the other moments by solving a hierarchy of semidefinite relaxations (viewed as moment matrix completion problems) with a specific sparsity-inducing criterion related to a weighted ℓ 1 -norm of the moment sequence of the measure. The resulting sequence of optimal solutions converges to the whole moment sequence of the measure which is shown to be the unique optimal solution of a certain infinite-dimensional linear optimization problem (LP). Then one may recover the function by a recent extraction algorithm based on the Christoffel–Darboux kernel associated with the measure. Finally, the support of such a measure supported on a graph is a meager, very thin (hence sparse) set. Therefore, the LP on measures with this sparsity-inducing criterion can be interpreted as an analogue for infinite-dimensional signals of the LP in super-resolution for (sparse) atomic signals. [ABSTRACT FROM AUTHOR]

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 correlative 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 a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits correlative sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected. [ABSTRACT FROM AUTHOR]

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 solutions to nonlinear hyperbolic PDEs, or using numerical integration from finitely many evaluations of the function. While most of the existing methods construct a piecewise polynomial approximation, we construct a semi-algebraic approximation whose estimation and evaluation can be performed efficiently. An appealing feature of this method is that it deals with nonsmoothness implicitly so that a single scheme can be used to treat smooth or nonsmooth functions without any prior knowledge. On the theoretical side, we prove pointwise convergence almost everywhere as well as convergence in the Lebesgue one norm under broad assumptions. Using more restrictive assumptions, we obtain explicit convergence rates. We illustrate our approach on various examples from control and approximation. In particular, we observe empirically that our method does not suffer from the Gibbs phenomenon when approximating discontinuous functions. [ABSTRACT FROM AUTHOR]

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 usually a polynomial function of design variables, allowing us to build an equivalent non-linear semidefinite programming formulation over a semi-algebraic feasible set. This formulation is subsequently solved using the Lasserre moment-sum-of-squares hierarchy, generating a sequence of outer convex approximations that monotonically converges from below to the optimum of the original problem. Globally optimal solutions can subsequently be extracted using the Curto-Fialkow flat extension theorem. Furthermore, we show that a simple correction to the solutions of the relaxed problems establishes a feasible upper bound, thereby deriving a simple sufficient condition of global ε-optimality. When the original problem possesses a unique minimum, we show that this solution is found with a zero optimality gap in the limit. These theoretical findings are illustrated on several examples of topology optimization of frames and shells, for which we observe that the hierarchy converges in a finite (rather small) number of steps. [ABSTRACT FROM AUTHOR]

We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and continuous 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 (or a class of measures) extremal with respect to the selected functional such as physical measures, ergodic measures, atomic measures (corresponding to, e.g., periodic orbits) or measures absolutely continuous w.r.t. to a given measure. The infinite-dimensional LP is then approximated using a standard hierarchy of finite-dimensional semidefinite programming problems, the solutions of which are truncated moment sequences, which are then used to reconstruct the measure. In particular, we show how to approximate the support of the measure as well as how to construct a sequence of weakly converging absolutely continuous approximations. As a by-product, we present a simple method to certify the nonexistence of an invariant measure, which is an important question in the theory of Markov processes. The presented framework, where a convex functional is minimized or maximized among all invariant measures, can be seen as a generalization of and a computational method to carry out the so-called ergodic optimization, where linear functionals are optimized over the set of invariant measures. Finally, we also describe how the presented framework can be adapted to compute eigenmeasures of the Perron–Frobenius operator. [ABSTRACT FROM AUTHOR]

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. Geometric interpretations and algorithmic consequences are mentioned. [ABSTRACT FROM AUTHOR]

We consider m × s matrices (with m ≥ s ) in a real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in n + m (s - r) n . It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach. [ABSTRACT FROM AUTHOR]

We propose to solve hyperbolic partial differential equations (PDEs) with polynomial flux using a convex optimization strategy.This approach is based on a very weak notion of solution of the nonlinear equation,namely the measure-valued (mv) solution,satisfying a linear equation in the space of Borel measures.The aim of this paper is,first,to provide the conditions that ensure the equivalence between the two formulations and,second,to introduce a method which approximates the infinite-dimensional linear problem by a hierarchy of convex,finite-dimensional,semidefinite programming problems.This result is then illustrated on the celebrated Burgers equation.We also compare our results with an existing numerical scheme,namely the Godunov scheme. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuous- and discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to the Lebesgue measure. Then, we focus on the approximation of the support of an invariant measure which is singular with respect to the Lebesgue measure. Each problem is handled through an appropriate reformulation into a conic optimization problem over measures, solved in practice with two hierarchies of finite-dimensional semidefinite moment-sum-of-square relaxations, also called Lasserre hierarchies. Under specific assumptions, the first Lasserre hierarchy allows to approximate the moments of an absolutely continuous invariant measure as close as desired and to extract a sequence of polynomials converging weakly to the density of this measure. The second Lasserre hierarchy allows to approximate as close as desired in the Hausdorff metric the support of a singular invariant measure with the level sets of the Christoffel polynomials associated to the moment matrices of this measure. We also present some application examples together with numerical results for several dynamical systems admitting either absolutely continuous or singular invariant measures. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the reachable set of a discrete-time polynomial system from a semialgebraic set of initial conditions under general semialgebraic set constraints. Assuming inclusion in a given simple set like a box or an ellipsoid, we provide a method to compute certified outer approximations of the reachable set. The proposed method consists of building a hierarchy of relaxations for an infinite-dimensional moment problem. Under certain assumptions, the optimal value of this problem is the volume of the reachable set and the optimum solution is the restriction of the Lebesgue measure on this set. Then, one can outer approximate the reachable set as closely as desired with a hierarchy of super level sets of increasing degree polynomials. For each fixed degree, finding the coefficients of the polynomial boils down to computing the optimal solution of a convex semidefinite program. When the degree of the polynomial approximation tends to infinity, we provide strong convergence guarantees of the super level sets to the reachable set. We also present some application examples together with numerical results. [ABSTRACT FROM AUTHOR]

This document describes our freely distributed Maple library SPECTRA, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities with symbolic computation in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. [ABSTRACT FROM AUTHOR]

Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. Under certain assumptions, we show that the asymptotic rate of this convergence is at least O(1/loglogd) in general and O(1/logd) provided that the semialgebraic set is defined by a single inequality. [ABSTRACT FROM AUTHOR]

We propose a tutorial on relaxations and weak formulations of optimal control with their semidefinite approximations. We present this approach solely through the prism of positivity certificates which we consider to be the most accessible for a broad audience, in particular in the engineering and robotics communities. This simple concept allows us to express very concisely powerful approximation certificates in control. The relevance of this technique is illustrated on three applications: region of attraction approximation, direct optimal control and inverse optimal control, for which it constitutes a common denominator. In a first step, we highlight the core mechanisms underpinning the application of positivity in control and how they appear in the different control applications. This relies on simple mathematical concepts and gives a unified treatment of the applications considered. This presentation is based on the combination and simplification of published materials. In a second step, we describe briefly relations with broader literature, in particular, occupation measures and Hamilton–Jacobi–Bellman equation which are important elements of the global picture. We describe the Sum-Of-Squares (SOS) semidefinite hierarchy in the semialgebraic case and briefly mention its convergence properties. Numerical experiments on a classical example in robotics, namely the nonholonomic vehicle, illustrate the concepts presented in the text for the three applications considered. [ABSTRACT FROM AUTHOR]

We investigate the multi-dimensional super resolution problem on closed semi-algebraic domains for various sampling schemes such as Fourier or moments. We present a new semidefinite programming (SDP) formulation of the \ell 1 -minimization in the space of Radon measures in the multi-dimensional frame on semi-algebraic sets. While standard approaches have focused on SDP relaxations of the dual program (a popular approach is based on Gram matrix representations), this paper introduces an exact formulation of the primal \ell 1 -minimization exact recovery problem of super resolution that unleashes standard techniques (such as moment-sum-of-squares hierarchies) to overcome intrinsic limitations of previous works in the literature. Notably, we show that one can exactly solve the super resolution problem in dimension greater than 2 and for a large family of domains described by semi-algebraic sets. [ABSTRACT FROM PUBLISHER]

Converging hierarchies of finite-dimensional semi-definite relaxations have been proposed for state-constrained optimal control problems featuring oscillation phenomena, by relaxing controls as Young measures. These semi-definite relaxations were later on extended to optimal control problems depending linearly on the control input and typically featuring concentration phenomena, interpreting the control as a measure of time with a discrete singular component modeling discontinuities or jumps of the state trajectories. In this contribution, we use measures introduced originally by DiPerna and Majda in the partial differential equations literature to model simultaneously, and in a unified framework, possible oscillation and concentration effects of the optimal control policy. We show that hierarchies of semi-definite relaxations can also be constructed to deal numerically with nonconvex optimal control problems with polynomial vector field and semialgebraic state constraints. [ABSTRACT FROM AUTHOR]

The efficiency of modern optimization methods, coupled with increasing computational resources, has led to the possibility of real-time optimization algorithms acting in safety-critical roles. There is a considerable body of mathematical proofs on on-line optimization algorithms which can be leveraged to assist in the development and verification of their implementation. In this paper, we demonstrate how theoretical proofs of real-time optimization algorithms can be used to describe functional properties at the level of the code, thereby making it accessible for the formal methods community. The running example used in this paper is a generic semi-definite programming solver. Semi-definite programs can encode a wide variety of optimization problems and can be solved in polynomial time at a given accuracy. We describe a top-down approach that transforms a high-level analysis of the algorithm into useful code annotations. We formulate some general remarks on how such a task can be incorporated into a convex programming autocoder. We then take a first step towards the automatic verification of the optimization program by identifying key issues to be addressed in future work. [ABSTRACT FROM AUTHOR]

Let A(x) = A0 + x1A1 +...+xnAn be a linear matrix, or pencil, generated by given symmetric matrices A0,A1,...,An of size m with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semialgebraic set called spectrahedron, described by a linear matrix inequality. We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree d of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear Bézout bound of d. When m (resp., n) is fixed, such a bound, and hence the complexity, is polynomial in n (resp., m). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is to identify explicit classes of locally controllable second-order systems and optimization functionals for which optimal control problems can be solved analytically, assuming that a differentiable optimal cost-to-go function exists for such control problems. An additional contribution of the paper is to obtain a Lyapunov function for the same classes of systems. The paper addresses the Lie point symmetries of the Hamilton--Jacobi--Bellman (HJB) equation for optimal control of second-order nonlinear control systems that are affine in a single input and for which the cost is quadratic in the input. It is shown that if there exists a dilation symmetry of the HJB equation for optimal control problems in this class, this symmetry can be used to obtain a solution. It is concluded that when the cost on the state preserves the dilation symmetry, solving the optimal control problem is reduced to finding the solution to a first-order ordinary differential equation. For some cases where the cost on the state breaks the dilation symmetry, the paper also presents an alternative method to find analytical solutions of the HJB equation corresponding to additive control inputs. The relevance of the proposed methodologies is illustrated in several examples for which analytical solutions are found, including the Van der Pol oscillator and mass--spring systems. Furthermore, it is proved that in the well-known case of a linear quadratic regulator, the quadratic cost is precisely the cost that preserves the dilation symmetry of the equation. [ABSTRACT FROM AUTHOR]

We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be relatively large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how public-domain software can be used to model and solve such problems. Finally, we also compare with the epigraph approach and the BARON software. [ABSTRACT FROM AUTHOR]

A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $$K$$ described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J. B. Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, we show that there is no duality gap between each primal and dual SDP problem in Lasserre's hierarchy, provided one of the constraints in the description of set $$K$$ is a ball constraint. Our proof uses elementary results on SDP duality, and it does not assume that $$K$$ has a strictly feasible point. [ABSTRACT FROM AUTHOR]

Given a compact semialgebraic set S ⊂ Rn and a polynomial map f : Rn → Rm, we consider the problem of approximating the image set F = f (S) ⊂ Rm. This includes in particular the projection of S on Rm for n ≥ m. Assuming that F ⊂ B, with B ⊂ Rm being a "simple" set (e.g., a box or a ball), we provide two methods to compute certified outer approximations of F. Method 1 exploits the fact that F can be defined with an existential quantifier, while Method 2 computes approximations of the support of image measures. The two methods output a sequence of superlevel sets defined with a single polynomial that yield explicit outer approximations of F. Finding the coefficients of this polynomial boils down to computing an optimal solution of a convex semidefinite program. We provide guarantees of strong convergence to F in L1 norm on B, when the degree of the polynomial approximation tends to infinity. Several examples of applications are provided, together with numerical experiments. [ABSTRACT FROM AUTHOR]

The fundamental matrix can be estimated from point matches. The current gold standard is to bootstrap the eight-point algorithm and two-view projective bundle adjustment. The eight-point algorithm first computes a simple linear least squares solution by minimizing an algebraic cost and then projects the result to the closest rank-deficient matrix. We propose a single-step method that solves both steps of the eight-point algorithm. Using recent results from polynomial global optimization, our method finds the rank-deficient matrix that exactly minimizes the algebraic cost. In this special case, the optimization method is reduced to the resolution of very short sequences of convex linear problems which are computationally efficient and numerically stable. The current gold standard is known to be extremely effective but is nonetheless outperformed by our rank-constrained method for bootstrapping bundle adjustment. This is here demonstrated on simulated and standard real datasets. With our initialization, bundle adjustment consistently finds a better local minimum (achieves a lower reprojection error) and takes less iterations to converge. [ABSTRACT FROM AUTHOR]

We characterize the maximum controlled invariant (MCI) set for discrete- as well as continuous-time nonlinear dynamical systems as the solution of an infinite-dimensional linear programming problem. For systems with polynomial dynamics and compact semialgebraic state and control constraints, we describe a hierarchy of finite-dimensional linear matrix inequality (LMI) relaxations whose optimal values converge to the volume of the MCI set; dual to these LMI relaxations are sum-of-squares (SOS) problems providing a converging sequence of outer approximations to the MCI set. The approach is simple and readily applicable in the sense that the approximations are the outcome of a single semidefinite program with no additional input apart from the problem description. A number of numerical examples illustrate the approach. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the unknown density $$u\in L^2(\Omega ,\lambda )$$ of a measure $$\mu $$ on $$\Omega \subset \mathbb {R}^n$$ , absolutely continuous with respect to some given reference measure $$\lambda $$ , only from the knowledge of finitely many moments of $$\mu $$ . Given $$d\in \mathbb {N}$$ and moments of order $$d$$ , we provide a polynomial $$p_d$$ which minimizes the mean square error $$\int (u-p)^2d\lambda $$ over all polynomials $$p$$ of degree at most $$d$$ . If there is no additional requirement, $$p_d$$ is obtained as solution of a linear system. In addition, if $$p_d$$ is expressed in the basis of polynomials that are orthonormal with respect to $$\lambda $$ , its vector of coefficients is just the vector of given moments and no computation is needed. Moreover $$p_d\rightarrow u$$ in $$L^2(\Omega ,\lambda )$$ as $$d\rightarrow \infty $$ . In general nonnegativity of $$p_d$$ is not guaranteed even though $$u$$ is nonnegative. However, with this additional nonnegativity requirement one obtains analogous results but computing $$p_d\ge 0$$ that minimizes $$\int (u-p)^2d\lambda $$ now requires solving an appropriate semidefinite program. We have tested the approach on some applications arising from the reconstruction of geometrical objects and the approximation of solutions of nonlinear differential equations. In all cases our results are significantly better than those obtained with the maximum entropy technique for estimating $$u$$ . [ABSTRACT FROM AUTHOR]