Border basis relaxation for polynomial optimization
From MaRDI portal
Abstract: A relaxation method based on border basis reduction which improves the efficiency of Lasserre's approach is proposed to compute the optimum of a polynomial function on a basic closed semi algebraic set. A new stopping criterion is given to detect when the relaxation sequence reaches the minimum, using a sparse flat extension criterion. We also provide a new algorithm to reconstruct a finite sum of weighted Dirac measures from a truncated sequence of moments, which can be applied to other sparse reconstruction problems. As an application, we obtain a new algorithm to compute zero-dimensional minimizer ideals and the minimizer points or zero-dimensional G-radical ideals. Experimentations show the impact of this new method on significant benchmarks.
Recommendations
- Border basis for polynomial system solving and optimization
- Polynomial optimization problems and their relaxations
- A hierarchy of spectral relaxations for polynomial optimization
- Bound-constrained polynomial optimization using only elementary calculations
- On linear programming relaxations for solving polynomial programming problems
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization
- Bilevel polynomial programs and semidefinite relaxation methods
- scientific article; zbMATH DE number 475484
Cites work
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 1504686 (Why is no real title available?)
- A generalized flat extension theorem for moment matrices
- A unified approach to computing real and complex zeros of zero-dimensional ideals
- Border basis representation of a general quotient algebra
- Class of global minimum bounds of polynomial functions
- Computing the global optimum of a multivariate polynomial over the reals
- Deciding reachability of the infimum of a multivariate polynomial
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Generalized normal forms and polynomial system solving
- Global optimization with polynomials and the problem of moments
- Handbook of test problems in local and global optimization
- Introduction to the solution of polynomial systems
- Minimizing polynomials via sum of squares over the gradient ideal
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- Representations of positive polynomials and optimization on noncompact semialgebraic sets
- Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- Stable normal forms for polynomial system solving
- Symbolic-numeric sparse interpolation of multivariate polynomials
- Symmetric tensor decomposition
Cited in
(6)- Sparse interpolation in terms of multivariate Chebyshev polynomials
- Unfoldings and the rank-one approximation of the tensor
- On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors
- A Polyhedral Characterization of Border Bases
- Border basis for polynomial system solving and optimization
- On the equivalence of two post-quantum cryptographic families
This page was built for publication: Border basis relaxation for polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898268)
