Polynomials nonnegative on a grid and discrete optimization
The author characterizes the polynomials \(p\in\mathbb{R}[X_1, \dots, X_n]\) that are non-negative on a `grid' \(K\) in \(\mathbb{R}^n\) where \(K\) is defined by \(g_i(X_1, \dots, X_n)=0\), \(1\leq i\leq n\), and \(g_i= \prod^{2r_i}_{j=1} (X_i-a_{ij})\). The author shows that every polynomial \(p\) of degree \(2r_0\) or \(2r_0-1\), non-negative on \(K\), can be written as a sum of squares of polynomials weighted by the polynomials \(g_i\), and whose degree is bounded by \(r+\max \{r_0-r, \max^n_{i=1} r_i\}\) with \(r=\sum^n_{i=1} (2r_i-1)\), independently of the points in the grid \(K\).NEWLINENEWLINE To prove this result, the author uses a detour to the associated discrete optimization problem \(p\mapsto p^*:= \min_{x\in K}p(x)\). He shows that this discrete problem is equivalent to a continuous convex optimization problem whose size depends on the number of points, but not the points themselves in \(K\). For this, the author defines a sequence of refined, so-called convex semidefinite relaxations of the original discrete optimization problem.
- A Sum of Squares Approximation of Nonnegative Polynomials
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- Global optimization with polynomials and the problem of moments
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- Optimization of Polynomial Functions
- Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
- Distinguished representations of strictly positive polynomials
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 4036424 (Why is no real title available?)
- scientific article; zbMATH DE number 16720 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 1489798 (Why is no real title available?)
- Semidefinite Programming
- The K-moment problem for compact semi-algebraic sets
- The classical moment problem as a self-adjoint finite difference operator
- The truncated complex K-moment problem
- On solving biquadratic optimization via semidefinite relaxation
- Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- Polyhedra related to integer-convex polynomial systems
- Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets
- Charges solve the truncated complex moment problem
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- The quintic complex moment problem
- Inhomogeneous polynomial optimization over a convex set: an approximation approach
- Semidefinite relaxations of dynamical programs under discrete constraints
- Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- On a solution of the multidimensional truncated moment problem on vertices of the hypercube based on Bell inequalities
- Semidefinite representations for finite varieties
- Exact relaxations of non-convex variational problems
This page was built for publication: Polynomials nonnegative on a grid and discrete optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2759070)
