Title page for ETD etd-12164379662151


Type of Document Master's Thesis
Author Battermann, Astrid
URN etd-12164379662151
Title Preconditioning of Karush--Kuhn--Tucker Systems arising in Optimal Control Problems
Degree Master of Science
Department Mathematics
Advisory Committee
Advisor Name Title
Beattie, Christopher A.
Burns, John A.
Heinkenschloss, Matthias Committee Chair
Keywords
  • preconditioning
  • optimal control
  • quadratic programming
  • karush-kuhn-tucker systems
  • indefinite systems
Date of Defense 1996-06-14
Availability unrestricted
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.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  etd.pdf 1.57 Mb 00:07:16 00:03:44 00:03:16 00:01:38 00:00:08

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.