A practical acceleration optimization approach for the sum of affine fractions programming
摘要
The sum of affine fractions programming (SFP) constitutes a class of non-convex programming that has been proven to be NP-hard, presenting significant computational and theoretical challenges. To solve the SFP, we start by mapping the affine functions of the numerators and denominators in the SFP to the variables in image space, thereby converting the SFP into an equivalent problem (EQP). Then, by the convex-concave envelope approximation of the quadratic functions and bilinear relaxation techniques, the EQP is underestimated by the relaxation programming (RP). Additionally, some acceleration methods are introduced to eliminate invalid regions where no global optimal solution exists. Thus, an image space branch acceleration bound algorithm (ISBABA) is designed by merging relaxation and acceleration methods into the branch-and-bound framework. Additionally, the ISBABA is theoretically guaranteed to converge to global optima, with a detailed analysis of its worst-case computational complexity. Finally, some experiments and application instances are conducted to illustrate the high efficiency and robustness of the ISBABA.