A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

DOI10.1007/S10107-006-0080-6zbMath1135.90034OpenAlexW2038611554MaRDI QIDQ2476994

Samuel Burer, Dieter Vandenbussche

Publication date: 12 March 2008

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

Full work available at URL: https://doi.org/10.1007/s10107-006-0080-6

zbMATH Keywords

Semidefinite programmingLift-and-project relaxations

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items (81)

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation ⋮ An accelerating algorithm for globally solving nonconvex quadratic programming ⋮ A fixed point iterative approach to integer programming and its distributed computation ⋮ Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound ⋮ Bilinear modeling solution approach for fixed charge network flow problems ⋮ A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations ⋮ A parametric linearizing approach for quadratically inequality constrained quadratic programs ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ On the copositive representation of binary and continuous nonconvex quadratic programs ⋮ On linear programming relaxations for solving polynomial programming problems ⋮ An abstract model for branch-and-cut ⋮ GLOMIQO: global mixed-integer quadratic optimizer ⋮ A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs ⋮ An exact semidefinite programming approach for the max-mean dispersion problem ⋮ Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations ⋮ On convex relaxations for quadratically constrained quadratic programming ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ Skyport location problem for urban air mobility system ⋮ \texttt{EXPEDIS}: an exact penalty method over discrete sets ⋮ A new global algorithm for factor-risk-constrained mean-variance portfolio selection ⋮ Algorithms for linear programming with linear complementarity constraints ⋮ Ellipsoid Bounds for Convex Quadratic Integer Programming ⋮ Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs ⋮ Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems ⋮ Steering exact penalty DCA for nonsmooth DC optimisation problems with equality and inequality constraints ⋮ (Global) optimization: historical notes and recent developments ⋮ An effective global algorithm for worst-case linear optimization under polyhedral uncertainty ⋮ Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints ⋮ An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints ⋮ Using general triangle inequalities within quadratic convex reformulation method ⋮ A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming ⋮ Effective algorithms for optimal portfolio deleveraging problem with cross impact ⋮ Domain reduction techniques for global NLP and MINLP optimization ⋮ An LPCC approach to nonconvex quadratic programs ⋮ Linear programing relaxations for a strategic pricing problem in electricity markets ⋮ A canonical dual approach for solving linearly constrained quadratic programs ⋮ On global optimization with indefinite quadratics ⋮ Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation ⋮ On linear programs with linear complementarity constraints ⋮ Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts ⋮ A novel optimization method for nonconvex quadratically constrained quadratic programs ⋮ A note on representations of linear inequalities in non-convex mixed-integer quadratic programs ⋮ Testing copositivity via mixed-integer linear programming ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ A guide to conic optimisation and its applications ⋮ Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations ⋮ New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation ⋮ Optimal portfolio deleveraging under market impact and margin restrictions ⋮ Bounds tightening based on optimality conditions for nonconvex box-constrained optimization ⋮ Nonlinear optimization problem of interdependent investment projects portfolio ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints ⋮ Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming ⋮ ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations ⋮ Semidefinite relaxation for linear programs with equilibrium constraints ⋮ Globally solving nonconvex quadratic programming problems via completely positive programming ⋮ Detecting Braess paradox based on stable dynamics in general congested transportation networks ⋮ A new algorithm for concave quadratic programming ⋮ Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs ⋮ Conic approximation to nonconvex quadratic programming with convex quadratic constraints ⋮ Penalized semidefinite programming for quadratically-constrained quadratic optimization ⋮ The exact solution of multiparametric quadratically constrained quadratic programming problems ⋮ Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming ⋮ Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons ⋮ Extensions on ellipsoid bounds for quadratic integer programming ⋮ DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ Quadratic maximization of reachable values of affine systems with diagonalizable matrix ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation ⋮ On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants ⋮ Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming ⋮ Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties ⋮ An Iterative Rank Penalty Method for Nonconvex Quadratically Constrained Quadratic Programs ⋮ QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs ⋮ Unnamed Item

Uses Software

• CPLEX
• NewtonKKTqp
• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Global optimization algorithms for linearly constrained indefinite quadratic problems
• Newton-KKT interior-point methods for indefinite quadratic programming
• Quadratic programming with one negative eigenvalue is NP-hard
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• Approximating quadratic programming with bound and quadratic constraints
• A polyhedral study of nonconvex quadratic programs with box constraints
• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• Some fundamental properties of successive convex relaxation methods on LCP and related problems
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• A reformulation-convexification approach for solving nonconvex quadratic programming problems
• BARON: A general purpose global optimization software package
• Convex quadratic and semidefinite programming relaxations in scheduling
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
• Solving Lift-and-Project Relaxations of Binary Integer Programs

This page was built for publication: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations