A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems

DOI10.1016/J.AMC.2004.10.024MaRDI QIDQ2572774zbMATH OpenOpenAlexFDO

Authors H. Xue, Yuelin Gao, Peiping Shen

Publication date 4 November 2005

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2004.10.024

zbMATH Keywords

algorithmBranch-and-bound methodconvergence accelerationGlobal optimizationNonconvex quadratic programmingnumerical experimentsRectangle reducing tactics

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

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.

Recommendations

• A new bound-and-reduce approach of nonconvex quadratic programming problems
• A branch and cut algorithm for nonconvex quadratically constrained quadratic programming
• A branch and bound algorithm for nonconvex quadratic programming with quadratic constraints
• A branch-and-bound reduced method for a class of non-negative integer quadratic programming problems
• A novel optimization method for nonconvex quadratically constrained quadratic programs
• A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• A reformulation-convexification approach for solving nonconvex quadratic programming problems
• A branch and bound reduced algorithm for quadratic programming problems with quadratic constraints
• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

Cites work

• A finite algorithm for solving general quadratic problems
• A Method for Solving the Indefinite Quadratic Programming Problem
• A parallel algorithm for constrained concave quadratic global minimization
• An algorithm for global minimization of linearly constrained quadratic functions
• Bilinear programming and structured stochastic games
• Checking local optimality in constrained quadratic programming is NP- hard
• Constrained global optimization: algorithms and applications
• Generalized Benders decomposition
• Global minimization of indefinite quadratic problems
• Global minimization of large-scale constrained concave quadratic problems by separable programming
• Global optimization of multiplicative programs
• scientific article; zbMATH DE number 3892947 (Why is no real title available?)
• scientific article; zbMATH DE number 970356 (Why is no real title available?)
• Introduction to global optimization
• Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem
• Some NP-complete problems in quadratic and nonlinear programming
• The Indefinite Quadratic Programming Problem

Cited in

(6)

• A parametric linearizing approach for quadratically inequality constrained quadratic programs
• A novel optimization method for nonconvex quadratically constrained quadratic programs
• Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs
• An accelerating algorithm for globally solving nonconvex quadratic programming
• A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming
• A new bound-and-reduce approach of nonconvex quadratic programming problems

This page was built for publication: A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2572774)