Some Studies Of The Grid-based Methods For Optimization Problems

Now, many convergence results of the derivative-free algorithms for the optimization problems have been established. Grid-based method is the main work in the paper. It is one of the direct search methods. An attractive feature of this algorithm is that it is derivative-free, i.e., no derivative of the objective function need to be computed. The grid-based methods seek a mininizer of the objective function by examining it on a sequence of successively grids. Each grid is defined by an element of class consisting of positive bases, thus selecting proper positive bases is the first considered factor for the algorithms. Since it belongs to the class of direct search methods, it is suitable for the large-scale problems, as well as applications where the derivative of the objective function are not available or are costly to compute.This paper mainly makes a further discussion about the grid-based methods for linear equality constrained optimization problems and nonlinear complementarity problems. The main contents of this thesis can be summarized as follows:In Chapter 1 and Chapter 2, we describe some information of the optimization theory and algorithm in detail, such as the structure and the rate of optimization algorithm,the cardinal principle, the traditional representations.In Chapter 3, we consider a direct search method for a class of linear equality constrained optimization problems, which makes use of grids called grid-based methods, and give a proof of its convergence. During the research the projected gradient methods are adopted, so every element of the class consisting of positive bases is a positive bases of R~n~m. Thus the dimension of the variables need to be computed in the algorithms is decreased and the implementation of the algorithms is simplified to some extent.In Chapter 4, we describe the grid-based methods for the nonlinear complementarity problems, we consider the methods under two different structures according to the condition degree, analyze the convergence respectively, and state the strict proof. The first result implies that at least one of the limit point of iterates generated by this method is the stationary point, and the second one means that every limit point of iterates generated is the stationary point.