Search

Christoffel polynomials are classical tools from approximation theory. They can be used to estimate the (compact) support of a measure $\mu$ on $\mathbb{R}^d$ based on its low-degree moments. Recently, they have been applied to problems in data science, including outlier detection and support inference. A major downside of Christoffel polynomials in such applications is the fact that, in order to compute their coefficients, one must invert a matrix whose size grows rapidly with the dimension $d$. In this paper, we propose a modification of the Christoffel polynomial which is significantly cheaper to compute, but retains many of its desirable properties. Our approach relies on sparsity of the underlying measure $\mu$, described by a graphical model. The complexity of our modification depends on the treewidth of this model., Comment: 21 pages, 1 figure

We introduce a variant of the D-optimal design of experiments problem with a more general information matrix that takes into account the representation of the design space S. The main motivation is that if S $\subset$ R d is the unit ball, the unit box or the canonical simplex, then remarkably, for every dimension d and every degree n, the equilibrium measure of S (in pluripotential theory) is an optimal solution. Equivalently, for each degree n, the unique optimal solution is the vector of moments (up to degree 2n) of the equilibrium measure of S. Hence nding an optimal design reduces to nding a cubature for the equilibrium measure, with atoms in S, positive weights, and exact up to degree 2n. In addition, any resulting sequence of atomic D-optimal measures converges to the equilibrium measure of S for the weak-star topology, as n increases. Links with Fekete sets of points are also discussed. More general compact basic semialgebraic sets are also considered, and a previously developed two-step design algorithm is easily adapted to this new variant of D-optimal design problem.

We introduce an infinite-dimensional version of the Christoffel function, where now (i) its argument lies in a Hilbert space of functions, and (ii) its associated underlying measure is supported on a compact subset of the Hilbert space. We show that it possesses the same crucial property as its finite-dimensional version to identify the support of the measure (and so to detect outliers). Indeed, the growth of its reciprocal with respect to its degree is at least exponential outside the support of the measure and at most polynomial inside. Moreover, for a fixed degree, its computation mimics that of the finite-dimensional case, but now the entries of the moment matrix associated with the measure are moments of moments. To illustrate the potential of this new tool, we consider the following application. Given a data base of registered reference trajectories, we consider the problem of detecting whether a newly acquired trajectory is abnormal (or out of distribution) with respect to the data base. As in the finite-dimensional case, we use the infinite-dimensional Christoffel function as a score function to detect outliers and abnormal trajectories. A few numerical examples are provided to illustrate the theory.

We consider a new multivariate generalization of the classical monic (univariate) Chebyshev polynomial that minimizes the uniform norm on the interval $[-1,1]$. Let $\Pi^*_n$ be the subset of polynomials of degree at most $n$ in $d$ variables, whose homogeneous part of degree $n$ has coefficients summing up to $1$. The problem is determining a polynomial in $\Pi^*_n$ with the smallest uniform norm on a domain $\Omega$, which we call a least Chebyshev polynomial (associated with $\Omega$). Our main result solves the problem for $\Omega$ belonging to a non-trivial class of domains, defined by a property of its diagonal, and establishes the remarkable result that a least Chebyshev polynomial can be given via the classical, univariate, Chebyshev polynomial. In particular, the solution can be independent of the dimension. The result is valid for fairly general domains that can be non-convex and highly irregular.

This paper explores methods for verifying the properties of Binary Neural Networks (BNNs), focusing on robustness against adversarial attacks. Despite their lower computational and memory needs, BNNs, like their full-precision counterparts, are also sensitive to input perturbations. Established methods for solving this problem are predominantly based on Satisfiability Modulo Theories and Mixed-Integer Linear Programming techniques, which are characterized by NP complexity and often face scalability issues. We introduce an alternative approach using Semidefinite Programming relaxations derived from sparse Polynomial Optimization. Our approach, compatible with continuous input space, not only mitigates numerical issues associated with floating-point calculations but also enhances verification scalability through the strategic use of tighter first-order semidefinite relaxations. We demonstrate the effectiveness of our method in verifying robustness against both $\|.\|_\infty$ and $\|.\|_2$-based adversarial attacks., Comment: 22 pages, 2 figures, 7 tables

This article is concerned with an extension of univariate Chebyshev polynomials of the first kind to the multivariate setting, where one chases best approximants to specific monomials by polynomials of lower degree relative to the uniform norm. Exploiting the Moment-SOS hierarchy, we devise a versatile semidefinite-programming-based procedure to compute such best approximants, as well as associated signatures. Applying this procedure in three variables leads to the values of best approximation errors for all monomials up to degree six on the euclidean ball, the simplex, and the cross-polytope. Furthermore, inspired by numerical experiments, we obtain explicit expressions for Chebyshev polynomials in two cases unresolved before, namely for the monomial $x_1^2 x_2^2 x_3$ on the euclidean ball and for the monomial $x_1^2 x_2 x_3$ on the simplex.

Given a determinate (multivariate) probability measure $\mu$, we characterize Gaussian mixtures $\nu\_\phi$ which minimize the Wasserstein distance $W\_2(\mu,\nu\_\phi)$ to $\mu$ when the mixing probability measure $\phi$ on the parameters $(m,\Sigma)$ of the Gaussians is supported on a compact set $S$.(i) We first show that such mixtures are optimal solutions of a particular optimal transport (OT) problem where the marginal $\nu\_{\phi}$ of the OT problem is also unknown via the mixing measure variable $\phi$. Next (ii) by using a well-known specific property of Gaussian measures, this optimal transport is then viewed as a Generalized Moment Problem (GMP) and if the set $S$ of mixture parameters $(m,\Sigma)$ is a basic compact semi-algebraic set, we provide a "mesh-free" numerical scheme to approximate as closely as desired the optimal distance by solving a hierarchy of semidefinite relaxations of increasing size. In particular, we neither assume that the mixing measure is finitely supported nor that the variance is the same for all components. If the original measure $\mu$ is not a Gaussian mixture with parameters $(m,\Sigma)\in S$, then a strictly positive distance is detected at a finite step of the hierarchy. If the original measure $\mu$ is a Gaussian mixture with parameters $(m,\Sigma)\in S$, then all semidefinite relaxations of the hierarchy have same zero optimal value. Moreover if the mixing measure is atomic with finite support, its components can sometimes be extracted from an optimal solution at some semidefinite relaxation of the hierarchy when Curto & Fialkow's flatness condition holds for some moment matrix.

Given two measures $\mu$, $\nu$ on Rd that satisfy Carleman's condition, we provide a numerical scheme to approximate as closely as desired the total variation distance between $\mu$ and $\nu$. It consists of solving a sequence (hierarchy) of convex relaxations whose associated sequence of optimal values converges to the total variation distance, an additional illustration of the versatility of the Moment-SOS hierarchy. Indeed each relaxation in the hierarchy is a semidefinite program whose size increases with the number of involved moments. It has an optimal solution which is a couple of degree-2n pseudo-moments which converge, as n grows, to moments of the Hahn-Jordan decomposition of $\mu$-$\nu$.

Set-membership estimation (SME) outputs a set estimator that guarantees to cover the groundtruth. Such sets are, however, defined by (many) abstract (and potentially nonconvex) constraints and therefore difficult to manipulate. We present tractable algorithms to compute simple and tight overapproximations of SME in the form of minimum enclosing ellipsoids (MEE). We first introduce the hierarchy of enclosing ellipsoids proposed by Nie and Demmel (2005), based on sums-of-squares relaxations, that asymptotically converge to the MEE of a basic semialgebraic set. This framework, however, struggles in modern control and perception problems due to computational challenges. We contribute three computational enhancements to make this framework practical, namely constraints pruning, generalized relaxed Chebyshev center, and handling non-Euclidean geometry. We showcase numerical examples on system identification and object pose estimation., Comment: Accepted to 6th Learning for Dynamics and Control (L4DC) as oral presentation

We extend the polynomial Pell's equation satisfied by univariate Chebyshev polynomials on [--1, 1] from one variable to several variables, using orthogonal polynomials on regular domains that include cubes, balls, and simplexes of arbitrary dimension. Moreover, we show that such an equation is strongly connected (i) to a certificate of positivity (from real algebraic geometry) on the domain, as well as (ii) to the Christoffel functions of the equilibrium measure on the domain. In addition, the solution to Pell's equation reflects an extremal property of orthonormal polynomials associated with an entropy-like criterion., Comment: To appear in Transactions of the Amercian Mathematical Society

AC-OPF (Alternative Current Optimal Power Flow)aims at minimizing the operating costs of a power gridunder physical constraints on voltages and power injections.Its mathematical formulation results in a nonconvex polynomial optimizationproblem which is hard to solve in general,but that can be tackled by a sequence of SDP(Semidefinite Programming) relaxationscorresponding to the steps of the moment-SOS (Sums-Of-Squares) hierarchy.Unfortunately, the size of these SDPs grows drastically in the hierarchy,so that even second-order relaxationsexploiting the correlative sparsity pattern of AC-OPFare hardly numerically tractable for largeinstances -- with thousands of power buses.Our contribution lies in a new sparsityframework, termed minimal sparsity, inspiredfrom the specific structure of power flowequations.Despite its heuristic nature, numerical examples show that minimal sparsity allows the computation ofhighly accurate second-order moment-SOS relaxationsof AC-OPF, while requiring far less computing time and memory resources than the standard correlative sparsity pattern. Thus, we manage to compute second-order relaxations on test caseswith about 6000 power buses, which we believe to be unprecedented.

We briefly recall basics of the Moment-SOS hierarchy in polynomial optimization and the Christoffel-Darboux kernel (and the Christoffel function (CF)) in theory of approximation and orthogonal polynomials. We then (i) show a strong link between the CF and the SOS-based positive certificate at the core of the Moment-SOS hierarchy, and (ii) describe how the CD-kernel provides a simple interpretation of the SOS-hierarchy of lower bounds as searching for some signed polynomial density (while the SOS-hierarchy of upper bounds is searching for a positive (SOS) density). This link between the CF and positive certificates, in turn allows us (i) to establish a disintegration property of the CF much like for measures, and (ii) for certain sets, to relate the CF of their equilibrium measure with a certificate of positivity on the set, for constant polynomials.

We show that Bernstein polynomials are related to the Lebesgue measure on [0, 1] in a manner similar as Chebyshev polynomials are related to the equilibrium measure of [--1, 1]. We also show that Pell's polynomial equation satisfied by Chebyshev polynomials, provides a partition of unity of [--1, 1], the analogue of the partition of unity of [0, 1] provided by Bernstein polynomials. Both partitions of unity are interpreted as a specific algebraic certificate that the constant polynomial ''1'' is positive-on [--1, 1] via Putinar's certificate of positivity (for Chebyshev), and-on [0, 1] via Handeman's certificate of positivity (for Bernstein). Then in a second step, one combines this partition of unity with an interpretation of a duality result of Nesterov in convex conic optimization to obtain an explicit connection with the equilibrium measure on [--1, 1] (for Chebyshev) and Lebesgue measure on [0, 1] (for Bernstein). Finally this connection is also partially established for the ''d''-dimensional simplex.

We propose to approximate a (possibly discontinuous) multivariate function f (x) on a compact set by the partial minimizer arg miny 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 f is a piecewise polynomial) we prove that the approximation is exact with a low-degree polynomial p. Our approach has three distinguishing features: (i) It is mesh-free and does not require the knowledge of the discontinuity locations. (ii) It is model-free in the sense that we only assume that the function to be approximated is available through samples (point evaluations). (iii) The size of the semidefinite program is independent of the ambient dimension and depends linearly on the number of samples. We also analyze the sample complexity of the approach, proving a generalization error bound in a probabilistic setting. This allows for a comparison with machine learning approaches.

We introduce a certain variant (or regularization) $\tilde{\Lambda}^\mu_n$ of the standard Christoffel function $\Lambda^\mu_n$ associated with a measure $\mu$ on a compact set $\Omega\subset \mathbb{R}^d$. Its reciprocal is now a sum-of-squares polynomial in the variables $(x,\varepsilon)$, $\varepsilon>0$. It shares the same dichotomy property of the standard Christoffel function, that is, the growth with $n$ of its inverse is at most polynomial inside and exponential outside the support of the measure. Its distinguishing and crucial feature states that for fixed $\varepsilon>0$, and under weak assumptions, $\lim_{n\to\infty} \varepsilon^{-d}\tilde{\Lambda}^\mu_n(\xi,\varepsilon)=f(\zeta_\varepsilon)$ where $f$ (assumed to be continuous) is the unknown density of $\mu$ w.r.t. Lebesgue measure on $\Omega$, and $\zeta_\varepsilon\in\mathbf{B}_\infty(\xi,\varepsilon)$ (and so $f(\zeta_\varepsilon)\approx f(\xi)$ when $\varepsilon>0$ is small). This is in contrast with the standard Christoffel function where if $\lim_{n\to\infty} n^d\Lambda^\mu_n(\xi)$ exists, it is of the form $f(\xi)/\omega_E(\xi)$ where $\omega_E$ is the density of the equilibrium measure of $\Omega$, usually unknown. At last but not least, the additional computational burden (when compared to computing $\Lambda^\mu_n$) is just integrating symbolically the monomial basis $(x^{\alpha})_{\alpha\in\mathbb{N}^d_n}$ on the box $\{x: \Vert x-\xi\Vert_\infty<\varepsilon/2\}$, so that $1/\tilde{\Lambda}^\mu_n$ is obtained as an explicit polynomial of $(\xi,\varepsilon)$., Comment: Rapport LAAS n 23003

We first interpret Pell's equation satisfied by Chebyshev polynomials for each degree t, as a certain Positivstellensatz, which then yields for each integer t, what we call a generalized Pell's equation, satisfied by reciprocals of Christoffel functions of ''degree'' 2t, associated with the equilibrium measure $\mu$ of the interval [--1, 1] and the measure (1 -- x 2)d$\mu$. We next extend this point of view to arbitrary compact basic semi-algebraic set S $\subset$ R n and obtain a generalized Pell's equation (by analogy with the interval [--1, 1]). Under some conditions, for each t the equation is satisfied by reciprocals of Christoffel functions of ''degree'' 2t associated with (i) the equilibrium measure $\mu$ of S and (ii), measures gd$\mu$ for an appropriate set of generators g of S. These equations depend on the particular choice of generators that define the set S. In addition to the interval [--1, 1], we show that for t = 1, 2, 3, the equations are indeed also satisfied for the equilibrium measures of the 2D-simplex, the 2D-Euclidean unit ball and unit box. Interestingly, this view point connects orthogonal polynomials, Christoffel functions and equilibrium measures on one side, with sum-of-squares, convex optimization and certificates of positivity in real algebraic geometry on another side.

We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of factor width, we propose a hierarchy of semidefinite relaxations based on the extension of P\'olya's Positivstellensatz by Dickinson-Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen arbitrarily and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate $O(\varepsilon^{-c})$ if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on P\'olya's Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy., Comment: 39 pages, 15 tables

A classical result from topology called Uryshon's lemma asserts the existence of a continuous separator of two disjoint closed sets in a sufficiently regular topological space. In this work we make a search for this separator constructive and efficient in the context of real algebraic geometry. Namely, given two compact disjoint basic semialgebraic sets which are contained in an $n$-dimensional box, we provide an algorithm that computes a separating polynomial greater than or equal to 1 on the first set and less than or equal to 0 on the second one., Comment: 4 pages, 1 figure, submitted as en extended abstract for the last POEMA workshop

We consider polynomials of a few linear forms and show how exploit this type of sparsity for optimization on some particular domains like the Euclidean sphere or a polytope. Moreover, a simple procedure allows to detect this form of sparsity and also allows to provide an approximation of any polynomial by such sparse polynomials.

We show that the Christoffel function (CF) factorizes (or can be disintegrated) as the product of two Christoffel functions, one associated with the marginal and the another related to the conditional distribution, in the spirit of "the CF of the disintegration is the disintegration of the CFs". In the proof one uses an apparently overlooked property (but interesting in its own) which states that any sum-of-squares polynomial is the Christoffel function of some linear form (with a representing measure in the univariate case). The same is true for the convex cone of polynomials that are positive on a basic semi-algebraic set. This interpretation of the CF establishes another bridge between polynomials optimization and orthogonal polynomials.

We show that the empirical Christoffel function associated with a cloud of finitely many points sampled from a distribution, can provide a simple tool for supervised classification in data analysis, with good generalization properties.

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 on the range of the possible prices. A complementary approach (also due to 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., Comment: 20 pages

Deep equilibrium models are based on implicitly defined functional relations and have shown competitive performance compared with the traditional deep networks. Monotone operator equilibrium networks (monDEQ) retain interesting performance with additional theoretical guaranties. Existing certification tools for classical deep networks cannot directly be applied to monDEQs for which much fewer tools exist. We introduce a semialgebraic representation for ReLU based monDEQs which allows to approximate the corresponding input output relation by semidefinite programming (SDP). We present several applications to network certification and obtain SDP models for the following problems : robustness certification, Lipschitz constant estimation, ellipsoidal uncertainty propagation. We use these models to certify robustness of monDEQs w.r.t. a general $L_q$ norm. Experimental results show that the proposed models outperform existing approaches for monDEQ certification. Furthermore, our investigations suggest that monDEQs are much more robust to $L_2$ perturbations than $L_{\infty}$ perturbations., Comment: 16 pages, 4 tables, 2 figures

We introduce a sublevel Moment-SOS hierarchy where each SDP relaxation can be viewed as an intermediate (or interpolation) between the d-th and (d+1)-th order SDP relaxations of the Moment-SOS hierarchy (dense or sparse version). With the flexible choice of determining the size (level) and number (depth) of subsets in the SDP relaxation, one is able to obtain different improvements compared to the d-th order relaxation, based on the machine memory capacity. In particular, we provide numerical experiments for d=1 and various types of problems both in combinatorial optimization (Max-Cut, Mixed Integer Programming) and deep learning (robustness certification, Lipschitz constant of neural networks), where the standard Lasserre's relaxation (or its sparse variant) is computationally intractable. In our numerical results, the lower bounds from the sublevel relaxations improve the bound from Shor's relaxation (first order Lasserre's relaxation) and are significantly closer to the optimal value or to the best-known lower/upper bounds., Comment: 25 pages, 13 tables

We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated quadratically constrained quadratic programs., Comment: 43 pages, 6 algorithms, 23 tables

This paper is concerned with minimizing a sum of rational functions over a compact set of high-dimension. Our approach relies on the second Lasserre's hierarchy (also known as the upper bounds hierarchy) formulated on the pushforward measure in order to work in a space of smaller dimension. We show that in the general case the minimum can be approximated as closely as desired from above with a hierarchy of semidefinite programs problems or, in the particular case of a single fraction, with a hierarchy of generalized eigenvalue problems. We numerically illustrate the potential of using the pushforward measure rather than the standard upper bounds hierarchy. In our opinion, this potential should be a strong incentive to investigate a related challenging problem interesting in its own; namely integrating an arbitrary power of a given polynomial on a simple set (e.g., unit box or unit sphere) with respect to Lebesgue or Haar measure., Comment: 24 pages, 3 tables

We consider the global minimization of a polynomial on a compact set B. We show that each step of the Moment-SOS hierarchy has a nice and simple interpretation that complements the usual one. Namely, it computes coefficients of a polynomial in an orthonormal basis of L 2 (B, $\mu$) where $\mu$ is an arbitrary reference measure whose support is exactly B. The resulting polynomial is a certain density (with respect to $\mu$) of some signed measure on B. When some relaxation is exact (which generically takes place) the coefficients of the optimal polynomial density are values of orthonormal polynomials at the global minimizer and the optimal (signed) density is simply related to the Christoffel-Darboux (CD) kernel and the Christoffel function associated with $\mu$. In contrast to the hierarchy of upper bounds which computes positive densities, the global optimum can be achieved exactly as integration against a polynomial (signed) density because the CD-kernel is a reproducing kernel, and so can mimic a Dirac measure (as long as finitely many moments are concerned).

We propose a novel method for planning shortest length piecewise-linear motions through complex environments punctured with static, moving, or even morphing obstacles. Using a moment optimization approach, we formulate a hierarchy of semidefinite programs that yield increasingly refined lower bounds converging monotonically to the optimal path length. For computational tractability, our global moment optimization approach motivates an iterative motion planner that outperforms competing sampling-based and nonlinear optimization baselines. Our method natively handles continuous time constraints without any need for time discretization, and has the potential to scale better with dimensions compared to popular sampling-based methods.

We consider degree-d forms on the Euclidean unit sphere. We specialize to our setting a genericity result by Nie obtained in a more general framework. We exhibit an homogeneous polynomial Res in the coefficients of f , such that if Res(f) = 0 then all points that satisfy first-and second-order necessary optimality conditions are in fact local minima of f on the unit sphere. Then we obtain obtain a simple and compact characterization of all local minima of generic degree-d forms, solely in terms of the value of (i) f , (ii) the norm of its gradient, and (iii) the first two smallest eigenvalues of its Hessian, all evaluated at the point. In fact this property also holds for twice continuous differentiable functions that are positively homogeneous. Finally we obtain a characterization of generic degree-d forms with no spurious local minimum on the unit sphere by using a property of gradient ideals in algebraic geometry.

We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems (QCQPs)., Comment: 38 pages, 6 figures, 11 tables

This work is a follow-up and a complement to arXiv:1912.08899 [math.OC] for solving polynomial optimization problems (POPs). The chordal-TSSOS hierarchy that we propose is a new sparse moment-SOS framework based on term-sparsity and chordal extension. By exploiting term-sparsity of the input polynomials we obtain a two-level hierarchy of semidefinite programming relaxations. The novelty and distinguishing feature of such relaxations is to obtain quasi block-diagonal matrices obtained in an iterative procedure that performs chordal extension of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Various numerical examples demonstrate the efficiency and the scalability of this new hierarchy for both unconstrained and constrained POPs. The two hierarchies are complementary. While the former TSSOS arXiv:1912.08899 [math.OC] has a theoretical convergence guarantee, the chordal-TSSOS has superior performance but lacks this theoretical guarantee., Comment: 29 pages, 14 tables, 5 figures. arXiv admin note: text overlap with arXiv:1912.08899

If $f$ is a positive definite form, Reznick's Positivstellensatz [Mathematische Zeitschrift. 220 (1995), pp. 75--97] states that there exists $k\in\mathbf{N}$ such that ${\| x \|^{2k}_2}f$ is a sum of squares of polynomials. Assuming that $f$ can be written as a sum of forms $\sum_{l=1}^p f_l$, where each $f_l$ depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists $k \in \mathbf{N}$ such that $f=\sum_{l = 1}^p {{\sigma_l}/{H_l^{k}}}$, where $\sigma_l$ is a sum of squares of polynomials, $H_l$ is a uniform polynomial denominator, and both polynomials $\sigma_l,H_l$ involve the same variables as $f_l$, for each $l=1,\dots,p$. In other words, the sparsity pattern of $f$ is also reflected in this sparse version of Reznick's certificate of positivity. We next use this result to also obtain positivity certificates for (i) polynomials nonnegative on the whole space and (ii) polynomials nonnegative on a (possibly non-compact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate due to Putinar and Vasilescu., Comment: 19 pages, 2 tables

The Lipschitz constant of a network plays an important role in many applications of deep learning, such as robustness certification and Wasserstein Generative Adversarial Network. We introduce a semidefinite programming hierarchy to estimate the global and local Lipschitz constant of a multiple layer deep neural network. The novelty is to combine a polynomial lifting for ReLU functions derivatives with a weak generalization of Putinar's positivity certificate. This idea could also apply to other, nearly sparse, polynomial optimization problems in machine learning. We empirically demonstrate that our method provides a trade-off with respect to state of the art linear programming approach, and in some cases we obtain better bounds in less time., Comment: NeurIPS 2020

Given a compact basic semi-algebraic set we provide a numerical scheme to approximate as closely as desired, any finite number of moments of the Hausdorff measure on the boundary of this set. This also allows one to approximate interesting quantities like length, surface, or more general integrals on the boundary, as closely as desired from above and below., Comment: 21 pages, 2 figures, 2 tables

This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite programming relaxations. The novelty (and distinguishing feature) of such relaxations is to involve block-diagonal matrices obtained in an iterative procedure performing completion of the connected components of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Our theoretical framework is then applied to compute lower bounds for polynomial optimization problems either randomly generated or coming from the networked systems literature., Comment: 29 pages, 1 figure, 10 tables

In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu [Comptes Rendus de l'Acad\'emie des Sciences-Series I-Mathematics, 328(6) (1999) pp. 495-499]. We use Jacobi's technique from [Mathematische Zeitschrift, 237(2) (2001) pp. 259-273] to provide an alternative proof with an effective degree bound on the sums of squares multipliers in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization problem. Convergence of this hierarchy to a neighborhood of the optimal value as well as strong duality and analysis are guaranteed. In a second contribution, we introduce a new numerical method for solving systems of polynomial inequalities and equalities with possibly uncountably many solutions. As a bonus, one may apply this method to obtain approximate global optimizers in polynomial optimization., Comment: 33 pages, 2 figures, 5 tables

We show that the Euclidean ball has the smallest volume among sublevel sets of nonnegative forms of bounded Bombieri norm as well as among sublevel sets of sum of squares forms whose Gram matrix has bounded Frobenius or nuclear (or, more generally, p-Schatten) norm. These volume-minimizing properties of the Euclidean ball with respect to its representation (as a sublevel set of a form of fixed even degree) complement its numerous intrinsic geometric properties. We also provide a probabilistic interpretation of the results.

Chebyshev polynomials of the first and second kind for a set K are monic polynomials with minimal L $\infty$-and L 1-norm on K, respectively. This articles presents numerical procedures based on semidefinite programming to compute these polynomials in case K is a finite union of compact intervals. For Chebyshev polynomials of the first kind, the procedure makes use of a characterization of polynomial nonnegativity. It can incorporate additional constraints, e.g. that all the roots of the polynomial lie in K. For Chebyshev polynomials of the second kind, the procedure exploits the method of moments. Key words and phrases: Chebyshev polynomials of the first kind, Chebyshev polynomials of the second kind, nonnegative polynomials, method of moments, semidefinite programming.

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 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 sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected.

We interpret some wrong results (due to numerical inaccuracies) already observed when solving SDP-relaxations for polynomial optimization on a double precision floating point SDP solver. It turns out that this behavior can be explained and justified satisfactorily by a relatively simple paradigm. In such a situation, the SDP solver (and not the user) performs some `robust optimization' without being told to do so. Instead of solving the original optimization problem with nominal criterion $f$, it uses a new criterion $\tilde{f}$ which belongs to a ball $\mathbf{B}_\infty(f,\varepsilon)$ of small radius $\varepsilon>0$, centered at the nominal criterion $f$ in the parameter space. In other words the resulting procedure can be viewed as a `$\max-\min$' robust optimization problem with two players (the solver which maximizes on $\mathbf{B}_\infty(f,\varepsilon)$ and the user who minimizes over the original decision variables). A mathematical rationale behind this `autonomous' behavior is described., Comment: 17 pages

Spectral features of the empirical moment matrix constitute a resourceful tool for unveiling properties of a cloud of points, among which, density, support and latent structures. It is already well known that the empirical moment matrix encodes a great deal of subtle attributes of the underlying measure. Starting from this object as base of observations we combine ideas from statistics, real algebraic geometry, orthogonal polynomials and approximation theory for opening new insights relevant for Machine Learning (ML) problems with data supported on singular sets. Refined concepts and results from real algebraic geometry and approximation theory are empowering a simple tool (the empirical moment matrix) for the task of solving non-trivial questions in data analysis. We provide (1) theoretical support, (2) numerical experiments and, (3) connections to real world data as a validation of the stamina of the empirical moment matrix approach.

This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a linear equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is then approximated by a hierarchy of convex, finite-dimensional, semidefinite programming problems (SDPs). In the case of analysis of uncontrolled PDEs, the solutions to these SDPs provide bounds on a specified, possibly nonlinear, functional of the solutions to the PDE; in the case of PDE control, the solutions to these SDPs provide bounds on the optimal value of a given optimal control problem as well as suboptimal feedback controllers. The entire approach is based purely on convex optimization and does not rely on spatio-temporal gridding, even though the PDE addressed can be fully nonlinear. The approach is applicable to a very broad class nonlinear PDEs with polynomial data. Computational complexity is analyzed and several complexity reduction procedures are described. Numerical examples demonstrate the approach.

We propose a moment relaxation for two problems, the separation and covering problem with semi-algebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases and (b) after performing some small perturbation of the original problem, convergence can be achieved with r=d. We further provide a practical iterative algorithm that is computationally tractable for large datasets and present encouraging computational results., Comment: 23 pages, 5 figures

The long-standing problem of minimal projections is addressed from a computational point of view. Techniques to determine bounds on the projection constants of univariate polynomial spaces are presented. The upper bound, produced by a linear program, and the lower bound, produced by a semidefinite program exploiting the method of moments, are often close enough to deduce the projection constant with reasonable accuracy. The implementation of these programs makes it possible to find the projection constant of several three-dimensional spaces with five digits of accuracy, as well as the projection constants of the spaces of cubic, quartic, and quintic polynomials with four digits of accuracy. Beliefs about uniqueness and shape-preservation of minimal projections are contested along the way.