A Socp Relaxation Based Branch-and-Bound Algorithm for Solving a Class of Generalized Sum-of-Linear-Fractions Programming Problems

This paper mainly studies a class of generalized sum-of-linear-fractions programming problems which have important applications in finance, economy and computational vision. In this process, we first propose a new method to re-represent the original problem as an equivalent problem (EP) with finite nonconvex constraints over the outer space. Secondly, by convexizing these constraints, a new convex relaxation subproblem (CRSP) is constructed for EP.In view of the special structure of the problem CRSP, it is reconstructed as a second-order cone programming (SOCP) problem, which is essentially a SOCP relaxation of EP. Thirdly, through the structural characteristics of the objective function of EP, a region reduction technique is designed to accelerate the termination of the algorithm as much as possible. By integrating the SOCP relaxation and acceleration strategy into the branch and bound framework, a new global optimization algorithm is developed. Further, the theoretical convergence and computational complexity of the algorithm are analyzed. Numerical experiment results reveal that the algorithm is effective and feasible