Global Optimization For Sum-of-Ratios Problems

The research of global optimization mainly focuses on the global optimization problemsthat do not have convexity and the computational methods for solving these problems.Global optimization problems have been widely applied in economic plan, molecular biology,network and transportation and so on. Since there exist multiple local optimalsolutions that differ from the global optimal points, which are actually needed, therefore,studying algorithms for fingding a global optimal solution not only has important significance,but also has challenges extremely.Sum-of-ratios problem has attracted the interests of a growing number of researchers inrecent decades. This is at least in part because from a practical point of view, this problemhas a variety of applications. Included among these, for example, are economics, shippingproblems, and so on. From a research point of view, sum-of-ratios problem is a specialclass of global optimization problems, thus, it also faces theoretical and computationalchallenges. In this paper, we propose a new accelerating method based on known theoryand algorithms for some sum-of-ratios problems. Main contents are as follows:Firstly, a brief introduction is given to several main global optimization approachesand the latest development of these approaches. Then we introduce briefly our work andthe basic theory to be applied in this paper.Secondly, for the more general sum of linear ratios problem on a polytope, by utilizingan equivalent problem constructed and concave envelope of the objective function for the equivalent problem, we establish a relaxation linear programming and develop acceleratingmeasures ((DT) and (BTT)) to propose a new accelerating global optimization algorithm.The measures are incorporated into the branch-and-bound process as an accelerating device,so that the solution procedure is enhanced and the proposed algorithm has betterperformance. Numerical experiments show that computational efficiency can be improvedobviously, specially, the number of the brangching operations can be significantly reduced.Finally, we combine the global optimization method proposed by Shen et al. with asuitable deleting technique to propose a new accelerating trapezoidal algorithm for solvingnonlinear sum-of-ratios problem (SRP) over a convex set. This technique offers a possibilityto cut away all or a large part of the currently investigated region in which theoptimal solution of the equivalent problem of (SRP) does not exist, and can be seen as anaccelerating device for the global optimization algorithm of the nonlinear sum-of -ratiosproblem. The compared results in the numberical experiments show that the computationalefficiency is obviously improved by using this new technique.