On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization​

"In this thesis, we present research on the topic of mathematical properties of methods for solving symmetric systems of linear equations that arise in various optimization problem formulations and in methods for solving such optimization problems.

In the first and the third paper (Paper A and Paper C), we consider the connection between the method of conjugate gradients and quasi-Newton methods on quadratic optimization problems or equivalently on a symmetric system of linear equations with a positive definite matrix. We state conditions on the quasi-Newton matrix and the update matrix such that the search direction generated by the corresponding quasi-Newton method is parallel to the search direction generated by the method of conjugate gradients. 

In paper A,

we derive such conditions on the update matrix based on a sufficient condition to obtain mutually conjugate search directions. These conditions are shown to be equivalent to the one-parameter Broyden family of update schemes. Further, we derive a one-to-one correspondence between the Broyden parameter and the scaling between the search directions from the method of conjugate gradients and a quasi-Newton method employing some well-defined update scheme in the one-parameter Broyden family respectively. 

In paper C, we give necessary and sufficient conditions on the quasi-Newton matrix

and on the update matrix such that equivalence with the method of conjugate gradients hold for the corresponding quasi-Newton method. We show that the set of quasi-Newton schemes admitted by these necessary and sufficient conditions is strictly larger than the one-parameter Broyden family. In addition, we show that this set of quasi-Newton schemes includes an infinite number of symmetric rank-one update schemes. 

In the second paper (Paper B), we utilize an unnormalized Krylov subspace framework for solving symmetric systems of linear equations. These systems may be incompatible and the matrix may be indefinite/singular. Such systems of symmetric linear equations arise in a number of problem formulations and methods for solving various constrained optimization problems. In the case of an incompatible symmetric system of linear equations we give a certificate of incompatibility based on a projection on the null space of the symmetric matrix and characterize a minimum-residual solution. Further we derive aminimum-residual method, give explicit recursions for the minimum-residual iterates and characterize a minimum-residual solution of minimum Euclidean norm in the case when the symmetric system of linear equations is incompatible. The unnormalized Krylov subspace framework is based on a symmetric unnormalized Lanczos process and in each step a triple of quantities, one of which being the unnormalized Lanczos vector,  is updated by three-term recurrence relations."