| Nonconvex programming has been widely concerned by scholars since the 1990s,and its applications include but are not limited to plant layout design and VLSI chip design.This paper considers a special class of nonconvex programming problems:linear multiplicative programming(LMP)problems.Based on different relaxation methods,two global optimization algorithms are proposed.The main contents of this paper are arranged as follows:The Chapter 1 gives the background knowledge of nonconvex programming,the model of the LMP problem,the research status at home and abroad and the research content of this paper.In Chapter 2,a spatial branch and bound algorithm with an adaptive branch rule is proposed.In the algorithm,the LMP problem is transformed into its equivalent problem.Then,based on piecewise linear approximations,an adaptive branching rule and branch and bound framework,the process of solving the LMP problem is transformed into solving a series of second order cone relaxation problems.In addition,the bound of the optimality gap in the iterative process is given,and the computational complexity of the algorithm is estimated as O((?)).Preliminary numerical results show that the algorithm can effectively find the global optimal solutions for test instances.In Chapter 3,an outer space branch and bound algorithm with an acceleration technology is presented to solve the LMP problem globally.Firstly,the LMP problem is transformed into an equivalent problem,and a linear relaxation technique is proposed.Subsequently,the process of solving the LMP problem is transformed into solving a series of linear programs.Secondly,the proposed region acceleration technique can delete the region that does not contain the global optimal solution of the original problem in the current search feasible region.Then,the convergence and computational complexity of the algorithm are given.Finally,the preliminary numerical results show that the proposed algorithm is feasible and effective. |
PDF Full Text Request