Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodríguez-Heck … Read more
Random projections map a set of points in a high dimensional space to a lower dimen- sional one while approximately preserving all pairwise Euclidean distances. While random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving … Read more
We consider the semi-infinite system of polynomial inequalities of the form \[ \mathbf{K}:=\{x\in\mathbb{R}^m\mid p(x,y)\ge 0,\ \ \forall y\in S\subseteq\mathbb{R}^n\}, \] where $p(X,Y)$ is a real polynomial in the variables $X$ and the parameters $Y$, the index set $S$ is a basic semialgebraic set in $\mathbb{R}^n$, $-p(X,y)$ is convex in $X$ for every $y\in S$. We … Read more
We construct norming meshes for polynomial optimization by the classical Markov inequality on general convex bodies in R^d, and by a tangential Markov inequality via an estimate of Dubiner distance on smooth convex bodies. These allow to compute a (1−eps)-approximation to the minimum of any polynomial of degree not exceeding n by O((n/sqrt(eps))^(ad)) samples, with … Read more
We construct web-shaped norming meshes on starlike polygons, by radial and boundary Chebyshev points. Via the approximation theoretic notion of Dubiner distance, we get a (1-eps)-approximation to the minimum of an arbitrary polynomial of degree n by O(n^2/eps) sampling points. CitationPreprint, July 2018 ArticleDownload View PDF
We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuousand 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 … Read more
This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. … Read more
In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellens\”atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\”udgen) that certify positivity of a polynomial on an … Read more
In this article we present a robustness analysis of the extraction of optimizers in polynomial optimization. Optimizers can be extracted by solving moment problems using flatness and the Gelfand-Naimark-Segal (GNS) construction. Here a modification of the GNS construction is presented that applies even to non-flat data, and then its sensitivity under perturbations is studied. The … Read more
In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone … Read more