Global Optimization Algorithm For Several Kinds Of Fractional Programming Problems And Its Application

Fractional programming is an extremely important problem in the field of optimization.It usually has many non-global local optimal solutions,so it is a sharp challenge to solve the fractional programming problem.At the same time,the fractional programming problem has been involved in systems engineering,financial management,biological molecular science and other fields.Therefore,many scholars have studied the fractional programming problem,at present,they have proposed level set algorithm,approximate algorithm,heuristic algorithm and so on.This paper puts forward different relaxation skills and optimization algorithms for several special types of fractional programming problems.The details are as follows.1.Based on the image space branch-and-bound scheme,the minimax linear fractional programming problem is solved globally.Firstly,the original problem is equivalently transformed.Next,the convex hull and concave hull approximation of bilinear function is used to relax its equivalent problem,and the resulting linear relaxation problem will be used to calculate the lower bound of the optimal value of the equivalent problem.By continuously thinning the initial image space rectangle,it can be proved that the algorithm converges globally to the optimal solution of the equivalent problem.In addition,we provide the convergence proof and computational complexity analysis of this algorithm.Finally,experimental comparisons show that this algorithm has better computational performance.2.A deterministic global algorithm is proposed to solve the linear fractional sum problem.Firstly,several auxiliary variables are introduced to compress the fraction space.Then,by using algebraic operations and convex hull and concave hull approximation of functions to propose a new two-stage relaxation method,we can obtain the relaxation problem.Secondly,based on the characteristics of branch-and-bound strategy,relaxation problem and equivalence problem,a deterministic global algorithm and its convergence proof are given.Finally,the maximum number of iterations of this algorithm is estimated,and experimental comparisons verify the feasibility and robustness of the algorithm.3.An image space algorithm is proposed for solving the generalized linear fractional multiplicative problem globally.Firstly,some image space variables are introduced for equivalent transformation.Secondly,to construct a linear relaxation programming problem of its equivalent problem,on the one hand,we use the geometric properties of exponential and logarithmic functions to relax the objective functions in the equivalent problem,and on the other hand,we use algebraic relationships to linearly relax the constraint functions in the equivalent problem.Next,by solving a series of relaxation problems,the upper and lower bounds of the original problem are constantly updated,by combining the branch-and-bound framework,an image space algorithm is proposed to solve the equivalent problem,and the global optimal solution of the original problem is obtained.Finally,the global convergence of the algorithm is proved,and the maximum number of iterations required for the algorithm in the worst case is estimated for the first time.Numerical experimental results verify the effectiveness of the algorithm.