线性分式多乘积规划问题的多项式时间近似算法

A Fully Polynomial Time Approximation Algorithm for Linear Fractional Multiplicative Programs

本文首先将一般形式的线性分式多乘积规划问题(MP),转化为特殊形式的子问题.再根据子问题提出一种求解(MP)的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.

In this article, we present a fully polynomial time approximation algorithm for solving a class of general linear fractional multiplicative programming（MP） problems. For solving the problem（MP）, we first convert the original problem（MP） into several subproblems where both the numerator and denominator of each ratio function are positive affine functions in the objective function. The proposed approximation algorithm can then find an ε-approximation solution for each subproblem. Thus, by using the subproblem solutions we can obtain an ε-approximation global optimization solution for problem（MP）, since the number of subproblem is finite. The convergence of the algorithm is proved, and an approximation fully polynomial time is given by analyzing the computational complexity of the algorithm.As the term p of fractional multiplicatives is fixed, there is a polynomial time dependency of the algorithm with respect to the inverse of the required precision, while there is an exponential time dependency with respect to p. Finally, the numerical examples show that the algorithm is feasible.