IMAGE SPACE BRANCH-REDUCTION-BOUND ALGORITHM FOR GLOBALLY SOLVING THE SUM OF AFFINE RATIOS PROBLEM  

作　　者：Hongwei Jiao Youlin Shang 

机构地区：[1]School of Mathematical Science,Henan Institute of Science and Technology,Xinxiang 453003,China [2]School of Mathematics and Statistics,Henan University of Science and Technology,Luoyang 471023,China

出　　处：《Journal of Computational Mathematics》2025年第1期203-228,共26页计算数学(英文)

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.11871196,12071133,12071112);by the Key Scientific and Technological Research Projects of Henan Province(Grant Nos.232102211085,202102210147);by the China Postdoctoral Science Foundation(Grant No.2017M622340);by the Science and Technology Climbing Program of Henan Institute of Science and Technology(Grant No.2018JY01).

摘　　要：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.

关 键 词：Sum of affine ratios Global optimization Affine relaxation problem Branchreduction-bound Computational complexity 

分 类 号：O17[理学—数学]