A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems (Q2572774): Difference between revisions

For solving nonconvex quadratic programming (QP) problems by the branch-and-reduce approach a new lower approximate linear function of the quadratic function over an \(n\)-rectangle is derived to calculate a lower bound on the global optimal value of the original problem over a rectangle which is necessary to develop the branch-and-bound algorithm. Thereafter a new simple rectangle partioning method is used and some ways for reducing and deleting subrectangles are described to accelerate the convergence of the proposed method.The convergence of the new branch-and-reduce algorithm to a global optimal solution of the original QP problems is proved. Executed numerical experiments show that the proposed algorithm is promising.