A hybrid global algorithm for linear plus linear fractional programs

The linear plus linear fractional (LPLF) problem is an important non-convex optimization model with applications in economics, engineering, and resource allocation. This paper introduces a globally convergent algorithm for the general LPLF problem. We first show that the problem can be reformulated as a fractional program whose numerator is a quadratic function with a Hessian that has at most one negative eigenvalue. This structural insight allows parametric subproblems from the Dinkelbach transformation to be classified as convex or nonconvex. We then propose a hybrid global algorithm combining Dinkelbach’s method with a branch-and-bound approach tailored to quadratic programs with a single negative eigenvalue. An application to two-stage network DEA enables exogenous assignment of stage weights, enhancing interpretability across decision-making units. Numerical experiments demonstrate that the proposed algorithm significantly outperforms the existing method in computational speed and scalability.