A Class Of Two-Stage Algorithm For Solving Non-Convex Quadratic Programming

Non-convex quadratic programming is an important model in constrained optimization.It has a wide range of applications in the fields of economics,engineering design,investment portfolio,etc.It has received a lot of attention in recent years.Different from the convex quadratic programming problem,to solve the global optimal solution of the non-convex quadratic programming is usually NP-hard,which makes the design of the algorithm for solving non-convex quadratic programming a certain degree of challenge.In recent years,great progress has been made in the research of non-convex quadratic programming algorithms,but there are still some shortages in terms of solving scale,calculation time and other indicators.In this paper,based on the recently proposed linearization method,a new strategy for solving non-convex quadratic programming is proposed,namely the two-stage construction method.Based on this strategy,the global and local algorithms for solving non-convex quadratic programming are constructed.The corresponding convergence analysis are established and preliminary numerical calculations are performed.The specific content of this article are as follows:Firstly,we introduce the research progress of current non-convex quadratic programming,summarize the existing branch and bound method and semi-definite relaxation techniques for solving non-convex quadratic programming problems,and give the research content of this paper.Secondly,based on the existing DIRECT algorithm,a global algorithm for solving non-convex quadratic programming is proposed.First construct a non-convex quadratic programming as an equivalent two-stage optimization problem,and then use the continuity of the optimal value function to establish the global convergence of the algorithm.Thirdly,by alternative solving the first and second stage problem of the two-stage optimization problem,the local algorithm for non-convex quadratic programming is obtained.The convergence analysis of the algorithm is established.The analysis shows that the solution sequence generated by this algorithm converges to a ? local optimal solution for non-convex quadratic programming.Finally,preliminary numerical experiments are performed on global and local algorithms,and corresponding numerical results are given.Numerical experiments show that the two algorithms can obtain the global and approximate local optimal solutions of non-convex quadratic programming.Moreover,the proposed algorithm is applied to a practical problems in real life,providing an effective way to solve a practical problem.