Global Polynomial Time Approximation Algorithms For Two Types Of Fractional Programming Problems

Global optimization has been widely used in the felds of molecular biology, economic,environmental engineering, information technology, industrial manufacturing and so on.But most of optimizational models abstracted from real life are non-convex, and existmany local optimal solutions which are not the global optimal solution. It is difcult tosolve them. Linear fractional programming is a special optimizational problem. In recentyears, it has attracted attention of many scholars, and has more and more solving methods.However, most of the methods don’t consider the computational complexity which is oneof the criteria to evaluate algorithms.This paper respectively proposes global polynomial time approximation algorithmsfor solving a linear sum-of-ratios fractional programming problem and a linear fractionalmultiplicative programming problem. The main contents of this paper are as follows:In Chapter1, several main global optimization approaches and the latest research de-velopment of problems studied in this paper are simply presented, and a brief introductionis given to related concepts of complexity and our work.In Chapter2, a polynomial time approximation algorithm is presented for globallysolving a linear sum-of-ratios fractional programming problem. By introducing new vari-ables, we transform the primal problem into a equivalent problem with box-constrained.According to the characteristics of the equivalent problem, the algorithm starts from thelower bound of the box to fnd the global optimal solution of the linear sum-of-ratios fractional programming problem. The convergence and complexity of the algorithm areproved, and the numerical examples show that the algorithm is feasible.In Chapter3, frstly, the general form of linear fractional multiplicative programmingproblem is transformed into special subproblems. Then according to the subproblemspresents a global polynomial time approximation algorithm for solving a linear fractionalmultiplicative programming. At last, the convergence and complexity of the algorithm areproved, and the numerical examples show that the algorithm is feasible.