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

Show simple item record

dc.contributor.advisor Burns, John A. en_US
dc.contributor.advisor Beattie, Christopher en_US
dc.contributor.advisor Heinkenschloss, Matthias en_US
dc.contributor.author Battermann, Astrid en_US
dc.date.accessioned 2011-08-05T14:49:48Z
dc.date.available 2011-08-05T14:49:48Z
dc.date.issued 1996-06-14 en_US
dc.identifier.other etd-12164379662151 en_US
dc.identifier.uri http://hdl.handle.net/10919/9579
dc.description.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. en_US
dc.format.medium ETD en_US
dc.publisher Virginia Tech en_US
dc.relation.haspart etd.pdf en_US
dc.rights The authors of the theses and dissertations are the copyright owners. Virginia Tech's Digital Library and Archives has their permission to store and provide access to these works. en_US
dc.source.uri http://scholar.lib.vt.edu/theses/available/etd-12164379662151 en_US
dc.subject preconditioning en_US
dc.subject optimal control en_US
dc.subject quadratic programming en_US
dc.subject karush-kuhn-tucker systems en_US
dc.subject indefinite systems en_US
dc.title Preconditioning of Karush--Kuhn--Tucker Systems arising in Optimal Control Problems en_US
dc.type Thesis en_US
dc.contributor.department Mathematics en_US
dc.description.degree MS en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search VTechWorks

Advanced Search


My Account