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] (Unpublished)
Download (507kB) | Preview
|Item Type:||Tesi di dottorato|
|Uncontrolled Keywords:||Iterative solution of KKT systems, Quadratic programming, Potential reduction method|
|Date Deposited:||30 Jul 2008|
|Last Modified:||30 Apr 2014 19:22|
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.
Actions (login required)