Approximation Algorithms For Generalized Nonlinear Fractional Programs

Non-convex optimization problems are an important class of optimization problem-s. They are widely used in the fields of molecular biology, environmental engineering, information technology, industrial manufacturing and so on. From a research point of view, these problems exist many local optimal solutions which are not the global optimal solution, and so, it is difficult to solve them. Recently, it is attracted the interest of researchers, and more and more methods are reported for solving these problems. How-ever, most of the methods are either lack of the complexity analysis of the algorithms or no performance guarantee of the solutions obtained. This paper proposes approximation algorithms for solving two special types for a class of generalized fractional programming problems respectively. We not only prove that these approximation algorithms can obtain an approximation solution for the origin problems, but also give the detailed computa-tional complexity analysis of these algorithms. It is proved that they are fully polynomial time approximation schemes when the number of ratio terms is fixed in the objective function. The main contents of this paper are as follows:In Chapter 1, we first give optimization problems that will be considered in this paper. Next, we present the significance of theoretical research and applications practical and related work of these optimization problems. Finally, the main work of this paper is briefly introduced.In Chapter 2, an approximation algorithm is presented for solving a class of nonlinear fractional programming problems where the objective function is a polynomial fractional function with positive coefficients. By introducing new variables, we transform the primal problem into an equivalent problem. According to the characteristics of the equivalent problem, the approximation algorithm is designed for solving the origin problem. The convergence and complexity of the algorithm are proved, and the numerical result shows that the algorithm is feasible and effective.In Chapter 3, we consider a class of generalized fractional programming problem with special properties. By the similar method in chapter 2, we transform the origin problem into an equivalent problem, and we design an approximation algorithm to solve the equiv-alent problem with its characteristics, thus we can obtain an an approximation solution for the origin problem. Moreover, the convergence and complexity of the algorithm are proved, and the numerical result shows that it is a feasible and effective algorithm.