Some Research Results On Space Decomposition Methods In Optimization

This dissertation mainly studies a class of space-decomposition algorithms for nonlinear programming problems, including smooth and nonsmooth space-decomposition algorithms suitable to parallelizing and nonsmooth space-decomposition algorithms suitable to serializing. The convergence theorems on convergence and convergence rate for various algorithms are demon-strated,and numerical experiments for one class of space-decomposition algorithms proposed in this dissertation are reported.The main results obtained in this dissertation are summarized as follows:1. In Chapter 2, the space-decomposition principle and the concept of algorithm mappings are introduced based on the present research results, leading to a unifying framework of space-decomposition algorithms in which an algorithm is regarded as a set-valued mapping. Different specific set-valued mappings produce various space-decomposition algorithms suitable to serializing, asynchronous parallelizing or synchronous parallelizing. A general convergence theory is estalished based on set-valued analysis, namely the main convergence theorem is demonstrated based on the notion of closed set-valued mappings. The general theory not only unifies the existing convergence results but also provides several new results. Several specific space-decomposition algorithms, including parallel gradient distribution method (PGD), parallel variable distribution method (PVD), piecewise Jacobi method, parallel variable transformation method (PVT), and UV-decomposition method, are derived from the unifying framework.2. In Chapter 3, some nonmonotone PVT algorithms are constructed and their convergence theorems are demonstrated. A second-order PVT algorithm for solving nonconvex unconstrained optimization problems, based on negative curvature directions and quadratic curve searches, is proposed, and its convergence theorem is proven. Numerical experiments of the second-order PVT algorithm are reported to show the efficiency of the algorithm.3. Another contribution of this dissertation lies in the constructing of nonsmooth space-decomposition algorithms and their convergence theorems. In Chapter 4, an unconstrained PVT-MYR algorithm, based on Moreau-Yosida regularization is given and its convergence theorem is demonstrated. A nonsmooth PGD algorithm dealing with block structure constraints is presented and its convergence is established. An inexact PVD algorithm for non-separable constrained nonsmooth problems is proposed and its convergence theorem is proved. A PVT algorithm, adopting subgradient projection technique, for solving non-smoothly constrained optimization problems, and its convergence results are presented aswell.4. Because of the instrinsic features of them, second-order expansions of noUnsmooth functions are not easily established and fast algorithms are not easy to obtain. In Chapter 5, based on the UV-composition theory of convex functions, second-order expansions are obtained for a class of D. C. functions, with the help of U-Lagrangians. Accordingly, a space-decomposition algorithm, namely UV-decomposition algorithm, for solving unconstrained and constrained D. C. programming problems, is presented, and its superlinear convergence is demonstrated.