A Relaxed and Bound Algorithm Based on Auxiliary Variables for Quadratically Constrained Quadratic Programming Problem
Open Access
- 16 January 2022
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 10 (2) , 270
Abstract
Quadratically constrained quadratic programs (QCQP), which often appear in engineering practice and management science, and other fields, are investigated in this paper. By introducing appropriate auxiliary variables, QCQP can be transformed into its equivalent problem (EP) with non-linear equality constraints. After these equality constraints are relaxed, a series of linear relaxation subproblems with auxiliary variables and bound constraints are generated, which can determine the effective lower bound of the global optimal value of QCQP. To enhance the compactness of sub-rectangles and improve the ability to remove sub-rectangles, two rectangle-reduction strategies are employed. Besides, two -subproblem deletion rules are introduced to improve the convergence speed of the algorithm. Therefore, a relaxation and bound algorithm based on auxiliary variables are proposed to solve QCQP. Numerical experiments show that this algorithm is effective and feasible.
Keywords
Funding Information
- National Natural Science Foundation of China (11961001)
- Construction Project of first-class subjects in Ningxia higher Education (NXYLXK2017B09)
- Major proprietary funded project of North Minzu University (ZDZX201901)
This publication has 35 references indexed in Scilit:
- New and old bounds for standard quadratic optimization: dominance, equivalence and incomparabilityMathematical Programming, 2007
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxationsMathematical Programming, 2006
- A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programsMathematical Programming, 2005
- Facility location models for distribution system designEuropean Journal of Operational Research, 2005
- A branch-and-cut algorithm for nonconvex quadratic programs with box constraintsMathematical Programming, 2004
- A polyhedral study of nonconvex quadratic programs with box constraintsMathematical Programming, 2004
- The trust region subproblem and semidefinite programming*Optimization Methods and Software, 2004
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A relaxation method for nonconvex quadratically constrained quadratic programsJournal of Global Optimization, 1995
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962