Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem (Journal of Computational Mathematics, 2024)
This article presents an image space branch-reduction-bound algorithm for globallysolving the sum of affine ratios problem. The algorithm works by solving its equivalentproblem, and by using convex hull and concave hull approximation of bilinear function,we can construct the affine relaxation problem of the equivalent problem, which can beused to compute the lower bounds during the branch-and-bound search. By subsequentlyrefining the initial image space rectangle and solving a series of affine relaxation problems,the proposed algorithm is convergent to the global optima of the primal problem. Forimproving the convergence speed, an image space region reducing method is adopted forcompressing the investigated image space rectangle. In addition, the global convergence ofthe algorithm is proved, and its computational complexity is analyzed. Finally, comparing with some existing methods, numerical results indicate that the algorithm has bettercomputational performance.