Research On Bound Relaxation Algorithms For Quadratic Constrained Quadratic Programming Problem

Quadratic constrained quadratic programming problem comes from many fields of science and engineering,economy and society,such as wireless communication,network security,data mining,image processing,economy and finance,ecological environment protection,etc.Generally,quadratic constraint quadratic programming problem is N-P hard problem.It is difficult to find the global optimal solution by using the traditional optimization methods such as the steepest descent method,Newton method,conjugate gradient method,quasi-Newton method,penalty function method,etc.Therefore,it is of great theoretical significance and application value to study the calculation method of the global optimal solution of quadratic constrained quadratic programming.In this dissertation,for nonconvex quadratic constrained quadratic programming problem,three relaxation and bound techniques and three different branching methods are given.Based on this,three branch and bound algorithms to find the global optimal solution to the problem are proposed,and the convergence analysis is carried out.Numerical experiments show that the proposed algorithms are feasible and effective.The specific content is as follows:Firstly,by introducing the auxiliary product variable,the quadratic constrained quadratic programming problem can be transformed into a linear combination nonlinear programming problem with only the product of auxiliary variable and decision variable,the auxiliary variable boundary relaxation technique is given,at the same time,the midpoint dichotomy method of hyper-rectangle in auxiliary variable space is given,the reduction strategy based on the linear function and the quadratic function of hyper-rectangle is introduced to enhance the compactness and deletion ability of the hyper-rectangle.Thus,a bound relaxation algorithm based on auxiliary variable for quadratic constrained quadratic programming problem is proposed.Secondly,still by introducing the auxiliary product variable,the quadratic constrained quadratic programming problem can be transformed into a linear combination nonlinear programming problem with only the product of auxiliary variable and decision variable,and the relaxation linear programming problem of the original problem is given by using the binary mean inequality,at the same time,the conditional dichotomy of the hyper-rectangle in the decision variable space is given.Thus,a bound relaxation algorithm based on binary mean inequality for quadratic constrained quadratic programming problem is proposed.Thirdly,for quadratic constrained programming problem with nonnegative decision variables,a bound relaxation technique based on decision variable is given,at the same time,a hyper-rectangular dynamic dichotomy method in decision variable space is given,and the reduction strategy based on the linear function of hyper-rectangle is used.Thus,a bound relaxation algorithm based on decision variable for quadratic constrained quadratic programming problem is proposed.