Global Optimization Algorithm For Nonconvex Optimization Problems

Global optimization porblems abound in economic modeling, finance, networks and transportation, databases, chip design, image processing, chemical engineering design and control, molecular biology, and environmental engineering. Since there exist multiple local optima that differ from the global solution, and the traditional minimization techniques for nonlinear programming are devised for obtaining local optimal solutions, they can not be used smoothly to solve the global optimization problems. During the past several decades, great development has been obtained in the theoretical and algorithmic aspects of global optimization due to the important practical applications. These developed approaches mainly consist of two categories:deterministric approaches and stochastic approaches.In this thesis, some global optimization methods for several nonconvex optimization problems are developed. In Chapter 1, a brief introduction is given to the existing main classes of deterministic global optimization approaches. In Chapter 2, global optimization algorithms for globally solving the linear multiplicative programming problem(LMP) over a compact convex set are proposed. In Section 2.2, by using suitable transformation, (LMP) can be converted into an equivalent parametric convex programming, parametric concave minimization problem or parametric D.C. programming problem. Then (LMP) can be solved by convex programming and univariate search. Given a nonempty, compact convex set, a test problem constructed by the procedure has the form of problem (LMP) and in general will possess local maxima that are not global maxima. In Section 2.3, by introducing auxiliary variables, we firstly convert problem (LMP) into an equivalent nonconvex programming problem. Then, the equivalent problem of (LMP) is reduce to a sequence of linear programming problems through the successive refinement of a linear relaxation of feasible region and of the objective function by the convex envelope of the bilinear function. In Section 2.4, a simplicial branch and bound duality-bounds algorithm for globally solving the problem (LMP) is presented. The branch takes place in a space of only dimension p, where p is the number of terms in the objective function of problem (LMP). By using the Lagrangian weak duality theorem of nonlinear programming, the lower bound of (LMP) can be found by solving an ordinary linear program. These feasible solutions of (LMP) are found from dual optimal solutions of these linear programming. In Chapter 3, global optimization algorithm for a class of multiplicative programming with exponent (MPE) under multiplicative constraints is proposed. In Section 3.2, the deleting technique, which is given for cut away a large part of the currently investigated region in which the globally optimal solution of MPE does not exist, can accelerate the convergence of the proposed global optimization algorithm. In Section 3.3, by the logarithmic property to the problem MPE, an equivalent problem of MPE can be obtained. Then, utilizing the parametric linearization relaxation method, equivalent problem is reduce to a sequence of linear programming problems through the successive refinement of a linear relaxation of feasible region and of the objective function. In Section 3.4, by utilizing a transformation, can convert initial nonlinear function into D.C. function, then using a new linearization technique tosystematically can convert a MPE problem into a series of linear programming problems. In Chapter 4, we present an global optimization algorithm for solving the D.C. multiplicative programming (P) over a convex compact subset. We firstly convert problem (P) into an equivalent D.C. programming problem by introducing auxiliary variables. Then we solve the equivalent D.C. programming problem by branch and bound method and outer approximation algorithm. In Chapter 5, presents a global optimization algorithm for globally solving the sum of convex-concave ratios problem over a compact convex set. In Section 5.2 we demonstrate how to convert convex-concave ratios problem into an equivalent nonlinear problem. By using the convex envelope of the bilinear function and the special property of quadratic function, we will illustrate how to generate the convex relaxation program for equivalent problem in Section 5.3. And the branch and bound algorithm for globally solving the sum of convex-concave ratios problem is presented. In Chapter 6, we presents a two-part parametric linearization technique for globally solving the sum of sum of generalized fractional programming problem(GFP). In Section 6.2, two-part parametric linearization method is presented for generating the relaxed linear programming of (GFP). In Section 6.3, we describe the proposed branch-and-bound algorithm in which the relaxed subproblems are embedde, and the convergence of the algorithm is established.