Author

Gul Karaduman

Graduation Semester and Year

2017

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Management

Department

Management

First Advisor

Ren-Cang Li

Abstract

In this thesis, we work on iterative solutions of large linear systems of saddle point problems of the form ? ? ? A B1 T B2 0 ? ? ? ? ? ? x y ? ? ? = ? ? ? f 0 ? ? ? , where A ? R n×n , B1, B2 ? R m×n , f ? R n , and n = m. Many applications in computational sciences and engineering give rise to saddle point problems such as finite element approximations to Stokes problems, image reconstruction, tomography, genetics, statistics and model order reduction for dynamical systems. Such problems are typically large and sparse. We develop new techniques to solve the saddle point problems depending on the rank of B2. First, we deal with the case when B2 has full row rank, i.e., rank(B2) = m. The key idea is to construct a projection matrix and transform the original problem to a least squares problem then solve the least squares problem by using one of the iterative methods such as LSMR. In most applications B2 has full rank, but not always. Next, we turn to the saddle point systems with the rank-deficient matrix B2. Similarly we construct a new projection matrix by using only maximal linearly independent rows of B2. By using this projection matrix, the original problem can still be transformed into a least squares problem. Again, the new system can be solved by using one of the iterative techniques for least squares problems. Numerical experiments show that the new iterative solution techniques work very well for large sparse saddle point systems with both full rank and rank-deficient matrix B2.

Keywords

Saddle point problems, KKT, Iterative

Disciplines

Business | Business Administration, Management, and Operations

License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Comments

Degree granted by The University of Texas at Arlington

28902-2.zip (1981 kB)

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.