Subspace Correction Methods for Convex Optimization Problems

Xue-Cheng Tai
Mathematics Institue, University of Bergen, Norway

Jinchao Xu
Department of Mathematics, Pennsylvania State University, USA

Abstract

Domain decomposition and multigrid methodshave been intensively studied for linear partial differential equations. Recent research reveals that domain decomposition and multigrid methods can be analysed using a same framework. The present work uses this framework to analyse the convergence of two algorithms for convex optimization problems. Our emphasis is on nonlinear problems instead of linear problems. The algorithms reduce to the standard additive and multiplicative Schwarz methods when used for linear partial differential equations.

Researches for domain decomposition and multigrid methods have been mostly concentrating on linear elliptic and parabolic partial differential equations. Extension to more difficult problems have been considered by some recent works.In this work,a general nonlinear convex minimization problems is considered. The proposed algorithms can be used for nonlinear partial differential equations, optimal control problems related to partial differential equations and eigenvalue problems. The space decomposition can be a domain decomposition method, a multigrid method or some other decomposition techniques.

Domain decomposition methods and multigrid methods have been studied for nonlinear partial differential equations by some earlier works. In comparison with the existing works, our approach has several features. For example, the proposed algorithms canbe used for certain degenerated or singular nonlinear diffusion problems, i.e., the nonlinear diffusion coefflcient can be zero or infinity and our approach do not need extra assumption on the smoothness of the solutions. The methods work for natural domain decomposition and multigrid meshes. Moreover, only small size nonlinear problems need to be solved on the decomposed subspaces. We also emphasis that our approach is valid for general space decomposition techniques. So the applications is not restricted to domain decomposition and multigrid methods. Other space decomposition techniques can also be considered. The two algorithms given in this work were first proposed elsewhere, where the qualitative convergence of the algorithms was proved, but the uniform rate of convergence was not given there.