Filled Function Metheods In Nonlinear Global Optimization

Optimization is a subject that is widely applied. It discusses and fixes on the optimal decision of certain problems, constructs calculation methods of optimal solutions and studies on its theoretical nature and the representation of its practical calculation. In 1970s, as bibliography [1, 2] occurs, various Global optimization methods emerge in endlessly that can be classified into two categories: deterministic and probabilistic. Filled function method is a determinate algorithm that pops up in the 1990s.Filled function method was originally put forward by Renpu Ge. as an effective algorithm of finding global minimizer of a multi-modal function ( see [4, 5, 6, 7, 8]) around 1990. At that moment, the theory is raised mainly to cope with unconstrained optimization problems.The rudimental notion of filled function method is: when a local minimizer is reached, it is hoped that " escaping " this local minimizer is possible. Furthermore, keep searching, and a better local minimizer is reached. By constructing an auxiliary function, a local minimizer is shifted into a local maximizer. We make the point perturbed (or deterministic perturbed) stochas-tically, and then, take this perturbed point as the initial point to search, and try to find the auxiliary function's local minimizer which is a better local minimizer of the objective function f(x) , or at least as well as the original one. Suppose the objective function /(x)'s local minimizers in the feasible region is finite in number, applying this method and continuing to search, we can always get to the global minimier.Filled function method is a two-phase iterative: the minimizer phase and the filling phase. In the first phase, we can use classic minimizer method, such as quasi-Newton method, the method of steepest descent, etc. to search for a local minimizer x\ in objective function. During the second phase, we take the present minimizer x* as the basic to define a filled function, and using it to find x\ $" xi> and so f(x2) — f(xD- Then we take /(x^) as the starting point and repeat the first phase. This occurs again and again until the best local minimizer could not be found.The filled function method fully grasps the present local information, for it only applies the mature loacal minimizer method, it is greatly popular with the theoretical and practical operators.As early as in 1990, Renpu Ge. put forward a filled function (2.1.1) with two parameters, in the article [4]. By some checkouts of the standard test function, the algorithm used filled function in (2.1.1) is available to the optimization of one variable, multi-modal objective function and higher dimension. On the contrary, the filled function (2.1.1) still has some defects:(1) Because of the exponential termexp (----------------).If p is too small or ||x — x*|| is too big,exp (r - r*ll22)is approaching to zero, so function (2.1.1) and its gradient hardly will have any change. In this case the calculating effect will be bad. And so p could not be too small. However, if p is relatively big, it is possible that conditions of filled function could not be satisfied, as a result, the two parameters r and p are hard to choose and adjust.(2) The filled function given in bibliography [4] is only applicable to f(x) in X only has finite local minimizer points, hence as to the problem of global minimizer with infinite local minimizers, the method could not be used to come to the global minimizer point.(3) The filled function in (2.1.1) could not ensure that a local minimizer or a stationary point definitely exists in a lower basin than B* , it can only ensure that there is a point x , so that the filled function has a minimizer on the line through x{ and x . As a result, using the filled function in order to get the point in the lower basin could not be obtained by direct getting the local minimizer of this function, and also because of the dimension of the line is small, it is very difficult to find the point in the lower basin.To these defects, Renpu Ge. and Qin renovates this filled function in [8]. Zheng xu and Xian liu also make some progress to the filled function above (see bibliography [8, 9, 10, 40] etc.), but these improvements are only made toward the defect (1), not toward the following two defects. Later on, Liansheng Zhang, Rui Li and NG, C.K. work on the definition of the filled function, make a big improvement, and bring out some filled functions ingood quality (some filled functions ensure the existence of local minimizer in the lower basin, and some functions have already get rid of the defects above) (see bibliography [13, 41]). Liansheng Zhang, Rui Li and Wenxing Zhu and other people apply the renovated filled function into solving nonlinear integer programming, establish an approximate algorithm directly that solves the nonlinear integer programming, and provide an approach in solving this problem (see bibliography [13, 22]etc). So it brings along the study of using filled function method to solve nonlinear integer programming.Having a thorough view of the development of the filled function methods, the crucial point influencing the numerical experimental outcome is the choice making of the filled function, namely the perturbing of the original local minimizer. As the perturbation is aimless, it is blind, and it has numerous projects, every one of which may lead to different results, however, these projects could not carry out in the practical calculation. If a;is a one dimension variable, there are two projects to perturb the local minimizer;and if x is an n dimension variable, there are infinite projects to perturb the local minimizer. Besides, the local optimal of auxiliary function gained by using the perturbed point may be the original local optimal point ultimately. Or after some calculations, it will return to the same optimal local point, so as to form a circulation. This means that we could not define the point that is gained by auxiliary function is the global optimal point.The matter is that these approaches for the most part have not take the specific structure of the problem into consideration. They are generally valid, but there always some cases that make these approaches invalid. In fact, asit has been proved that the problem of global optimizer generally is NP-hard. Therefore, it is a doable approach to develop the filled function method from the specific problems, concentrating on and making clear of their structures and finding out the relation between the filled function and the problem's structure.This paper systematically summarizes the development, theory and the applied studying status of the filled function methods and makes some analysis and comments. It is divided into three chapters. The first chapter is generally about the problem of global optimizer and the notions concerning it, and introduces the background and the basic thoughts of the filled function method. The second chapter has a detailed introduction and analysis on the development of filled function methods and the difficulties it meets in continuous optimizer and the nonlinear integer programming which are the two most active fields. The third chapter makes a summarizing analysis and haves a future prospect of the development of the filled function method.