A vector quantization multistart method for global optimization

The multistart method is one of the most promising stochastic global optimization techniques. It finds the global minimum of a nonlinear multimodal function by enumerating all the local minima with function value less than a threshold. In this dissertation the vector quantization multistart (VQ-multistart) method is introduced and developed. The method of vector quantization divides the domain of interest into optimal Voronoi cells by defining a lattice with the smallest possible quantization error. The Voronoi cells are constructed around the lattice points and all data points that lie in a Voronoi cell are quantized to the corresponding lattice point. Vector quantization is used to identify clusters by examining the density of the reduced sample points, a fraction of the sample points with the smallest function value. Local minima are found by starting a local minimization procedure from one point in every identified cluster. The local minimum with the smallest function value is an estimate of the global minimum.; Convergence properties of the VQ-multistart method are analyzed and its superiority is demonstrated by applying it to several standard test problems. The results of the computational experiment show that, compared to the algorithms proposed earlier, the VQ-multistart method found more local minima, or the same number of local minima with fewer executions of the local minimization procedure. This method is also extended to nonlinear multimodal constrained optimization problems. In addition a framework which is based on the multistart method is developed for finding the global optimum of nonlinear integer and mixed integer programming problems.; The VQ-multistart method results in substantial savings in both the incore memory requirements and the computation time as compared to existing algorithms for the multistart method, which implies that larger problems can now be solved by this method. For instance, it is shown that for a problem with 7 variables, the amount of storage required is about {dollar}1over11{dollar}th that of a multistart algorithm that uses hypercubes for clustering. This method also provides valuable insight about the structure of the nonlinear multimodal problem under consideration.