The Study On The Global DC Algorithm For Single Quadratically Constrained Non-convex Quadratic Quadratic Programming

The non-convex quadratic programming(QP)problem has a wide range of applications in the fields of engineering,economic management and finance.The non-convex QP problem with multiple quadratic constraints is one of the most challenging continuous optimization problems.It is well-known that finding its global optimal solution is NP-hard.The non-convex QP problem with a single quadratic constraint is a generalized trust region sub-problem,which has important applications in compression sensing and double well potential problems.According to the classic S-Lemma,such a problem can be transformed into a semi-definite programming(SDP)problem,which is solvable in polynomial time,but the SDP method cannot solve largescale problems.This paper aims to study the global optimization algorithm for the large-scale single quadratically constrained non-convex QP problem,and conduct numeric experiments to evaluate the performance of the proposed algorithm.(i)This thesis studies the global DC(Difference of Convex function,DC)algorithm for the non-convex QP problem with a single convex quadratic constraint.First,we use an ellipsoid transformation technique to transform the convex quadratic constraint into a spherical constraint,and hence the original problem can be transformed into a classic trust-region subproblem.We then propose the DC algorithm for the transformed trust-region subproblem,and prove it converges to the KKT point of the original problem.Based on the KKT point found by the DC algorithm and the global optimality condition of the trust-region subproblem,we propose a method to find a new initial feasible point.Combining this method,we propose a global DC algorithm for a single convex quadratic constrained non-convex QP problem.Numerical experiments show that the proposed global DC algorithm can effectively find the global optimal solution of large-scale singly quadratically constrained non-convex QP problems.(ii)This thesis further studies the global DC algorithm and its numerical implementation for the non-convex QP problem with a single non-convex quadratic constraint.The non-convex quadratic constraint is decomposed into a DC function,then we use the linear function to approximate the negative quadratic term in the constraints,and obtain a non-convex quadratic approximation problem with a convex quadratic constraint.Finally,based on the global DC algorithm for the non-convex QP problem with a single convex quadratic constraint,we propose a global DC algorithm for a single non-convex quadratic constrained non-convex QP problem,and prove it converges to the KKT point of the original problem.However,the numerical experimental results prove that the proposed global DC algorithm can effectively find the global optimal solution of a large-scale single non-convex quadratic constrained non-convex QP problem.