TY - JOUR
T1 - Refining the lower bound on the positive eigenvalues of saddle point matrices with insights on the interactions between the blocks
AU - Ruiz, Daniel
AU - Sartenaer, Annick
AU - Tannier, Charlotte
PY - 2018/1
Y1 - 2018/1
N2 - Efficiently solving saddle point systems like Karush–Kuhn–Tucker (KKT) systems is crucial for many algorithms in constrained nonlinear continuous optimization. Such systems can be very ill conditioned, in particular when the (1,1) block has few very small eigenvalues (see Rusten and Winther [SIAM J. Matrix Anal. Appl., 13 (1992), pp. 887–904]). 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 paper, we highlight some aspects of this interaction. We illustrate in particular, with some examples, how and in which circumstances the convergence of Minres might be affected by these few very small eigenvalues in the (1,1) block. We further derive theoretically a tighter lower bound on the positive eigenvalues of saddle point matrices of the KKT form.
AB - Efficiently solving saddle point systems like Karush–Kuhn–Tucker (KKT) systems is crucial for many algorithms in constrained nonlinear continuous optimization. Such systems can be very ill conditioned, in particular when the (1,1) block has few very small eigenvalues (see Rusten and Winther [SIAM J. Matrix Anal. Appl., 13 (1992), pp. 887–904]). 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 paper, we highlight some aspects of this interaction. We illustrate in particular, with some examples, how and in which circumstances the convergence of Minres might be affected by these few very small eigenvalues in the (1,1) block. We further derive theoretically a tighter lower bound on the positive eigenvalues of saddle point matrices of the KKT form.
KW - Ill-conditioning
KW - Minimum residual methods
KW - Saddle point systems
KW - Spectral analysis
UR - http://www.scopus.com/inward/record.url?scp=85049746865&partnerID=8YFLogxK
U2 - 10.1137/16M108152X
DO - 10.1137/16M108152X
M3 - Article
AN - SCOPUS:85049746865
VL - 39
SP - 712
EP - 736
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
SN - 0895-4798
IS - 2
ER -