Relaxed Branch and Bound Method for General Quadratic
Programming Problems with Quadratic Constraints
Gao Yuelin,Xu Chengxian
(School of Sciences, Xi'an Jiaotong Univercity 710049,China)
Abstract:The solution of general quadratic programming problems with quadratic constraints is concerned. When all the quadratic constraints are not convex, a strategy is proposed either to relax one of the quadratic constraints into a convex quadratic constraint or to add a ball constraint in the original problem. The feasible region of the original problem is included in the feasible region of the relaxed quadratic programming problem. A projection subgradient algorithm for the Lagrangian dual problem of the relaxed quadratic problem is employed to general lower bounds of the optimal value for the original problem. An upper bound of the optimal value of the original problem is obtained and adjusted from the generated feasible points in the iteration process. The proposed algorithm either terminates after finite iteration when the upper and lower bounds of the optimal value are equal, or generates an infinite sequence and any convergent subsequence of the sequence gives a global solution of the problem.
Keywords:global optimization;branchandbound method;Lagrangian duality;projection subgradient method