Research On Mesh Adaptive Direct Search Algorithm

In practical applications,some optimization problems with partial derivative information or derivative-free information,these optimization problems are called derivative free optimization problems,such as the existence of the range problem of interference or the "black box" problem.The mesh adaptive direct search algorithm is a derivative-free optimization algorithm.Therefore,the algorithm is of great practical significance for solving the derivative-free optimization problem.For solving these problems,the common algorithms contain the generalized pattern search algorithm,the mesh adaptive direct search algorithm,the generation set algorithm and the trust region algorithm.In order to solve some problems whose objective function and constraint function are nonsmooth.In this paper,two modified mesh adaptive direct search algorithms are proposed.The convergence of the algorithm is proved strictly.The details is as follows:First,the orthogonal triangular decomposition is applied to the presented algorithm.In search step,using the Taylor series expansion,rank-one update and linear regression,the quadratic model of the function is built by means of a second directional derivative-based Hessian update.The model of the constraints is linear.By solving the subprogram of the problem,it can obtain the local solution.The poll step searched in the neighbor of the trial points.Based on the traditional mesh adaptive direct search algorithm framework,the modified mesh adaptive direct search with second directional derivative-based Hessian update is presented.The modified algorithm outperforms the original algorithm in terms of iteration times on some test problems.Second,based on the study of augmented Lagrange multiplier method and the mesh adaptive direct search algorithm,we proposed a modified mesh adaptive direct search algorithm based on augmented Lagrange multiplier method.In the search step,the algorithm constructs the quadratic model of the function and the linear model of the constraint function.Considering the extensiveness of the augmented Lagrange algorithm to solve the problem,then we combines the augmented Lagrange multiplier method to solve the subproblem.In the poll step,we will explore the direction set the number of elements from 2n reduced to n +1 according to a certain strategy,and proves the convergence of the new algorithm in theory.By analyzing the test function of different dimensions,the algorithm has some advantages over the mesh adaptive direct search algorithm in terms of iteration times,iteration time and convergence rate.