A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints

DOI10.1007/s10898-017-0521-1zbMath1382.90082OpenAlexW2606666012MaRDI QIDQ1679484

Dror Pan, Amir Beck

Publication date: 9 November 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-017-0521-1

zbMATH Keywords

nonconvex programmingbranch and boundtrust region subproblemquadratically constrained quadratic problemssparse source localization

Mathematics Subject Classification ID

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

Related Items

An efficient algorithm for the extended trust-region subproblem with two linear constraints, On Local Minimizers of Nonconvex Homogeneous Quadratically Constrained Quadratic Optimization with at Most Two Constraints, On box-constrained total least squares problem, On the branch and bound algorithm for the extended trust-region subproblem, On indefinite quadratic optimization over the intersection of balls and linear constraints, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, KKT-based primal-dual exactness conditions for the Shor relaxation, Finding second-order stationary points in constrained minimization: a feasible direction approach, Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem, A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Nonconvex Optimization, An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem

Uses Software

• SCIP
• CVX
• GQTPAR
• QuadProgBB

Cites Work

• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Globally solving nonconvex quadratic programming problems via completely positive programming
• The trust region subproblem with non-intersecting linear constraints
• Graph Implementations for Nonsmooth Convex Programs
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• Computing a Trust Region Step
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Computing Optimal Locally Constrained Steps
• Newton’s Method with a Model Trust Region Modification
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• New Results on Quadratic Minimization
• Exact and Approximate Solutions of Source Localization Problems
• Second-Order-Cone Constraints for Extended Trust-Region Subproblems
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• On Cones of Nonnegative Quadratic Functions
• Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints