A potential practical algorithm for minimizing the sum of affine fractional functions

Abstract

This article presents and validates a potential practical algorithm for minimizing the sum of affine fractional functions over a polyhedron. During the branch and bound search, this algorithm computes the lower bounds by solving the affine relaxation problems of the equivalent problem, which are derived by utilizing a two-level affine relaxation technique. By successive refinement and successively solving a series of affine relaxation problems, the algorithm is convergent to the global minimum of the primal problem. Moreover, the gap between the objective function and its affine relaxation function is derived for the first time, and when the partition interval tends to be infinitesimal, the gap is infinitely close to zero. Furthermore, the maximum iterations of the proposed algorithm are derived by estimating its computational complexity. Some test problems are solved to verify the potential practical and computational advantages of the algorithm.

Keywords:

• Sum of affine fractional functions
• global optimization
• two-level affine relaxation technique
• branch and bound
• computational complexity

Acknowledgments

The authors are very grateful to the responsible editors and the anonymous referees for their valuable comments and suggestions, which have greatly improved the earlier version of this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This paper was supported by the National Natural Science Foundation of China [11871196; 12071133; 12071112], the China Postdoctoral Science Foundation [2017M622340], the Key Scientific and Technological Research Projects in Henan Province [202102210147, 192102210114], the Science and Technology Climbing Program of Henan Institute of Science and Technology [2018JY01], Henan Institute of Science and Technology Postdoctoral Science Foundation [103040116001/043], and Henan University Key Research Projects [19A110016].