How to convexify the intersection of a second order cone and a nonconvex quadratic

DOI10.1007/S10107-016-1045-ZMaRDI QIDQ517311zbMATH OpenOpenAlexFDO

Authors Samuel Burer, Fatma Kılınç-Karzan

Publication date 23 March 2017

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

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

zbMATH Keywords

convex hulldisjunctive programmingmixed-integer linear programmingmixed-integer nonlinear programmingmixed-integer quadratic programmingnonconvex quadratic programmingsecond-order-cone programmingtrust-region subproblem

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26)

Abstract: A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown---by several authors using different techniques---that the convex hull of the intersection of an ellipsoid, $E$, and a split disjunction, $(l-x_j)(x_j-u)le0$ with $l<u$, equals the intersection of $E$ with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form $KcapQ$ and $KcapQcapH$, where $K$ is a SOCr cone, $Q$ is a nonconvex cone defined by a single homogeneous quadratic, and $H$ is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations $KcapS$ and $KcapScapH$, where $S$ is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.

Recommendations

• A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
• Two-term disjunctions on the second-order cone
• Two-term disjunctions on the second-order cone
• A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization
• Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations

Cites work

• \(\alpha BB\): A global optimization method for general constrained nonconvex problems
• A branch-and-cut method for 0-1 mixed convex programming
• A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints
• A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
• A convex-analysis perspective on disjunctive cuts
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A Survey of the S-Lemma
• Computable representations for convex hulls of low-dimensional quadratic forms
• Computing a Trust Region Step
• Computing deep facet-defining disjunctive cuts for mixed-integer programming
• Conic mixed-integer rounding cuts
• Convex hull of two quadratic constraints is an LMI set
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• Convex programming for disjunctive convex optimization
• Convexification techniques for linear complementarity constraints
• Cuts for mixed 0-1 conic programming
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• Cutting-planes for weakly-coupled 0/1 second order cone programs
• Disjunctive cuts for cross-sections of the second-order cone
• Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
• Disjunctive Cuts for Nonconvex MINLP
• Disjunctive Programming
• Explicit convex and concave envelopes through polyhedral subdivisions
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 3288876 (Why is no real title available?)
• Intersection cuts for mixed integer conic quadratic sets
• Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Lift-and-project cuts for convex mixed integer nonlinear programs
• Lift-and-project cuts for mixed integer convex programs
• Mixed integer second order cone programming.
• On families of quadratic surfaces having fixed intersections with two hyperplanes
• On minimal valid inequalities for mixed integer conic programs
• On the Global Solution of Linear Programs with Linear Complementarity Constraints
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Optimization with disjunctive constraints
• Perspective reformulations of mixed integer nonlinear programs with indicator variables
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• Second-order-cone constraints for extended trust-region subproblems
• Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
• Solving the Trust-Region Subproblem using the Lanczos Method
• Split cuts and extended formulations for mixed integer conic quadratic programming
• Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
• The MILP road to MIQCP
• The split closure of a strictly convex body
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Two-term disjunctions on the second-order cone
• Two-term disjunctions on the second-order cone

Cited in

(33)

• Intersection cuts for convex mixed integer programs from translated cones
• The generalized trust region subproblem: solution complexity and convex hull results
• Ideal formulations for constrained convex optimization problems with indicator variables
• Maximal quadratic-free sets
• On the tightness of SDP relaxations of QCQPs
• Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
• A survey of hidden convex optimization
• A new framework to relax composite functions in nonlinear programs
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• On families of quadratic surfaces having fixed intersections with two hyperplanes
• On minimal valid inequalities for mixed integer conic programs
• On sublinear inequalities for mixed integer conic programs
• A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
• Maximal quadratic-free sets
• On Convex Hulls of Epigraphs of QCQPs
• On the convexification of constrained quadratic optimization problems with indicator variables
• On obtaining the convex hull of quadratic inequalities via aggregations
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• The convex hull of a quadratic constraint over a polytope
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• A second-order cone based approach for solving the trust-region subproblem and its variants
• On the implementation and strengthening of intersection cuts for QCQPs
• On the implementation and strengthening of intersection cuts for QCQPs
• Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
• (Global) optimization: historical notes and recent developments
• Convex hull results on quadratic programs with non-intersecting constraints
• Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
• The nonconvex second-order cone: algebraic structure toward optimization
• Accelerated first-order methods for a class of semidefinite programs
• Non-convex optimization problems with linear KKT subsystem
• Cutting planes for signomial programming
• On semidefinite descriptions for convex hulls of quadratic programs
• Two-term disjunctions on the second-order cone

Describes a project that uses

Uses Software

• GQTPAR

This page was built for publication: How to convexify the intersection of a second order cone and a nonconvex quadratic

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