Refining the bounds from Rusten and Winther with insights on the interaction between the blocks in saddle point systems
Efficiently solving saddle point systems like KKT ones using iterative solvers is a crucial task for many algorithms in constrained optimization. Such systems can be very ill-conditioned, in particular when the (1,1) block has few very small eigenvalues (see Rusten and Winther, 1992). However, it is commonly observed that despite these small eigenvalues, some sort of interaction between this (1,1) block and the (1,2) block actually occurs, that may influence strongly the convergence of Krylov subspace methods like MINRES. In this talk, we highlight some aspects of this interaction and give deeper insights on how and in which circumstances the bad conditioning contained in these few very small eigenvalues of the (1,1) block effectively spoils the convergence of MINRES. Our study is based on theoretical arguments, deriving a tight lower bound on the positive eigenvalues of saddle point matrices of the KKT form, and supported by numerical illustrations.