BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jean Lasserre

Jean Lasserre appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCmath.NAmath.AGmath.CANumerical AnalysisComputational Geometryeess.SYmath.COSystems and Control

Catalog footprint

What is connected

12works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

12 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access