OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Refining the lower bound on the positive eigenvalues of saddle point matrices with insights on the interactions between the blocks

Ruiz, Daniel and Sartenaer, Annick and Tannier, Charlotte Refining the lower bound on the positive eigenvalues of saddle point matrices with insights on the interactions between the blocks. (2018) SIAM Journal on Matrix Analysis and Applications, 39 (2). 712-736. ISSN 0895-4798

[img]
Preview
(Document in English)

PDF (Publisher's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
468kB

Official URL: https://doi.org/10.1137/16M108152X

Abstract

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.

Item Type:Article
Additional Information:SIAM: Society for Industrial and Applied Mathematics https://epubs.siam.org/doi/10.1137/16M108152X
HAL Id:hal-02348261
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Namur - UNamur (BELGIQUE)
Laboratory name:
Funders:
ANR : Agence nationale de la recherche, Programme Modèles Num ériques 2011 (France) - Belgian Science Policy Office, Interuniversity Attraction Poles Programme (Belgique)
Statistics:download
Deposited On:14 Oct 2019 12:25

Repository Staff Only: item control page