Study On The Parallel Algorithms For Optimization Problems

This thesis is mainly on the study of parallel algorithm on unconstrained and sim-ple constrained optimization. Researches are carried through concerning the existing Parallel Variable Distribution algorithm (PVD) and Parallel Variable Transformation algorithm (PVT). On the ground of the former two parallel algorithms, the thesis demonstrates three improving algorithms in chapter two, three and four:PVD algo-rithm with linear inseparable constraints, asynchronous PVT algorithm with uncon-straint and partial asynchronous PVT algorithm on the large-scale linear constrained optimization. In chapter five and six, parallel algorithms on unconstrained pattern search method and on pattern search method with bound constraint are researched owing to pattern search method's effectiveness in dealing with actual problems, and its potential parallelism.In chapter two, two type-PVD algorithms of inseparable linear constraint optimiza-tion are presented. We make reduced gradient as PVD direction in parallel computers to lessen computation. In order to maintain convergence of the new algorithm, we get the active constraint set by computing of coordinate rotation at every step, through which we have the expanding reduced gradient, a feasible descending direction. Then we take it as the PVD direction, and work out the PVD algorithm on general linear constraint optimization of inequation. These two algorithms are easier than projected gradient residual function proposed by Solodov, and we can have the whole convergence of the original problem.We discuss M. Fukushima's PVT algorithm frame about unconstrained optimiza-tion in chapter three. PVT algorithm is the extension of PVD algorithm, which can also be viewed as the special case of PVT algorithm. PVT algorithm doesn't need to divide the variable into main variable and secondary variable. It just selects suit- able transforming matrix and transforms the variable space of the problem into multi variable subspaces of smaller dimension. Consequently, original problem is parted into multi sub-problems, which are processed parallel computation. But only after the processor finishes processing all the sub-problems respectively, is it able to carry out synchronously and get to next iteration point. This algorithm wastes computing re-sources extensively, and can not achieve computing and message-sending at the same time. So we study an asynchronous algorithm which means that as long as one of the sub-problems satisfies the condition of convergence, the whole computation will stop. This asynchronous algorithm saves synchronous time. From numerical experiments, we can see that the reformed algorithm improves the efficiency of parallel computation greatly.Chapter four is devoted to a new asynchronous PVT algorithm on large-scale linear constrained optimization based on chapter three. The method adopts Fischer's function, and changes the linear constrained problem into the equivalent unconstrained optimization. We obtain the asynchronous PVT algorithm on the linear constrained problem. The thesis proves the whole convergence of the algorithm. And we get linear convergence rate independent of the number of processors pointing to the specialized problem. Compared with the original synchronous PVT, whose linear convergence rate is inversely proportional to the number of processors, this new algorithms shows the advantage of asynchronous algorithm.Chapters five and six are concerned with pattern search method which is one type of the direct search methods. Pattern search method is meant to solve the problem in which accurate or approximate gradient of function is difficult to obtain. In chapter five, for unconstrained optimization, we apply pattern search method on distributed cluster system with asynchronous architecture, and work out its parallel algorithm. The algorithm mainly achieves parallelism of search directions, but not simple parallelism of function value. Through the simulation of numerical experiment, the algorithm is proved to be an effective parallel pattern search method on the cluster system with asynchronous architecture.In addition, we compare the distinguishing features of bound constraint pattern search method with those of unconstraint pattern search method, and present the differences of mesh, and different choices of search direction. Then the parallel method mentioned in chapter five is expanded. Besides, the feasibility of this parallel method in chapter six is proved and convergence is illustrated in the thesis.The last part is concerned with some topics that need further studies in the light of some new methods of the existing optimization problems including the unsolved ones in this thesis.