Abstract 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).

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 ].

Given symmetric matrices A0,A1,…,An of size m with rational entries, the set of real vectors x=(x1,…,xn) such that the matrix A0+x1A1+⋯+xnAn has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed.

Classical control of cyber-physical systems used to rely on basic linear controllers. These controllers provided a safe and robust behavior but lack the ability to perform more complex controls such as aggressive maneuvering or performing fuel-efficient controls. Another approach called optimal control is capable of computing such difficult trajectories but lacks the ability to adapt to dynamic changes in the environment. In both cases, the control was designed offline, relying on more or less complex algorithms to find the appropriate parameters. More recent kinds of approaches such as Linear Model-Predictive Control (MPC) rely on the online use of convex optimization to compute the best control at each sample time. In these settings optimization algorithms are specialized for the specific control problem and embed on the device. This paper proposes to revisit the code generation of an interior point method (IPM) algorithm, an efficient family of convex optimization, focusing on the proof of its implementation at code level. Our approach relies on the code specialization phase to produce additional annotations formalizing the intended specification of the algorithm. Deductive methods are then used to prove automatically the validity of these assertions. Since the algorithm is complex, additional lemmas are also produced, allowing the complete proof to be checked by SMT solvers only. This work is the first to address the effective formal proof of an IPM algorithm. The approach could also be generalized more systematically to code generation frameworks, producing proof certificate along the code, for numerical intensive software.

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 l1-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 l1-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.

Let H0, …, H n be m x m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix H(x) = H0+x1H_1+…+xnHn and the problem of computing sample points in each connected component of the real algebraic set defined by the rank constraint rank}(H(x))≤ r, for a given integer r ≤ m-1. Computing sample points in real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general real algebraic sets: it tackles examples that are out of reach of the state-of-the-art.

The need to relate measurements made by a camera to a different known coordinate system arises in many engineering applications. Historically, it appeared for the first time in the connection with cameras mounted on robotic systems. This problem is commonly known as hand-eye calibration. In this paper, we present several formulations of hand-eye calibration that lead to multivariate polynomial optimization problems. We show that the method of convex linear matrix inequality (LMI) relaxations can be used to effectively solve these problems and to obtain globally optimal solutions. Further, we show that the same approach can be used for the simultaneous hand-eye and robot-world calibration. Finally, we validate the proposed solutions using both synthetic and real datasets.

Variability in the analogue components of integrators in cascaded 2-1 sigma-delta modulators causes imperfect cancellation of first stage quantization noise, and reduced signal-to-noise ratio in analogue-to-digital converters. Design of robust matching filters based on low-frequency weighted convex optimization over uncertain linearized representations are mathematically very complex and computationally intensive, and offer little insight into the solution. This letter describes a design method based on formal optimization of a low-frequency uncertain linearized model of the modulator, and leads to a simple intuitive result which can shed light on the more complex models. Simulation results confirm the optimal properties of the filter.

The set of controllers stabilizing a linear system is generally non-convex in the parameter space. In the case of two-parameter controller design (e.g. PI control or static output feedback with one input and two outputs), we observe however that quite often for benchmark problem instances, the set of stabilizing controllers seems to be convex. In this note we use elementary techniques from real algebraic geometry (resultants and Bezoutian matrices) to explain this phenomenon. As a byproduct, we derive a convex linear matrix inequality (LMI) formulation of two-parameter fixed-order controller design problem, when possible.

Uncertainty in the integrators of 2-1 sigma-delta modulators causes imperfect cancellation of first stage quantization noise, and reduces signal-to-noise ratio in analogue-to-digital converters. Design of robust matching filters based on convex optimization over uncertain linearized state-space representations gives complicated models and high-order designs. This letter describes a polynomial design method leading to simpler multilinear models and fixed-order filters. The modulators are cast as a polynomial polytope, and filters satisfying an Hinfinbound arise from solving linear matrix inequalities (LMIs). Results at low frequency show the proposed filter outperforming the nominal one, with a performance close to the estimated optimum.

We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or nonoptimality - or a combination of both - we pursue the goal of achieving global solutions of the statistically optimal cost-function. Our approach is based on a hierarchy of convex relaxations to solve nonconvex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality, or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum without any problem splitting. Global optimality is detected and isolated optimal solutions are extracted automatically. Numerical experiments show that for most of the small-scale problems described in the literature, the global optimum is reached at low computational cost.