Several Grid-based Algorithms For Optimization Problems

This thesis studies two classes of grid-based algorithms, the Coope-Priceframework based direct search algorithms for nding a local solution of an uncon-strained optimization problem, and the DIRECT (DIviding RECTangle) algorithmfor nding a global solution of a bound constrained optimization problem.In chapter 2, we propose a new strategy for updating the grid size based onthe mixed non-monotone decrease condition in the Coope-Price framework. Thenwe propose a direct search algorithm called the Mix-DSCG algorithm, which canbe regarded as an improvement of the original DSCG algorithm. The Mix-DSCGalgorithm possesses the following advantages compared with the DSCG algorithm.First, without the requirement that the limitation of the grid size is zero, theglobal convergence of the algorithm is achieved. Second, the Mix-DSCG algorithmis more reliable than the original DSCG algorithm.In chapter 3, we choose the minimal positive basis to build the Coope-Pricedirect search framework. By the use of the function value information gatheredduring the direct search process, we get estimation to the simplex gradient of theobjective function. We then form a derivative-free conjugate gradient directionand propose a direct search algorithm called the MDSCG algorithm. The globalconvergence of the MDSCG algorithm is proved under mild conditions. Our exten-sive numerical results show that the MDSCG algorithm performs better than someexisting direct search algorithms, such as the DSCG algorithm and the popularNelder-Mead simplex method.In chapter 4, we introduce the idea of the multigrid method to the DIRECTalgorithm and then propose a multigrid-based global optimization (MGGO) algo-rithm. So far, there seems no related research. The proposed MGGO algorithmmay be the rst algorithm that adopts the idea of the multigrid method to solve theglobal optimization problems. The global convergence of the proposed algorithmis proved under the condition that the objective function is Lipschitz continuous.Our numerical results show that the MGGO algorithm is competitive deterministicglobal optimization solver. Numerical results also show that the MGGO algorithmis sensible to algorithm parameters, which is similar to the geometric multigrid(GMG) method for linear systems.In chapter 5, we analyze the convergence of the multigrid methods with resid-ual scaling technique, where the scaling factor is a positive constant. The multigrid method is treated as a perturbed two-grid method, and then we obtain an inequal-ity which measures the relationship between the convergence factor of the multigridmethod and the convergence factor of the two-grid method. The inequality shows/(1 + ) is an upper bound for the convergence factor of the multigrid W-cyclewith residual scaling techniques, where 0 < 0.5 is the upper bound for theconvergence factor of the two-grid method. This upper bound is independent ofthe level. We prove that /(1+ ) is always an upper bound whatever the resid-ual is scaled at all levels or at some levels. Furthermore, it is proved that when0.5< 1, we can increase the cycle index such that there is always an up-per bound for the convergence factor of the multigrid method with residual scalingtechniques. This upper bound is also independent of the level and is always smallerthan /(1+). Finally, we do some numerical experiments. The results show thatthe scaling technique accelerates the convergence of the multigrid. Numerical re-sults also show that the smaller the convergence factor of the two-grid method is,the smaller the convergence factor of the multigrid method is.This dissertation is supported by the National Natural Science Foundation ofChina (10971058, 11071087).This dissertation is typeset by software 2.