Source author record

Jean Lasserre

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC math.NA math.AG math.CA Numerical Analysis Computational Geometry eess.SY math.CO Systems and Control

Catalog footprint

Research overview

12works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Approximating regions of attraction of a sparse polynomial differential system *

Motivated by stability analysis of large scale power systems, we describe how the Lasserre (moment-sums of squares, SOS) hierarchy can be used to generate outer approximations of the region of attraction (ROA) of sparse polynomial differential systems, at the price of solving linear matrix inequalities (LMI) of increasing size. We identify specific sparsity structures for which we can provide numerically certified outer approximations of the region of attraction in high dimension. For this purpose, we combine previous results on non-sparse ROA approximations with sparse semi-algebraic set volume computation.

preprint2020arXiv

Connecting optimization with spectral analysis of tri-diagonal matrices

We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r x r) tri-diagonal univariate moment matrices of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal polynomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal symmetric matrices.

preprint2020arXiv

Simple Formula for Integration of Polynomials on a Simplex

We show that integrating a polynomial of degree t on an arbitrary simplex (with respect to Lebesgue measure) reduces to evaluating t homogeneous polynomials of degree j = 1, 2,. .. , t, each at a unique point $ξ$ j of the simplex. This new and very simple formula can be exploited in finite (and extended finite) element methods, as well as in other applications where such integrals are needed.

preprint2016arXiv

Bound-constrained polynomial optimization using only elementary calculations

We provide a monotone non increasing sequence of upper bounds $f^H_k$ ( $k\ge 1$ ) converging to the global minimum of a polynomial $f$ on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds $f^H_k$ have a rate of convergence in $O(1/\sqrt {k})$ . Moreover we show a stronger convergence rate in $O(1/k)$ for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator $k$ produces bounds with a rate of convergence in $O(1/k^2)$ , but at the cost of $O(k^n)$ function evaluations, while the new bound $f^H_k$ needs only $O(n^k)$ elementary calculations.

preprint2012arXiv

A Lagrangian relaxation view of linear and semidefinite hierarchies

We consider the general polynomial optimization problem $P: f^*=\min \{f(x)\,:\,x\in K\}$ where $K$ is a compact basic semi-algebraic set. We first show that the standard Lagrangian relaxation yields a lower bound as close as desired to the global optimum $f^*$ , provided that it is applied to a problem $\tilde{P}$ equivalent to $P$ , in which sufficiently many redundant constraints (products of the initial ones) are added to the initial description of $P$ . Next we show that the standard hierarchy of LP-relaxations of $P$ (in the spirit of Sherali-Adams' RLT) can be interpreted as a brute force simplification of the above Lagrangian relaxation in which a nonnegative polynomial (with coefficients to be determined) is replaced with a constant polynomial equal to zero. Inspired by this interpretation, we provide a systematic improvement of the LP-hierarchy by doing a much less brutal simplification which results into a parametrized hierarchy of semidefinite programs (and not linear programs any more). For each semidefinite program in the parametrized hierarchy, the semidefinite constraint has a fixed size $O(n^k)$ , independently of the rank in the hierarchy, in contrast with the standard hierarchy of semidefinite relaxations. The parameter $k$ is to be decided by the user. When applied to a non trivial class of convex problems, the first relaxation of the parametrized hierarchy is exact, in contrast with the LP-hierarchy where convergence cannot be finite. When applied to 0/1 programs it is at least as good as the first one in the hierarchy of semidefinite relaxations. However obstructions to exactness still exist and are briefly analyzed. Finally, the standard semidefinite hierarchy can also be viewed as a simplification of an extended Lagrangian relaxation, but different in spirit as sums of squares (and not scalars) multipliers are allowed.

preprint2012arXiv

Recovering an homogeneous polynomial from moments of its level set

Let $K:={x: g(x)\leq 1}$ be the compact sub-level set of some homogeneous polynomial $g$ . Assume that the only knowledge about $K$ is the degree of $g$ as well as the moments of the Lebesgue measure on $K$ up to order 2d. Then the vector of coefficients of $g$ is solution of a simple linear system whose associated matrix is nonsingular. In other words, the moments up to order 2d of the Lebesgue measure on $K$ encode all information on the homogeneous polynomial $g$ that defines $K$ (in fact, only moments of order $d$ and 2d are needed).

preprint2012arXiv

The inverse moment problem for convex polytopes

The goal of this paper is to present a general and novel approach for the reconstruction of any convex d-dimensional polytope P, from knowledge of its moments. In particular, we show that the vertices of an N-vertex polytope in R^d can be reconstructed from the knowledge of O(DN) axial moments (w.r.t. to an unknown polynomial measure od degree D) in d+1 distinct generic directions. Our approach is based on the collection of moment formulas due to Brion, Lawrence, Khovanskii-Pukhikov, and Barvinok that arise in the discrete geometry of polytopes, and what variously known as Prony's method, or Vandermonde factorization of finite rank Hankel matrices.

preprint2011arXiv

An algorithm for semi-infinite polynomial optimization

We consider the semi-infinite optimization problem: $f^*:=\min_{x\in X}\:\{f(x): g(x,y)\,\leq \,0,\:\forally\in Y_x\}$, where $f,g$ are polynomials and $X\subset R^n$ as well as $Y_\x\subset R^p$, $x\in X$ , are compact basic semi-algebraic sets. To approximate $f^*$ we proceed in two steps. First, we use the "joint+marginal" approach of the author to approximate from above the function $x\mapstoΦ(x)=\sup \{g(x,y): y\in Y_x\}$ by a polynomial $Φ_d\geqΦ$ , of degree at most $2d$ , with the strong property that $Φ_d$ converges to $Φ$ for the $L_1$ -norm, as $d\to\infty$ (and in particular, almost uniformly for some subsequence $(d_\ell)$ , $\ell\in\N$ ). Then we solve the polynomial optimization problem $f^*_d=\min_{x\in X} \{f(x): Φ_d(x)\leq0\}$ via a (by now standard) hierarchy of semidefinite relaxations. It turns out that the optimal value $f^*_d\geq f^*$ converges to $f^*$ as $d\to\infty$ . In practice we let $d$ be fixed, small, and relax the constraint $Φ_d\leq0$ to $Φ_d(x)\leqε$ with $ε>0$ , allowing to change $ε$ dynamically.

preprint2011arXiv

Existence of Gaussian cubature formulas

We provide a necessary and sufficient condition for existence of Gaussian cubature formulas. It consists of checking whether some overdetermined linear system has a solution and so complements Mysovskikh's theorem which requires computing common zeros of orthonormal polynomials. Moreover, the size of the linear system shows that existence of a cubature formula imposes severe restrictions on the associated linear functional. For fixed precision (or degree), the larger the number of variables the worse it gets. And for fixed number of variables, the larger the precision the worse it gets. Finally, we also provide an interpretation of the necessary and sufficient condition in terms of existence of a polynomial with very specific properties.

preprint2011arXiv

The K-moment problem for continuous linear functionals

Given a closed (and non necessarily compact) basic semi-algebraic set $K\subseteq R^n$ , we solve the $K$ -moment problem for continuous linear functionals. Namely, we introduce a weighted $\ell_1$ -norm $\ell_w$ on $R[x]$ , and show that the $\ell_w$ -closures of the preordering $P$ and quadratic module $Q$ (associated with the generators of $K$ ) is the cone $psd(K)$ of polynomials nonnegative on $K$ . We also prove that $P$ an $Q$ solve the $K$ -moment problem for $\ell_w$ -continuous linear functionals and completely characterize those $\ell_w$ -continuous linear functionals nonnegative on $P$ and $Q$ (hence on $psd(K)$ ). When $K$ has a nonempty interior we also provide in explicit form a canonical $\ell_w$ -projection $g^w_f$ for any polynomial $f$ , on the (degree-truncated) preordering or quadratic module. Remarkably, the support of $g^w_f$ is very sparse and does not depend on $K$ ! This enables us to provide an explicit Positivstellensatz on $K$ . At last but not least, we provide a simple characterization of polynomials nonnegative on $K$ , which is crucial in proving the above results.

preprint2010arXiv

Best $\ell_1$ -approximation of nonnegative polynomials by sums of squares

Given a nonnegative polynomial f, we provide an explicit expression for its best $\ell_1$ -norm approximation by a sum of squares of given degree.

preprint2010arXiv

Bounding the support of a measure from its marginal moments

Given all moments of the marginals of a measure on Rn, one provides (a) explicit bounds on its support and (b), a numerical scheme to compute the smallest box that contains the support. It consists of solving a hierarchy of generalized eigenvalue problems associated with some Hankel matrices.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jean Lasserre

Research overview

Is this your work?

12 publications

Approximating regions of attraction of a sparse polynomial differential system *

Connecting optimization with spectral analysis of tri-diagonal matrices

Simple Formula for Integration of Polynomials on a Simplex

Bound-constrained polynomial optimization using only elementary calculations

A Lagrangian relaxation view of linear and semidefinite hierarchies

Recovering an homogeneous polynomial from moments of its level set

The inverse moment problem for convex polytopes

An algorithm for semi-infinite polynomial optimization

Existence of Gaussian cubature formulas

The K-moment problem for continuous linear functionals

Best $\ell_1$ -approximation of nonnegative polynomials by sums of squares

Bounding the support of a measure from its marginal moments

See the researcher in context

Building this map preview

Jean Lasserre

Research overview

Is this your work?

12 publications

Approximating regions of attraction of a sparse polynomial differential system *

Connecting optimization with spectral analysis of tri-diagonal matrices

Simple Formula for Integration of Polynomials on a Simplex

Bound-constrained polynomial optimization using only elementary calculations

A Lagrangian relaxation view of linear and semidefinite hierarchies

Recovering an homogeneous polynomial from moments of its level set

The inverse moment problem for convex polytopes

An algorithm for semi-infinite polynomial optimization

Existence of Gaussian cubature formulas

The K-moment problem for continuous linear functionals

Best ℓ1\ell_1ℓ1​-approximation of nonnegative polynomials by sums of squares

Bounding the support of a measure from its marginal moments

See the researcher in context

Building this map preview

Best $\ell_1$ -approximation of nonnegative polynomials by sums of squares