Global optimization algorithm for a class of linear ratios optimization problem

Abstract

We presented an image space branch-and-bound algorithm for globally minimizing the sum of linear ratios problem. In the algorithm, a new linearizing technique was proposed for deriving the linear relaxation problem. An image space region reduction technique was constructed for improving the convergence speed of the algorithm. Moreover, by analyzing the computational complexity of the algorithm, the maximum iterations of the algorithm were estimated, and numerical experimental results showed the potential computing benefits of the algorithm. Finally, a practical application problem in education investment was solved to verify the usefulness of the proposed algorithm.

Keywords

• sum of linear ratios
• global optimization
• image space branch-and-bound
• region reduction technique
• computational complexity