Multilevel subspace correction for large-scale optimization problems.
详细信息
文摘
In this work we study the application of domain decomposition and multigrid techniques to optimization. We illustrate the resulting algorithms by applying them to optimization problems derived from discretizations of partial differential equations, as well as to purely algebraic optimization problems arising in mathematical finance. For the analysis of the presented algorithms we utilize the subspace correction framework (cf. Xu, 1992).;We discuss the cases of convex non-smooth and smooth non-convex optimization, as well as constrained optimization, and present the convergence analysis for the multiplicative Schwarz algorithms for these problems. For PDE-based optimization problems we also discuss the effect of coarse grid correction and analyze the convergence rate of the corresponding multiplicative and additive Schwarz methods.;We consider the application of the multiplicative subspace correction method to the variational formulation of the elliptic eigenvalue problem and show that, as in the linear case, if the coarse grid correction is used, the convergence rate is independent of both the number of subdomains and the meshsize. We discuss the generalization of this method for simultaneous computation of several eigenfunctions and its applications to the problem of partitioning a graph based on spectral bisection.;In the final chapter we consider the application of the subspace correction methods to some algebraic optimization problems arising in mathematical finance. We restrict our attention to the minimization of the Frobenius distance used in covariance matrix estimation, the factor analysis problem, and the gain-loss optimization problem. Numerical results illustrating the convergence behavior of the subspace correction methods applied to these problems are presented.