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

This paper investigated the linear ratio sum problem, a complex non-convex optimization problem with extensive applications in finance, economics, computer vision, and other fields. We proposed a novel global optimization approach that reformulated the original problem into an equivalent one with nonlinear constraints. The approach constructed linear fractional relaxation subproblems via constraint relaxation and leveraged the structural properties of the relaxations to transform these subproblems into linear programming formulations, thereby ensuring efficient computation. Furthermore, rectangular branching rules were designed based on the relaxed nonlinear constraints. These rules, complemented by region elimination techniques, accelerated convergence by exploiting the structure of the objective function. By integrating these components into a branch-and-bound framework, a novel global optimization algorithm was devised. Theoretical analysis confirmed the convergence and computational complexity of the proposed algorithm, while numerical tests validated its effectiveness and feasibility.