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

DOI10.1007/S10107-020-01484-3zbMATH Open1450.90024arXiv1610.04604OpenAlexW3008300991MaRDI QIDQ2196293FDOQ2196293

Gonzalo Muñoz, Chen Chen, Daniel Bienstock

Publication date: 28 August 2020

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (19)

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

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)