Journals
Resources
About Us
Open Access

Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem

Image Space Branch-Reduction-Bound Algorithm for Globally Solving the Sum of Affine Ratios Problem

Year:    2025

Author:    Hongwei Jiao, Youlin Shang

Journal of Computational Mathematics, Vol. 43 (2025), Iss. 1 : pp. 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.

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/jcm.2203-m2021-0085

Journal of Computational Mathematics, Vol. 43 (2025), Iss. 1 : pp. 203–228

Published online:    2025-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    26

Keywords:    Sum of affine ratios Global optimization Affine relaxation problem Branch-reduction-bound Computational complexity.

Author Details

Hongwei Jiao

Youlin Shang

  1. Global algorithm for effectively solving min-max affine fractional programs

    Jiao, Hongwei

    Sun, Yudong

    Wang, Wenjie

    Shang, Youlin

    Journal of Applied Mathematics and Computing, Vol. 70 (2024), Iss. 2 P.1787

    https://doi.org/10.1007/s12190-024-02027-1 [Citations: 1]