Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations

DOI10.1007/s10107-010-0340-3zbMath1229.90144OpenAlexW4231143303MaRDI QIDQ652290

Anureet Saxena, Jon Lee, Pierre Bonami

Publication date: 14 December 2011

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

Full work available at URL: https://doi.org/10.1007/s10107-010-0340-3

zbMATH Keywords

projection techniquesSDPeigen-reformulationMIQCPsubgradient-based heuristic

Mathematics Subject Classification ID

Semidefinite programming (90C22) Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26)

Related Items

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Disjunctive Cuts for Nonconvex MINLP, Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, Obtaining Tighter Relaxations of Mathematical Programs with Complementarity Constraints, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, A computational study for bilevel quadratic programs using semidefinite relaxations, Generating cutting planes for the semidefinite relaxation of quadratic programs, Conic approximation to quadratic optimization with linear complementarity constraints, Intersection Disjunctions for Reverse Convex Sets, SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs, GLOMIQO: global mixed-integer quadratic optimizer, Global optimization of MIQCPs with dynamic piecewise relaxations, Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Partial Lasserre relaxation for sparse Max-Cut, A new global algorithm for factor-risk-constrained mean-variance portfolio selection, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, Outer-product-free sets for polynomial optimization and oracle-based cuts, An effective global algorithm for worst-case linear optimization under polyhedral uncertainty, Effective algorithms for optimal portfolio deleveraging problem with cross impact, An LPCC approach to nonconvex quadratic programs, Linear programing relaxations for a strategic pricing problem in electricity markets, An integer linear programming approach for bilinear integer programming, On global optimization with indefinite quadratics, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations, On linear programs with linear complementarity constraints, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, Optimal rank-sparsity decomposition, A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Global solution of non-convex quadratically constrained quadratic programs, Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint, A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation, Extensions on ellipsoid bounds for quadratic integer programming, DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs, An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation, Convexification of bilinear forms through non-symmetric lifting, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem, Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations, Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties, On the Composition of Convex Envelopes for Quadrilinear Terms, Compact mixed-integer programming formulations in quadratic optimization, SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

Uses Software

• SDPA
• SDPLR
• Bonmin
• Ipopt
• FilMINT

Cites Work

• Unnamed Item
• MIP reformulations of the probabilistic set covering problem
• An algorithmic framework for convex mixed integer nonlinear programs
• Relaxations for probabilistically constrained programs with discrete random variables
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Disjunctive programming: Properties of the convex hull of feasible points
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A polyhedral study of nonconvex quadratic programs with box constraints
• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• A branch-and-cut method for 0-1 mixed convex programming
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Optimizing over the split closure
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• \(NP\)-hardness of linear multiplicative programming and related problems
• Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• FilMINT: An Outer Approximation-Based Solver for Convex Mixed-Integer Nonlinear Programs
• A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed-Integer Conic Quadratic Programs
• Branching and bounds tighteningtechniques for non-convex MINLP
• Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
• The Homotopy Principle and Algorithms for Linear Programming
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• On Polyhedral Approximations of the Second-Order Cone