Optimization Online


A Branch and Bound Algorithm for Nonconvex Quadratic Optimization with Ball and Linear Constraints

Amir Beck(becka***at***ie.technion.ac.il)
Dror Pan(dror.pan***at***campus.technion.ac.il)

Abstract: We suggest a branch and bound algorithm for solving continuous optimization problems where a (generally nonconvex) objective function is to be minimized under nonconvex inequality constraints which satisfy some specific solvability assumptions. The assumptions hold for some special cases of nonconvex quadratic optimization problems. We show how the algorithm can be applied to the problem of minimizing a nonconvex quadratic function under ball, out-of-ball and linear constraints. The main tool we utilize is the ability to solve in polynomial computation time the minimization of a general quadratic under one Euclidean sphere constraint, namely the so-called trust region subproblem, including the computation of all local minimizers of that problem. Application of the algorithm on it sparse source localization} problems is presented.

Keywords: quadratically constrained quadratic problems; nonconvex programming; branch and bound; sparse source localization

Category 1: Global Optimization

Citation: submitted for publication

Download: [PDF]

Entry Submitted: 02/24/2017
Entry Accepted: 02/24/2017
Entry Last Modified: 02/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society