Shen Peiping, Zhang Tongli, Wang Chunfeng
College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007 P.R. China.
J Inequal Appl. 2017;2017(1):147. doi: 10.1186/s13660-017-1420-1. Epub 2017 Jun 24.
This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an exploration of a suitably defined nonuniform grid. The main work of the algorithm involves checking the feasibility of linear programs associated with the interesting grid points. It is proved that the proposed algorithm is a fully polynomial time approximation scheme as the ratio terms are fixed in the objective function to problem (P), based on the computational complexity result. In contrast to existing results in literature, the algorithm does not require the assumptions on quasi-concavity or low-rank of the objective function to problem (P). Numerical results are given to illustrate the feasibility and effectiveness of the proposed algorithm.
本文提出了一种新的近似算法，用于全局求解一类广义分式规划问题（P），其目标函数被定义为仿射函数比值的适当组合。为了解决这个问题，该算法通过探索一个适当定义的非均匀网格来求解一个等价的优化问题（Q）。该算法的主要工作包括检查与感兴趣的网格点相关的线性规划的可行性。基于计算复杂度结果，证明了所提出的算法是一个完全多项式时间近似方案，因为目标函数中与问题（P）相关的比值项是固定的。与文献中的现有结果相比，该算法不需要对问题（P）的目标函数的拟凹性或低秩性做假设。给出了数值结果以说明所提算法的可行性和有效性。
