Global Optimization Algorithms For Solving Two Classes Of Nonconvex Programming Problems

Nonconvex programming problems have many important practical applications such as plant layout design and bond portfolio optimization.In recent years,many scholars have proposed different algorithms,including approximation algorithm,outer approximation algorithm and branch-and-bound algorithm.In this thesis,we consider two classes of special nonconvex programming problems: linear multiplicative programming problem and sum of linear ratios programming problem.The corresponding global optimization algorithms for two classes of problems are given,respectively.The main contents are as follows:In Chapter 1,we propose two types of optimization problems studied in this thesis,and the application background as well as research status of the two problems.Finally,the main research contents of this thesis are presented.In Chapter 2,we study a class of linear multiplicative programming problems.First,the problem is transformed into an equivalent bilevel programming problem.With the help of the structure of equivalent problem we construct the convex quadratic programming problem to obtain the lower bound on the optimal objective function value of the equivalent problem.Second,a simplicial branch-and-bound algorithm is designed,which integrates the convex quadratic programming problem and simplicial branching process.Also,we establish the convergence and complexity analysis of the algorithm.Finally,the results of numerical experiments confirm the feasibility and efficiency of the proposed algorithm.In Chapter 3,we consider a sum of linear ratios programming problem.First,we convert the problem into an equivalent problem by introducing auxiliary variables.And,we obtain the convex relaxation of equivalent problem by means of relaxation techniques.Then,combined with the convex relaxation technique,adaptive branching rule and accelerating technique,a branch-and-bound algorithm is presented for globally solving the original problem.In addition,we prove the convergence results for the algorithm and give the complexity analysis of the algorithm.In the end,numerical results demonstrate the proposed algorithm can efficiently find the optimal solutions for test instances.