A Branch And Bound Algorithm For Two Classes Of Non-Convex Global Optimization Problems

During the past decades, with the development of science technique, especially theinformation technique develops, global optimization has been widely applied in economydesign, networks and transportation, image processing, detabases and chip design, molec-ular biology, environmental engineering and nuclear and mechanical design, finance andfixed charges. However, global optimization problems always exist multiple local optimalsolutions that di?er from the global solution, thus, studying global optimal solution forthis kind of problems has important significance and challenges extremely. In this paper,we propose two global optimization algorithms based on the known theory and algorithmsfor two classes of global optimization problems. The main contents are as follows:In Chapter 1, we make a brief introduction for some main deterministic approaches andstochastic approaches for solving global optimization problems, and their latest researchdevelopment. Then, the brie?y work is introduced in this article.In Chapter 2, we propose a branch and bound algorithm for globally solving a classof the sum of convex-convex ratios problem (NRP) with reverse convex constraints. First,we convert the problem (NRP) into a equivalent problem, then, we use Lagrangian dualitytheory to search the lower bound for the equivalent program by solving a sequence oflinear programming problems, and the feasible sloution of problem (NRP) for updating theupper bound can be obtained from the duality problem of the lower bound problem. Theconvergence analysis and the numerical experiments validate the e?ciency of the algorithm. The merits of this algorithm are that it only needs to solve the linear subproblems, andthe scale of these subproblems does not enlarge when the number of iterations increase.In Chapter 3, we present a global optimization method for golbally solving a classof non-convex quadratic problem (QP) with additional multiplicative constraints . Forminimizing the problem,the algorithm firstly constructs a equivalent problem, then usesLagrangian duality theory to convert the bounding subproblems during the algorithm intoa sequence of linear programming problem, which can be solved e?cently. Then we presentthe convergence analysis and the numerical examples to show the feasibility of the proposedalgorithm.