Block Preconditioners for KKT Systems in PDE—Governed Optimal Control Problems
Birkhäuser Basel eBooksPublished 1 January 2001
Astrid Battermann, E. W. Sachs
Citations42
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper is concerned with block preconditioners for linear KKT systems that arise in optimization problems governed by partial differential equations in the general case.
Abstract
This paper is concerned with block preconditioners for linear KKT systems that arise in optimization problems governed by partial differential equations. The preconditioners exhibit, like the KKT system, a specific block structure and are composed of preconditioners for submatrices in the general case. Implementation issues are discussed. Numerical results are given for an elliptic boundary control problem from ground water modeling.
Keywords
Computer ScienceMathematicsEngineering
SIAM Journal on Scientific and Statistical ComputingGMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
11,056 Citations1986Youcef Saad, Martin H. Schultz
An iterative method for solving linear systems, which has the property of minimizing at every step the norm of the residual vector over a Krylov subspace.
Cambridge University Press eBooksIterative Solution Methods
2,104 Citations1994Owe Axelsson
This paper presents a meta-analyses of matrix eigenvalues and condition numbers for preconditional matrices using the framework of the Perron-Frobenius theory for nonnegative matrices and some simple iterative methods.
SIAM Journal on Numerical AnalysisSolution of Sparse Indefinite Systems of Linear Equations
1,602 Citations1975Christopher C. Paige, Michael A. Saunders
The method of conjugate gradients for solving systems of linear equations with a symmetric positive definite matrix A is given as a logical development of the Lanczos algorithm for tridiagonalizing...
Texts in applied mathematicsIterative Methods for Solving Linear Systems
1,038 Citations2006Alfio Quarteroni, Riccardo Sacco +1 more
Numerische MathematikQMR: a quasi-minimal residual method for non-Hermitian linear systems
975 Citations1991Roland W. Freund, No�l M. Nachtigal
A novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG is presented and how BCG iterates can be recovered stably from the QMR process is shown.
SIAM Journal on Scientific ComputingA Note on Preconditioning for Indefinite Linear Systems
534 Citations2000Malcolm F. Murphy, Gene H. Golub +1 more
For nonsingular indefinite matrices of saddle-point (or KKT) form, it is shown how preconditioners incorporating an exact Schur complement lead to preconditionsed matrices with exactly two or exactly three distinct eigenvalues.
SIAM Journal on Numerical AnalysisFast Iterative Solution of Stabilised Stokes Systems Part II: Using General Block Preconditioners
398 Citations1994David J. Silvester, Andrew J. Wathen
This paper considers the more general class of block preconditioners, where the partitioning into blocks corresponds to the natural partitions into the velocity and pressure variables, and it is shown that the convergence rate of the iteration depends on the eigenvalue distribution of the discrete Stokes operator.
SIAM Journal on Matrix Analysis and ApplicationsConstraint Preconditioning for Indefinite Linear Systems
328 Citations2000Carsten Keller, Nicholas I. M. Gould +1 more
The problem of finding good preconditioners for the numerical solution of indefinite linear systems is considered and special emphasis is put on preconditionsers that have a 2 × 2 block structure and that incorporate the (1,2 and (2,1) blocks of the original matrix.
SIAM Journal on Matrix Analysis and ApplicationsA Preconditioned Iterative Method for Saddlepoint Problems
318 Citations1992Torgeir Rusten, Ragnar Winther
A preconditioned iterative method for indefinite linear systems corresponding to certain saddlepoint problems is suggested, which is applied to systems derived from discretizations of the Stokes problem and mixed formulations of second-order elliptic problems.
SIAM Journal on Matrix Analysis and ApplicationsHow Fast are Nonsymmetric Matrix Iterations?
308 Citations1992Noël M. Nachtigal, S C Reddy +1 more
It is shown that the convergence of CGN is governed by singular values and that of GMRES and CGS by eigenvalues or pseudo-eigenvalues, and the three methods are found to be fundamentally different.
SIAM Journal on Numerical AnalysisFast Iterative Solution of Stabilised Stokes Systems. Part I: Using Simple Diagonal Preconditioners
226 Citations1993Andrew J. Wathen, David J. Silvester
A conjugate gradient-like method is proposed which is applicable to symmetric indefinite problems, the effects of stabilisation on the algebraic structure of the discrete Stokes operator are described and estimates of the eigenvalue spectrum of this operator are derived on which the convergence rate of the iteration depends.
BIT Numerical MathematicsMinimum residual methods for augmented systems
203 Citations1998Bernd Fischer, Alison Ramage +2 more
It is proved that when the definite and indenfinite preconditioners are related in the obvious way, MINRES and full GMRES give residual vectors with identical Euclidean norm at each iteration, which shows that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed.
SIAM Journal on Matrix Analysis and ApplicationsPreconditioners for Indefinite Systems Arising in Optimization
145 Citations1992Philip E. Gill, Walter Murray +2 more
Methods are discussed for the solution of sparse linear equations $Ky = z$, where K is symmetric and indefinite, and direct and iterative methods are both used.
Optimal Control: Theory, Algorithms, and Applications
114 Citations1998William W. Hager, P. M. Pardalos
A new Krylov-subspace method for symmetric indefinite linear systems
112 Citations1994R.W. Freund, Noël M. Nachtigal
The authors describe a new Krylov-subspace iteration for solving symmetric indefinite linear systems that can be combined with arbitrary symmetric preconditioners and produces iterates defined by a quasi-minimal residual property.
BIT Numerical MathematicsGMRES and the minimal polynomial
111 Citations1996Stephen L. Campbell, Ilse C. F. Ipsen +2 more
A qualitative model for the convergence behaviour of the Generalised Minimal Residual (GMRES) method for solving nonsingular systems of linear equationsAx =b in finite and infinite dimensional spaces and bounds are provided that explain the convergence of GMRES.
SIAM ReviewInertia-Controlling Methods for General Quadratic Programming
98 Citations1991Philip E. Gill, Walter Murray +2 more
An overview of a generic inertia-controlling QP method, including the equations satisfied by the search direction when the reduced Hessian is positive definite, singular and indefinite, is presented.
Applied optimizationFormulation and Analysis of a Sequential Quadratic Programming Method for the Optimal Dirichlet Boundary Control of Navier-Stokes Flow
47 Citations1998Matthias Heinkenschloss
Compatibility is enforced by choosing appropriate function spaces by applying a sequential quadratic programming (SQP) method to the optimization problem and compared with other approaches.
Birkhäuser Basel eBooksBlock Preconditioners for KKT Systems in PDE—Governed Optimal Control Problems
42 Citations2001Astrid Battermann, E. W. Sachs
This paper is concerned with block preconditioners for linear KKT systems that arise in optimization problems governed by partial differential equations in the general case.
How Descriptive are GMRES Convergence Bounds?
41 Citations2022Mark Embree
This paper analyzes and compares eigenvalues with the eigenvector condition number, the field of values, and pseudospectra as the basis for convergence bounds for minimum residual Krylov subspace methods applied to non-normal coefficient matrices.
SIAM Journal on Matrix Analysis and ApplicationsPreconditioning Reduced Matrices
38 Citations1996Stephen G. Nash, Ariela Sofer
Preconditioning strategies for linear systems with positive-definite matrices of the form $Z^{T} GZ$ are studied, which are suitable within algorithms for constrained optimization problems in the calculus of variations.
Some Linear Algebra Issues in Large-Scale Optimization
4 Citations1993Margaret H. Wright
This work discusses selected features of large-scale problems and of the associated forms of inexactness of linear systems for unconstrained, linearly constrained and nonlinearly constrained optimization.
Approximation of the Newton Step by a Defect Correction Process
4 Citations1999Eyal Arian, A. Batterman +1 more
An optimal control problem governed by a partial differential equation is considered and the Newton step for this system can be computed by solving a coupled system of equations by means of a modifying operator introduced into the system.
SIAM Journal on OptimizationEstimates for the Nash--Sofer Preconditioner for the Reduced Hessian for Some Elliptic Variational Inequalities
2 Citations1999Tony Doungho Choi, C. T. Kelley
A class of examples is presented to show how the quality of the Nash--Sofer preconditioner can be directly estimated and one consequence is that if the Hessian is the five-point discretization of a certain type of strongly elliptic operator with homogeneous Dirichlet boundary conditions on an $n \times n$ mesh, then the condition number of the reduced Hessian can be lowered.
Birkhäuser Basel eBooksIncomplete Indefinite Decompositions as Multigrid Smoothers for KKT Systems
2 Citations1999Volker Schulz
New incomplete decompositions of Bunch-Parlett type for linear KKT systems are developed as natural generalizations of incomplete LU decomposition, in order to be applied as smoothers within a multigrid algorithm.
VTechWorks (Virginia Tech)Preconditioning of Karush--Kuhn--Tucker Systems arising in Optimal Control Problems
1 Citations1996Astrid Battermann