DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs

摘要

The difference-of-convex (DC) decomposition is an effective method for designing a branch-and-bound algorithm. In this paper, we design two new branch-and-bound algorithms based on DC decomposition, to find global solutions of nonconvex box-constrained quadratic programming problems, and compare the efficiency of the proposed algorithms with two previous state-of-the-art branch-and-bound algorithms. Numerical experiments are conducted to show the competitiveness of the proposed algorithms on 20-60 dimensional box-constrained quadratic programming problems.