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)

Anteprima

PDF Cafieri.pdf Download (507kB) | Anteprima

[error in script] [error in script]

Tipologia del documento:	Tesi di dottorato
Lingua:	English
Titolo:	On the application of iterative solvers to KKT systems in Interior Point methods for Large-Scale Quadratic Programming problems
Autori:	Autore Email Cafieri, Sonia [non definito]
Data:	2006
Tipo di data:	Pubblicazione
Numero di pagine:	123
Istituzione:	Università degli Studi di Napoli Federico II
Dipartimento:	Matematica e applicazioni "Renato Caccioppoli"
Dottorato:	Scienze matematiche
Ciclo di dottorato:	17
Coordinatore del Corso di dottorato:	nome email Rionero, Salvatore [non definito]
Tutor:	nome email D'Apuzzo, Marco [non definito]
Data:	2006
Numero di pagine:	123
Parole chiave:	Iterative solution of KKT systems, Quadratic programming, Potential reduction method
Settori scientifico-disciplinari del MIUR:	Area 01 - Scienze matematiche e informatiche > MAT/08 - Analisi numerica
Depositato il:	30 Lug 2008
Ultima modifica:	01 Dic 2014 13:49
URI:	http://www.fedoa.unina.it/id/eprint/535
DOI:	10.6092/UNINA/FEDOA/535

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.

Downloads

Actions (login required)

Modifica documento