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)
Filename		Size	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