Approximation Algorithms For Two Types Of Nonconvex Programming Problems

As an important class of optimization problem,nonconvex programming problems can be widely used in economic?financial and investment?management science?system engineering and so on.Normally,this kind problem may have multiple locally optimal solutions,most of which fail to be globally optimal,and may be difficult to carry out.There are many ways to study these problems,such as heuristic methods,level set al-gorithm,branch and bound methods and so on.In this paper,two kinds of nonconvex programming problems are solved for global optimal solution by exploiting different ap-proximation algorithms based on the characteristics of these problems.The main contents are as follows:In Chapter 1,firstly,we present the optimization model,then introduce the research background?the current situation?theoretical significance,finally the main work in this paper is shown.In Chapter 2,an approximation algorithm is proposed for a class of convex multi-plicative problems,by introducing variables the solving process of the prime problem is transformed into a series of convex programming problems on the defined grid area which are easy to solve,then the optimal solution and the optimal value can be concluded.The proof of convergence and complexity analysis are given,and the comparison of the numerical results show that the algorithm is feasible.In Chapter 3,we consider a class of linear ratios by introducing variables and establish mesh region,the prime problem can be transformed and decomposed into a series of linear programming subproblems which are easy to solve,then we can obtain the optimal solu-tion of the prime problem by solving the equivalent problem and the proposed algorithm can acquire the global ?-approximation solution in theory,finally,the computational complexity analysis of the algorithm demonstrate this algorithm is fully polynomial time approximation algorithm.The results of numerical experiments show that the proposed algorithm has advantage in solving this class of problem.