Optimization Methods For Solving Two Types Of Nonconvex Programming Problems

As is known to all,the non-convex programming problems usually have multiple non-global local optimal solutions,which increases the difficulty of solving and is a typical NP-hard problem.At the same time,the nonconvex programming problems can be widely applied in in investment portfolio and optimization,economy,trade,engineering optimization design and so on,which has attracted the attention of many researchers.In recent years,a variety of methods to solve this kind of model have been proposed,such as heuristic algorithm,level set algorithm,branch and bound algorithm and so on.In this paper,for a class of Minimax fractional programming problems and a special kind of DC programming problem,the iterative algorithm and branch and bound algorithm are given respectively according to the characteristics of these two kinds of problems.The main contents are as follows:In Chapter 1,we first give two classes of problems studied in this paper,then introduce the research background,theoretical significance and the current relevant researches of these two kinds of models respectively.Finally,we present the main contents of this paper.In Chapter 2,an iterative algorithm is proposed for the Minimax fractional programming problem.First of all,the original problem is transformed into its equivalent problem by introducing variables.Then,we express each constraint function of the equivalent problem as the ratio of two polynomials with positive coefficients.Next,based on the different selection of y,the equivalent problem is compressed into a geometric programming problem which is easy to solve by using the compression method.In this way,the solution of the original problem can be obtained indirectly by solving a series of geometric programming problems.In the end,the convergence of the algorithm is given.And the numerical results show that the algorithm is feasible and effective.In Chapter 3,a branch and bound algorithm is proposed for a special kind of DC programming problem.In the first place,the original problem is transformed into its equivalent problem,then the equivalent problem is relaxed by utilizing the convex relaxation technique,to determine the lower bound of the optimal value of the original problem.Hence,the optimal solution and the optimal value of the original problem are obtained by solving a series of convex programming problems.In addition,a compression method based on feasibility is presented to accelerate the iteration of the algorithm.Finally,the convergence of the algorithm is shown.And the numerical results indicate that the algorithm is feasible and effective.