Some Preconditioning Techniques for Saddle Point Problems
Saddle point problems arise frequently in many applications in science and engineering, including constrained optimization, mixed finite element formulations of partial differential equations, circuit analysis, and so forth. Indeed the formulation of most
- PDF / 251,652 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 198 Views
Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322, USA [email protected] Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK [email protected]
1 Introduction Saddle point problems arise frequently in many applications in science and engineering, including constrained optimization, mixed finite element formulations of partial differential equations, circuit analysis, and so forth. Indeed the formulation of most problems with constraints gives rise to saddle point systems. This paper provides a concise overview of iterative approaches for the solution of such systems which are of particular importance in the context of large scale computation. In particular we describe some of the most useful preconditioning techniques for Krylov subspace solvers applied to saddle point problems, including block and constraint preconditioners. Many applied problems can be stated in the form of constrained minimization problems. Frequently, such problems are infinite-dimensional and highly nonlinear. Discretization results in finite-dimensional problems of large size. These problems are usually replaced by a sequence of quadratic minimization problems subject to linear equality constraints: min J(u) = 12 uT Au − f T u subject to Bu = g .
(1) (2)
Here A ∈ Rn×n is symmetric positive semidefinite, and B ∈ Rm×n , with m < n; f ∈ Rn and g ∈ Rm are given vectors. The first-order optimality conditions are given by the linear system u f A BT = . (3) g B O p ∗∗
The work of the first author was supported in part by the National Science Foundation grant DMS-0511336.
196
M. Benzi and A.J. Wathen
In (3), p ∈ Rm is a vector of Lagrange multipliers . Linear systems of the form (3) are known as saddle point problems, since any solution (u, p) of (3) is a saddle point of the Lagrangian function L(u, p) = 12 uT Au − f T u + (Bu − g)T p . Large linear systems in saddle point form also arise from inherently discrete physical models, such as mechanical structures [41] and RCL circuits [17]. More generally, we consider linear systems of the form A BT u f Ax = = = b, (4) B −C p g with A and B as before and C ∈ Rm×m symmetric and positive semidefinite. Systems of the form (4) with a nonzero (2,2) block arise, for instance, in the context of interior point methods for constrained optimization [32]. Other examples are provided by mixed finite elements for incompressible flow problems, when some form of pressure stabilization is included in the discretization [13], and by the modeling of slightly compressible materials in linear elasticity theory [7]. Typically, A is large and sparse and (4) must be solved iteratively, usually by means of Krylov subspace algorithms [42]. Unfortunately, Krylov methods tend to converge very slowly when applied to saddle point systems, and good preconditioners are needed to achieve rapid convergence. In the last few years, much work has been devoted to developing effective preconditioners for saddle point systems. The goa
Data Loading...
