A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs

DOI10.1007/s10107-005-0582-7zbMath1099.90039OpenAlexW2075161899MaRDI QIDQ1780950

Jeff Linderoth

Publication date: 14 June 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-005-0582-7

zbMATH Keywords

Global optimizationBranch-and-boundNonconvex quadratic programmingConvex envelope

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20)

Related Items

Deterministic global optimization of binary hybrid distillation/melt-crystallization processes based on relaxed MINLP formulations, An accelerating algorithm for globally solving nonconvex quadratic programming, Global solutions to a class of CEC benchmark constrained optimization problems, On structural decompositions of finite frames, An optimal trade-off model for portfolio selection with sensitivity of parameters, Exact quadratic convex reformulations of mixed-integer quadratically constrained problems, A review of recent advances in global optimization, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, Non polyhedral convex envelopes for 1-convex functions, On conic QPCCs, conic QCQPs and completely positive programs, A fair division approach to humanitarian logistics inspired by conditional value-at-risk, Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Computable representations for convex hulls of low-dimensional quadratic forms, A parametric linearizing approach for quadratically inequality constrained quadratic programs, Generating cutting planes for the semidefinite relaxation of quadratic programs, A branch-bound cut technique for non-linear fractional multi-objective optimization problems, A linearized relaxing algorithm for the specific nonlinear optimization problem, Scalable Optimization Methods for Incorporating Spatiotemporal Fractionation into Intensity-Modulated Radiotherapy Planning, Dynamic optimization of nonlinear systems with guaranteed feasibility of inequality-path-constraints, An extension of Yuan's lemma and its applications in optimization, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs, 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, Alternative branching rules for some nonconvex problems, Tight convex relaxations for the expansion planning problem, Error bounds for monomial convexification in polynomial optimization, Continuous piecewise linear delta-approximations for bivariate and multivariate functions, A new global algorithm for factor-risk-constrained mean-variance portfolio selection, Copositivity and constrained fractional quadratic problems, Convex Envelopes of Some Quadratic Functions over the n-Dimensional Unit Simplex, Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming, (Global) optimization: historical notes and recent developments, A duality-bounds algorithm for non-convex quadratic programs with additional multiplicative constraints, Using Two-Dimensional Projections for Stronger Separation and Propagation of Bilinear Terms, Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints, A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, Effective algorithms for optimal portfolio deleveraging problem with cross impact, Explicit convex and concave envelopes through polyhedral subdivisions, Representing quadratically constrained quadratic programs as generalized copositive programs, Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems, A simultaneous diagonalization based SOCP relaxation for portfolio optimization with an orthogonality constraint, 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, A novel optimization method for nonconvex quadratically constrained quadratic programs, Computing the value of the convex envelope of quadratic forms over polytopes through a semidefinite program, Convex and concave envelopes: revisited and new perspectives, A distributed continuous-time method for non-convex QCQPs, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, A class of differential quadratic programming problems, A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems, Optimal portfolio deleveraging under market impact and margin restrictions, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, Global optimization algorithm for mixed integer quadratically constrained quadratic program, Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming, Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint, A technique to derive the analytical form of convex envelopes for some bivariate functions, Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, New multi-commodity flow formulations for the pooling problem, A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation, Convex envelopes of bivariate functions through the solution of KKT systems, Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs, 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, DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs, Electricity swing option pricing by stochastic bilevel optimization: a survey and new approaches, Quadratic optimization with switching variables: the convex hull for \(n=2\), Convex hull representations for bounded products of variables, A geometric branch and bound method for robust maximization of convex functions, Template polyhedra and bilinear optimization, Convex envelopes for ray-concave functions, New SOCP relaxation and branching rule for bipartite bilinear programs, Active fault diagnosis under hybrid bounded and Gaussian uncertainties, An algorithm for global solution to bi-parametric linear complementarity constrained linear programs, Active allocation of systematic risk and control of risk sensitivity in portfolio optimization, Mixed-integer linear methods for layout-optimization of screening systems in recovered paper production

Uses Software

• BARON
• GLOPT
• LANCELOT
• SeDuMi
• HTCondor MW
• COIN-OR
• INTOPT_90
• Ipopt
• Numerica

Cites Work

• Unnamed Item
• Unnamed Item
• The convergence rate of the sandwich algorithm for approximating convex functions
• Generalized bilinear programming. I: Models, applications and linear programming relaxation
• A new reformulation-linearization technique for bilinear programming problems
• A simplicial branch-and-bound method for solving nonconvex all-quadratic programs
• Rigorous global search: continuous problems
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• A relaxation method for nonconvex quadratically constrained quadratic programs
• \(\alpha BB\): A global optimization method for general constrained nonconvex problems
• A branch-and-reduce approach to global optimization
• BARON: A general purpose global optimization software package
• A branch and cut algorithm for nonconvex quadratically constrained quadratic programming
• An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• Jointly Constrained Biconvex Programming
• An algorithm for nonconvex programming problems
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Rigorous Lower and Upper Bounds in Linear Programming
• On Polyhedral Approximations of the Second-Order Cone
• Semidefinite relaxations of fractional programs via novel convexification techniques
• Benchmarking optimization software with performance profiles.