The Study On The Exact Solution Of Quadratically Constrained Quadratic Programming Problems

Nonconvex quadratically constrained quadratic program(QCQP)is an NP-hard problem.If P NP,we can not solve the problem in polynomial time.For a general nonconvex QCQP problem,one perspective is using a convex relaxation method combining with a branch and bound method to find a global optimal solution,another perspective is reformulating the primal problem as an equivalent conic programming problem over cones of nonnegative quadratic functions and using the computable cone covering method to solve it.In this thesis,we first study a type of QCQP problem that has hidden convexity—the extended trust region subproblem(eTRS).We complement the work that Burer et al.have done on this problem in the literature.They proved the existence of the optimal solution of this type of eTRS,we further give a recovering algorithm for the optimal solution of eTRS involving three linear constraints,the algorithm also works for most cases that eTRS has more than three linear constraints except for one special situation.Next,we propose an angle division based branch and bound algorithm for solving a quadratic program involving one rank-two concave constraint.The efficiency of such algorithm is better than SDP relaxation and linear relaxation based algorithms.Finally,we design four different branch and bound algorithms for globally solving general eTRS and compare their running efficiencies.Numerical experiment shows that adding second order cone constraints to SDP yields the improvement of the branch and bound efficiency significantly.It also shows that the algorithms branching along certain eigenvectors are generally more efficient than those branching along axles.The main innovation points of this thesis are:? Based on the rank-one decomposition of semidefinite matrix,we first propose an algorithm on recovering the optimal solution of the extended trust region subprob-lem when the number of linear constraints of eTRS is three,the algorithm also works for most cases when eTRS has more than three linear constraints.? We consider the two eigenvectors corresponding to the negative eigenvalues of the quadratic term's matrix of the nonconvex constraint together and establish a relaxation model based on angle division,then design a branch and bound algorithm with the parameter of angle for nonconvex quadratic program,numerical experiment shows that such algorithm is more efficient than the traditional convex relaxation based branch and bound algorithms.? We add the second order cone constraints to the SDP relaxation in order to enhance the lower bound,and branch along some eigenvectors for globally solving eTRS,numerical experiment shows that such algorithm is more efficient than those proposed in recent literatures.