1. Refining the lower bound on the positive eigenvalues of saddle point matrices with insights on the interactions between the blocks
- Author
-
Charlotte Tannier, Annick Sartenaer, Daniel Ruiz, Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Université de Namur - UNamur (BELGIQUE), Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National Polytechnique (Toulouse) (Toulouse INP), Namur Center for Complex Systems [Namur] (NaXys), Université de Namur [Namur] (UNamur), and Institut National Polytechnique de Toulouse - INPT (FRANCE)
- Subjects
Karush–Kuhn–Tucker conditions ,Ill conditioning ,0211 other engineering and technologies ,Mathematics::Optimization and Control ,010103 numerical & computational mathematics ,02 engineering and technology ,Spectral analysis ,01 natural sciences ,Upper and lower bounds ,Minimum residual methods ,Statistics::Machine Learning ,Refining ,Saddle point ,Applied mathematics ,0101 mathematics ,[MATH]Mathematics [math] ,Ill-conditioning ,Eigenvalues and eigenvectors ,Mathematics ,Continuous optimization ,Traitement du texte et du document ,021103 operations research ,AMS: 15A42, 65F10 ,Nonlinear system ,Saddle point systems ,Analysis - Abstract
International audience; 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.
- Published
- 2018
- Full Text
- View/download PDF