arrow
Volume 43, Issue 1
Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem

Hongwei Jiao & Youlin Shang

J. Comp. Math., 43 (2025), pp. 203-228.

Published online: 2024-11

Export citation
  • Abstract

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.

  • AMS Subject Headings

90C26, 90C32

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-43-203, author = {Jiao , Hongwei and Shang , Youlin}, title = {Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem}, journal = {Journal of Computational Mathematics}, year = {2024}, volume = {43}, number = {1}, pages = {203--228}, abstract = {

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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2203-m2021-0085}, url = {http://global-sci.org/intro/article_detail/jcm/23536.html} }
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 -

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.

Jiao , Hongwei and Shang , Youlin. (2024). Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem. Journal of Computational Mathematics. 43 (1). 203-228. doi:10.4208/jcm.2203-m2021-0085
Copy to clipboard
The citation has been copied to your clipboard