Preconditioning of Karush--Kuhn--Tucker Systems arising in Optimal Control Problems

Abstract

This work is concerned with the construction of preconditioners for indefinite linear systems. The systems under investigation arise in the numerical solution of quadratic programming problems, for example in the form of Karush--Kuhn--Tucker (KKT) optimality conditions or in interior--point methods. Therefore, the system matrix is referred to as a KKT matrix. It is not the purpose of this thesis to investigate systems arising from general quadratic programming problems, but to study systems arising in linear quadratic control problems governed by partial differential equations. The KKT matrix is symmetric, nonsingular, and indefinite. For the solution of the linear systems generalizations of the conjugate gradient method, MINRES and SYMMLQ, are used. The performance of these iterative solution methods depends on the eigenvalue distribution of the matrix and of the cost of the multiplication of the system matrix with a vector. To increase the performance of these methods, one tries to transform the system to favorably change its eigenvalue distribution. This is called preconditioning and the nonsingular transformation matrices are called preconditioners. Since the overall performance of the iterative methods also depends on the cost of matrix--vector multiplications, the preconditioner has to be constructed so that it can be applied efficiently. The preconditioners designed in this thesis are positive definite and they maintain the symmetry of the system. For the construction of the preconditioners we strongly exploit the structure of the underlying system. The preconditioners are composed of preconditioners for the submatrices in the KKT system. Therefore, known efficient preconditioners can be readily adapted to this context. The derivation of the preconditioners is motivated by the properties of the KKT matrices arising in optimal control problems. An analysis of the preconditioners is given and various cases which are important for interior point methods are treated separately. The preconditioners are tested on a typical problem, a Neumann boundary control for an elliptic equation. In many important situations the preconditioners substantially reduce the number of iterations needed by the solvers. In some cases, it can even be shown that the number of iterations for the preconditioned system is independent of the refinement of the discretization of the partial differential equation.