Research On Branch And Bound Algorithms For Non-convex Quadratic Programs

In engineering practice and management science,many problems can be reduced to nonconvex quadratic programming problems.Based on the analytic properties of the non-convex quadratic objective function of the problem,four new linear relaxation bounded strategies are proposed.Four deterministic global algorithms are designed with the framework of branch and bound algorithm.The main contents are as follows:In the first part,the quadratic objective function is rewritten into the difference form of two convex functions,and on the basis of the equivalent problem,a new linear programming relaxation subproblem,rectangular partition method and reduction technique are given respectively,and then a branch and bound algorithm based on the square variance formula is proposed.In the second part,a new equivalent problem of objective function with bilinear structure is constructed by using orthogonal trigonometric decomposition method of matrix.A new relaxation subproblem of linear programming is constructed by applying appropriate linear relaxation to the objective function,and a second branch and bound algorithm based on orthogonal trigonometric decomposition is proposed,which also includes rectangular reduction technique.In the third part,the objective function is reconstructed into an equivalent problem with bilinear structure without any matrix decomposition method.Secondly,the objective function of the equivalent problem is linearized and relaxed by using the monotonicity of univariate linear function.Finally,a third branch and bound algorithm based on vector inner product with reduction technique is proposed.In the fourth part,the full rank decomposition of matrix is used to transform the objective function into another form with bilinear structure,and the equivalent problem is obtained by introducing auxiliary variables.Based on the idea of branching in the space where auxiliary variables reside,a new linear relaxation technique and a branch and bound algorithm for output space are proposed.The effectiveness and feasibility of the four algorithms are verified by a large number of numerical experiments.