Some Deterministic Methods In Global Optimization

The global optimization problem can be stated as follows: Given a nonempty, closed set D R" and a continuous functionf: A-R, where A R" is a suitable set containing D, find at least one point x * D satisfy ingf(x*) f(x) for all xi.e.There are many applications of the nonlinear global optimization in the field of science and technology, optimal design of engineering," economic managenent and so on. In this dissertation, we consider mainly some deterministic methods for solving global optimization problems.In Chapter 1, a brief introduction is given to the main classes of global optimization problems that can be treated by deterministic methods. Some of these methods are successively to approximate global solution; most prominent examples are the outer approximation, the branch-and-bound method, the interval method and the integral method. Others are developed from the local minimum to the global minimum, such as the tunneling algorithm and the filled function method.In Chapter 2, we modify Zheng's integral method and propose several algorithms to find the global solution of (P). They are implementable algorithms and have the merit, which only calculatethe values of the objective functions. The following is the organization of Chapter 2. In Section 2.2, we present an algorithm for solving the problem (P) by discrete level set-mean value. The main idea of this algorithm is that, at each iteration, we take more points on some regions in which the values of the function f(x) is smaller than those in other regions, and take fewer points on the regions in which the values of the function f(x) is bigger than those in other regions. In this way the efficiency of computation can be improved. Moreover, the termination rule for discrete level set-mean value is given and the convergence of the algorithm is proved. In Section 2.3, we propose a modified integral-level set algorithm for solving the global optimization. In each iterative process, we construct a new function, which has the same global optimum as that of the primitive function. The algorithm is implemented by applying the deterministic uniform distribution numerical integral in number theory to approach the level value and the level set. Because of not changing the search domain, we can avoide using Zheng's Monte-Carlo implemtable algorithm, which is maybe to lose of the global optimum, to approach the level set. Furthmore, we gain the optimality conditions and prove the convergence of the algorithm. Section 2.4 discusses how to solve the constrained global optimization. Several numerical examples are presented in Section 2.5, the priliminary numerical results show that our algorithms are effective.In Chapter 3, we construct a class of auxiliary functions which correspond to a class of filled functions, and we propose some algorithms to find the global minimum for the unconstrained2000optimization and the nonlinear integer programming. The organization of Chapter 3 is as follows. Section 3.2 discusses a filled function with only one parameter. In Section 3.3 we show how using another filled function to construct an algorithm to solve the global unconstrained optimization. The computational results show that this algorithm is effective. There is no any algorithm for integer programming with quadratic constraints and linear objective function. Therefore, we assume that the domain of function is bounded when nonlinear integer programming is concerned. Even for this case, there is also lack of algorithms to solve it. We proposed an approach for finding the global minimum of nonlinear integer programming. Section 3.4 is devoted to study a filled function p(x1,x1',p)with only one parameter..In Section 3.5,we present theother filled function p(x/,x*1, p,//) in order to solve the nonlinearinteger programming. The numerical test results show that thealgorithm is also effective.