Branch And Bound Method For Globally Solving Several Programming Problems

Global optimization is an important branch in the feld of optimization theory. Comparedwith local optimization, its theoretical and related computational methods are not very matureand perfect. Since global optimization problem may be non-convex, i.e. it may be containmultiple local optimal solutions that are not globally optima, there exists computational diff-culty to identify their global optimality. Moreover, because many practical problems are as-sociated with non-convex global optimization problem closely, so it has practical signifcanceto study methods for globally solving non-convex problem. In the past few decades, manyglobal optimization algorithms have been presented by researchers. These algorithms can beclassifed into deterministic and stochastic algorithms, for example, deterministic algorithmincludes branch-and-bound method, flled function method and integral level set method, etc.;stochastic algorithm includes simulated annealing method, genetic method and ant colonyoptimization method, etc.Under the framework of branch and bound algorithm, this paper studies several specialnonlinear programming, including generalized geometric programming, generalized geomet-ric fractional programming, generalized sum of linear ratios fractional programming and gen-eralized linear multiplicative programming, etc., and presents some effective methods. Thework has been done includes fve facets are listed as follows:For generalized geometric programming problem, a global optimization algorithm isdeveloped based on a new linearization technique. Furthermore, in order to improve the con-vergence speed of this algorithm, a new pruning technique is proposed, which can be used tocut away a large part of the current investigated region in which the global optimal solutiondoes not exist. Convergence of this algorithm is proved, and some experiments are reportedto show the feasibility and effciency of the proposed algorithm.For generalized geometric fractional programming problem under geometric con-straints, frstly, by using an equivalent transformation and a new linear relaxation technique, anew effective branch and bound algorithm is presented. Then, some accelerating techniquesare proposed to improve the convergence speed of the proposed algorithm. Numerical resultsare reported to show the feasibility and effciency of our algorithm.For the programming problem with a concave function sum of products of two linearfunctions, a simplicial branch and bound algorithm is developed by using convex envelopeand simplicial subdivision. Compared with other methods, numerical experiments show thesuperiority of this method.For generalized sum of linear ratios fractional programming problem, by utilizing thecharacteristic of the problem, convex separation technique and a two-part relaxation tech- nique, the initial problem is solved by converted to solve a sequence of linear programmingproblems. Meanwhile, to improve the convergence speed of this algorithm, some accelerat-ing techniques are introduced. The convergence of this algorithm is established, and someexperiments are reported to show the feasibility and effciency of the proposed algorithm.For generalized linear multiplicative programming problem, through using an equiva-lent transformation frstly, an equivalent problem can be obtained. Then, two new linearizationmethods are proposed by utilizing the characteristic of the equivalent problem. Furthermore,two deterministic global optimization algorithms are presented based on these two lineariza-tion methods. Finally, for improving the convergence speed of the proposed algorithms, someaccelerating techniques are discussed. Numerical results show that our algorithms can fndthe global optimal solution of the initial problem effectively.