Research On Branch And Bound Algorithms For Two Kinds Of Non-convex Programming Problems

As a typical deterministic global optimization method,branch and bound algorithm can be used for the global optimization of some non-convex programming problems.For two kinds of non-convex problems,quadratically constrained quadratic programming and fractional programming,respectively,branch and bound algorithms are proposed.Specific work is described as follows:For quadratic programming with quadratic constraints,two branch and bound algorithms are proposed.In the first parameterized linear relaxation branch and bound algorithm,the bilinear function is reconstructed on a bounded closed interval by introducing parameters with fixed parameters of 0 or 1.The parametric linear relaxation technique is obtained by using the analytical properties of the reconstructed function.The branch operation uses the hyper-rectangular standard dichotomy.The second adaptive linear relaxation branch and bound algorithm also introduces parameters,and the parameters are adaptive.By approximating bilinear functions with upper and lower bounds on bounded closed intervals,the adaptive linear relaxation technique is obtained.The branch operation uses the hyperrectangular conditional dichotomy.In addition,it is proved that the two algorithms are both convergent,and the numerical results show that the two algorithms are feasible and effective.The advantages and disadvantages of the two are compared through the numerical results.For the sum of linear fraction programming,the output-space branch and bound algorithm is proposed.By introducing a small number of new variables,the non-convexity of the original problem is transformed into the output-space of the input variables with small dimensions,and the analytical properties of the one-ratio linear functions on bounded closed intervals are studied,and a new linear relaxation technique is presented.The branch operation adopts the output space dichotomy.Moreover,it is proved that the proposed algorithm is convergent,and the numerical results show that the proposed algorithm is feasible and effective.For quadratic fractional programming,a new branch and bound algorithm is proposed.By diagonalizing a real symmetric matrix and transforming it into equivalent,a linear fractional relaxation technique is proposed for quadratic fractional programming.The numerator and denominator of the objective function of the equivalent problem are linearly relaxed,which can be converted into simple linear programming for solving.The branch operation uses the standard rectangular dichotomy.Furthermore,it is proved that the algorithm is convergent,and the numerical results show that the algorithm is feasible and effective.