TY - JOUR
T1 - Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem
AU - Jiao , Hongwei
AU - Shang , Youlin
JO - Journal of Computational Mathematics
VL - 1
SP - 203
EP - 228
PY - 2024
DA - 2024/11
SN - 43
DO - http://doi.org/10.4208/jcm.2203-m2021-0085
UR - https://global-sci.org/intro/article_detail/jcm/23536.html
KW - Sum of affine ratios, Global optimization, Affine relaxation problem, Branch-reduction-bound, Computational complexity.
AB - <p style="text-align: justify;">This article presents an image space branch-reduction-bound algorithm for globally
solving the sum of affine ratios problem. The algorithm works by solving its equivalent
problem, 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 be
used to compute the lower bounds during the branch-and-bound search. By subsequently
refining 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. For
improving the convergence speed, an image space region reducing method is adopted for
compressing the investigated image space rectangle. In addition, the global convergence of
the algorithm is proved, and its computational complexity is analyzed. Finally, comparing with some existing methods, numerical results indicate that the algorithm has better
computational performance.</p>