On the application of iterative solvers to KKT systems in Interior Point methods for Large-Scale Quadratic Programming problems

Cafieri, Sonia (2006) On the application of iterative solvers to KKT systems in Interior Point methods for Large-Scale Quadratic Programming problems. [Tesi di dottorato] (Inedito)

Full text disponibile come:

[img]PDF - Richiede un editor Pdf del tipo GSview, Xpdf o Adobe Acrobat Reader
495Kb

Abstract

Interior Point methods for linear and nonlinear optimization problems have received an increasing attention in the last years. A crucial issue in the development of efficient Interior Point software is the solution of the linear system, named KKT system, that arises at each iteration of the method. Iterative solvers appear to be very promising, however the use of effective preconditioners is mandatory because of the increasing ill-conditioning of the system when the iterates generated by the Interior Point method approach the solution. The aim of the research activity described in this thesis has been the analysis, the development and the implementation of iterative methods for the efficient solution of the KKT systems arising at each iteration of Interior Point methods for large-scale convex Quadratic Programming problems. We focus on KKT systems reduced to the well known augmented system and normal equations forms and we consider a preconditioned Conjugate Gradient method for their solution. Specifically we consider an incomplete Cholesky factorization with limited memory for the normal equations approach and a constraint preconditioner for the augmented system approach. In the last case, we analyze the behaviour of the constraint preconditioner with the Conjugate Gradient algorithm and we show, for KKT systems deriving from linear inequality constraints and nonnegativity bounds on the variables, the equivalence with a suitable preconditioned Conjugate Gradient applied to the positive definite normal equations. The Interior Point framework is given by the Potential Reduction method. Due to our interest on the iterative solution of the linear systems, we extend convergence results for the Potential Reduction method in the case of inexact solution of the KKT system arising at each iteration. We describe two software packages that have been developed for solving large-scale convex quadratic problems with the considered algorithms. We discuss some implementation issues, mainly focusing on those related to the solution of the KKT systems with iterative methods. We describe a computational study of stopping criteria of the preconditioned Conjugate Gradient method for solving the KKT systems. We present results of numerical experiments carried out to verify the effectiveness of the proposed approaches on a set of large-scale quadratic problems. We also compare our software packages to a well-estabilished software for nonlinear optimization problems.

Tipologia di documento:Tesi di dottorato
Parole chiave:Iterative solution of KKT systems, Quadratic programming, Potential reduction method
Settori scientifico-disciplinari MIUR:Area 01 Scienze matematiche e informatiche > MAT/08 ANALISI NUMERICA
Coordinatori della Scuola di dottorato:
Coordinatore del Corso di dottoratoe-mail (se nota)
Rionero, Salvatore
Tutor della Scuola di dottorato:
Tutor del Corso di dottoratoe-mail (se nota)
D'Apuzzo, Marco
Stato del full text:Accessibile
Data:2006
Numero di pagine:123
Istituzione:Università degli Studi di Napoli Federico II
Dipartimento o Struttura:Matematica e Applicazioni
Tipo di tesi:Dottorato
Stato dell'Eprint:Inedito
Scuola di dottorato:Scuola di Scienze Matematiche
Denominazione del dottorato:Scienze Matematiche
Ciclo di dottorato:XVII
Numero di sistema:535
Depositato il:30 Luglio 2008
Ultima modifica:04 Febbraio 2009 09:38

Solo per gli Amministratori dell'archivio: edita il record