Outer-product-free sets for polynomial optimization and oracle-based cuts

DOI10.1007/S10107-020-01484-3MaRDI QIDQ2196293zbMATH OpenOpenAlexFDO

Authors Chen Chen, Gonzalo Muñoz, Daniel Bienstock

Publication date 28 August 2020

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04604

zbMATH Keywords

polynomial optimizationcutting planesintersection cuts\(S\)-free sets

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonlinear programming (90C30) Polynomial optimization (90C23)

Abstract: This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $ScapP$, where $S$ is a closed set, and $P$ is a polyhedron. Given an oracle that provides the distance from a point to $S$, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or $S$-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of emph{outer-product-free} sets, where $S$ is the set of real, symmetric matrices of the form $x{x}^T$. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach.

Recommendations

• Intersection cuts for polynomial optimization
• Cut-generating functions
• Maximal quadratic-free sets
• Maximal quadratic-free sets
• Outer approximation by polyhedral convex sets

Cites work

• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3215121 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A branch and cut algorithm for nonconvex quadratically constrained quadratic programming
• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• A convex envelope formula for multilinear functions
• A dynamic inequality generation scheme for polynomial programming
• A new general-purpose algorithm for mixed-integer bilevel linear programs
• A note on the selection of Benders' cuts
• A polyhedral branch-and-cut approach to global optimization
• A unifying framework for several cutting plane methods for semidefinite programming
• Aggregation and Mixed Integer Rounding to Solve MIPs
• An analysis of mixed integer linear sets based on lattice point free convex sets
• Choosing the best set of variables in regression analysis using integer programming
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Computing a nearest symmetric positive semidefinite matrix
• Cone adaptation strategies for a finite and exact cutting plane algorithm for concave minimization
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Conic mixed-integer rounding cuts
• Constrained infinite group relaxations of MIPs
• Convex Analysis
• Convex Bodies The Brunn-MinkowskiTheory
• Convex extensions and envelopes of lower semi-continuous functions
• Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
• Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
• Convex sets and minimal sublinear functions
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Cook, Kannan and Schrijver's example revisited
• Cut-generating functions and \(S\)-free sets
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• Disjunctive programming: Properties of the convex hull of feasible points
• Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
• Edmonds polytopes and a hierarchy of combinatorial problems
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Equivalence between intersection cuts and the corner polyhedron
• Existence and sum decomposition of vertex polyhedral convex envelopes
• Explicit convex and concave envelopes through polyhedral subdivisions
• Finite exact branch-and-bound algorithms for concave minimization over polytopes
• Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
• Global optimization with polynomials and the problem of moments
• Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound
• Globally solving nonconvex quadratic programming problems via completely positive programming
• Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
• Inequalities from Two Rows of a Simplex Tableau
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Intersection cuts for factorable MINLP
• Intersection cuts for mixed integer conic quadratic sets
• Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
• Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles
• Linear programming relaxations of quadratically constrained quadratic programs
• Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem
• Maximal lattice-free convex sets in linear subspaces
• Minimal inequalities for an infinite relaxation of integer programs
• Minimal valid inequalities for integer constraints
• Mixed-integer nonlinear optimization
• Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
• New solution approaches for the maximum-reliability stochastic network interdiction problem
• Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization
• On convergence in mixed integer programming
• On convex envelopes for bivariate functions over polytopes
• On families of quadratic surfaces having fixed intersections with two hyperplanes
• On minimal valid inequalities for mixed integer conic programs
• On the complexity of four polyhedral set containment problems
• Optimizing a polyhedral-semidefinite relaxation of completely positive programs
• Optimizing over the first Chvátal closure
• Optimizing over the split closure
• Outline of an algorithm for integer solutions to linear programs
• Partitioning procedures for solving mixed-variables programming problems
• Polyhedral convexity cuts and negative edge extensions
• Reverse convex programming
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
• Some continuous functions related to corner polyhedra
• Some results on the strength of relaxations of multilinear functions
• Split cuts and extended formulations for mixed integer conic quadratic programming
• Sufficiency of cut-generating functions
• Sums of squares, moment matrices and optimization over polynomials
• The Cutting-Plane Method for Solving Convex Programs
• The ellipsoid method and its consequences in combinatorial optimization
• The split closure of a strictly convex body

Cited in

(20)

• Towards a characterization of maximal quadratic-free sets
• On the implementation and strengthening of intersection cuts for QCQPs
• A disjunctive cutting plane algorithm for bilinear programming
• On tackling reverse convex constraints for non-overlapping of unequal circles
• Lifting convex inequalities for bipartite bilinear programs
• Lifting convex inequalities for bipartite bilinear programs
• Maximal quadratic-free sets
• Maximal quadratic-free sets
• On a generalization of the Chvátal-Gomory closure
• (Global) optimization: historical notes and recent developments
• On obtaining the convex hull of quadratic inequalities via aggregations
• Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
• Generating valid linear inequalities for nonlinear programs via sums of squares
• Monoidal strengthening and unique lifting in MIQCPs
• A branch-and-cut algorithm for mixed-integer bilinear programming
• Intersection cuts for polynomial optimization
• Intersection Disjunctions for Reverse Convex Sets
• Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem
• Cutting plane generation through sparse principal component analysis
• On the implementation and strengthening of intersection cuts for QCQPs

Describes a project that uses

Uses Software

• GLOBALLib
• Eigen
• GloMIQO
• QuadProgBB
• quadprogIP

This page was built for publication: Outer-product-free sets for polynomial optimization and oracle-based cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196293)