Error bounds for monomial convexification in polynomial optimization
From MaRDI portal
Abstract: Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of . This implies additive error bounds for relaxing a polynomial optimization problem by convexifying each monomial separately. Our main error bounds depend primarily on the degree of the monomial, making them easy to compute. Since monomial convexification studies depend on the bounds on the associated variables, in the second part, we conduct an error analysis for a multilinear monomial over two different types of box constraints. As part of this analysis, we also derive the convex hull of a multilinear monomial over .
Recommendations
Cites work
- A class of valid inequalities for multilinear 0-1 optimization problems
- A convex envelope formula for multilinear functions
- A polyhedral branch-and-cut approach to global optimization
- A polyhedral study of binary polynomial programs
- A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs
- ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
- An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
- An introduction to polynomial and semi-algebraic optimization
- Analysis of MILP techniques for the pooling problem
- Analysis of bounds for multilinear functions
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Branching and bounds tighteningtechniques for non-convex MINLP
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Concave envelopes of monomial functions over rectangles
- Concave extensions for nonlinear 0-1 maximization problems
- Convex envelopes for edge-concave functions
- Convex envelopes of monomials of odd degree
- Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
- Convex extensions and envelopes of lower semi-continuous functions
- Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
- Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
- Error bounds in mathematical programming
- Explicit convex and concave envelopes through polyhedral subdivisions
- Global optimization of nonconvex problems with multilinear intermediates
- Global optimization with polynomials and the problem of moments
- Integer Programming Subject to Monomial Constraints
- Jointly Constrained Biconvex Programming
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
- On convex envelopes for bivariate functions over polytopes
- Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes
- Quantifying double McCormick
- RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems
- Reduced RLT representations for nonconvex polynomial programming problems
- Some results on the strength of relaxations of multilinear functions
- Sums of squares, moment matrices and optimization over polynomials
- Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes
- Valid inequalities and convex hulls for multilinear functions
Cited in
(7)- The convex hull of a quadratic constraint over a polytope
- The optimal \(L_ 1\) problem for generalized polynomial monosplines and a related problem
- Exact and approximate results for convex envelopes of special structured functions over simplices
- scientific article; zbMATH DE number 7305739 (Why is no real title available?)
- scientific article; zbMATH DE number 2248404 (Why is no real title available?)
- Convex hull representations of special monomials of binary variables
- Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
This page was built for publication: Error bounds for monomial convexification in polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414910)
