A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems

Abstract

This paper mainly studies the sum-of-linear-ratios 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). Secondly, by relaxing these constraints, a nonlinear relaxation subproblem is constructed for EP. In view of the special structure of the relaxation, 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.

Keywords

• global optimization
• fractional program
• branch and bound
• socp relaxation