Relaxation Delimiting Methods For Several Kinds Of Nonconvex Optimization Problems

Nonconvex optimization is a kind of difficult problem in the optimization field,it is widely used in financial statistics,engineering design,data mining,securities portfolio,computer vision,image processing and pattern recognition,and many other fields.This kind of problem is difficult in both theoretical basis and algorithm implementation because there may be multiple non-globally optimal local extremum points and there is no global optimality criterion.At present,most of the existing algorithms are designed for nonconvex problems with small or medium scale or special structure,but the efficiency of solving large-scale problems is not high,or only the local approximate optimal solution of the original problem can be obtained.Based on the framework of branch-and-bound algorithm,this paper studies several kinds of non-convex optimization problems,combines the existing global optimization methods to construct a more simple,effective and easy to execute relaxation method and acceleration technique,designs global optimization algorithms with higher execution efficiency and better solving performance,and theoretically proves the global convergence of the algorithm.The feasibility and efficiency of the algorithm are verified by numerical experiments compared with existing algorithms.Its main contents are as follows:1.An accelerated linearization algorithm based on the branch and bound method is proposed for nonconvex quadratic programming problem.By using a new linear relaxation method,the initial nonconvex quadratic programming problem is transformed into a series of linear relaxation programming problems,and the lower bound of the optimal solution of the original problem is obtained by solving the linear relaxation programming problem.The interval deletion rule is adopted to quickly eliminate the unsolvable subregion,and the convergence speed of the algorithm is improved.Numerical experiment results show that the algorithm has high efficiency.2.For sum of linear fractional programming problem,a branch and bound algorithm based on outcome space is proposed,which requires only a non-zero denominator in a given region.Through the transformation of equivalent problems,affine relaxation programming of equivalent problems is established by using the linear approximation property of bilinear functions.By combining the relaxation model with the branch-and-bound framework,a branch-and-bound algorithm in the outcome space is designed to solve the problem.Because the regional subdivision in the process of the algorithm takes place in the outcome space,its dimension is equal to the number of fractions rather than the variable dimension space,thus effectively reducing the computational complexity of the algorithm.The results of numerical experiments show that the algorithm is feasible and efficient.3.Two global algorithms based on fractional linearization and denominator linearization are proposed for minimax linear fractional programming problem.In order to solve the global optimal solution of this problem,using the structural characteristics of the minimax linear fractional programming problem,the equivalent problem is transformed into a linear relaxation programming problem by introducing additional variables,and two branch and bound solving algorithms are established by different linearization methods.Then,by solving a series of linear relaxation programming problems,the lower bound of the optimal solution of the original problem is approached infinitely.The proof of the global convergence and the maximum number of iterations are given,and the feasibility and effectiveness of the algorithm are demonstrated by numerical results.4.A new global optimization algorithm for sum of quadratic fractional programming problem with quadratic constraints is designed by using the properties of parametric linear relaxation functions.By means of the new parametric linearization method,the upper and lower bounds of the quadratic objective function and constraint function are obtained,the original problem is transformed into a linear relaxation programming problem that is easy to solve.The optimal solution of the original problem is obtained by continuously solving the iterative subproblem of the relaxation programming,and the global convergence of the algorithm is proved.A large number of random experimental examples are tested,and the numerical results are compared with those of the algorithms in literature,which show that the proposed algorithm is efficient and feasible.