Some Deterministic Methods For Global Optimization

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, several deterministic approaches of global 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, some convex-ification and concavification methods are given for some kinds of global optimization problems with special structures. Then these global optimization problems can be converted into equivalent convex programming problems or concave minimization problems or reverse convex programming problems or D.C. programming problems. Since any local minimum of a convex programming problem is a global minimum, if a programming problem can be converted into an equivalent convex programming problem (which is called a hidden convex programming problem), then a local minimization technique can be used to obtained the global optimal solution of the primal problem. Today there are many relatively mature global optimization approaches for concave minimization problems, reverse convex programming problems and D.C. programming problems such as outer approximatation method, branch and bounded method, ect. . Thus, if a programming problem can be converted into an equivalent concave minimization or reverse convex programming problem or D.C. programming problem, then its global minimum or approxiamte global minimum can be obtained by solving the converted structured problems. Chapter 2 is organized as follows. A general convexification and concavification method are presented in Section 2.2 for strictly monotone functions, then a strictly monotone nonlinear programming problem can be converted into an equivalent concave minimization or reverse convex programing problem or D.C. programming problem( generally, it can not be converted into an equivalent convex programming problem). In Section 2.3, a general conveification and concavification method for the objective function in a program-ming problem with certain monotonicity for constraints and nonmonotone objective function are presented. By the proposed transformation methods, a programming problem with monotone constraints and nonmonotone objective function programming problem can be directly converted into an equivalent concave minimization or reverse convex programing problem or D.C. programming problem (generally, it can not be converted into an equivalent convex programming problem). In Section 2.4, by the convexification of some kinds of nonconvex functions, firstly some sufficient coditions that assure a nonconvex function( not necessarily to be monotone) can be converted into a convex function are presented. This kind of functions are said to be hidden convex functions. The relationships among some kinds of convexities are discussed. Then, some sufficient coditions that assure a nonconvex programming problem can be converted into an equivalent convex programming problem are proposed. This kind of programming problems are said to be hidden convex programming problems. Futhermore, some sufficient conditions that assure a quadratic programming problem is a hidden convex programming problem are derived. In particular, sufficient conditions which can be directly verified by the coefficients is proposed for some special quadratic programming problems. Finall...