The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/65830
Record Status Checked
Record Id 65830
Title Iterative methods within optimization problems
Abstract One of the major bottlenecks in modern optimization codes is the requirement to solve multiple so-called saddle point systems. For example, primal-dual interior point methods apply variants of Newton's method to a non-linear system to find a minimum of constrained quadratic program. This method requires the solution of a sequence of saddle point systems of the form above -- called the augmented system in this context -- at each step of the Newton iteration. In many situations -- especially for large scale optimization problems -- we would like to solve the saddle point system iteratively, as computing the factorizations at each Newton step to employ a direct solver would be prohibitively expensive. However, it is important to choose the iterative solver so that the errors are sympathetic to the outer Newton iteration. For this reason Krylov subspace methods with constraint preconditioners have been popular in the optimization community, as they are known to preserve the constraints, and this fact can be used to prove convergence of the inexact Newton method. However, applying such a preconditioner can be costly, and ensuring that the solution remains on the constraint manifold in the presence of rounding errors can be delicate. Block diagonal preconditioners have proved successful in, e.g., the field of computational fluid dynamics, due to their ease of application and effectiveness. However, giving conditions for the convergence of an inexact Newton method when using such an iterative method is not trivial. In this talk I will describe a way to combine both of these preconditioners in an inner iteration, using the easy to apply block diagonal preconditioner to do most of the work, and then using one application of the constraint preconditioners to project the approximate solution onto the constraint manifold. We hope that this will increase the number of types of preconditioners which can be used safely in constrained optimization problems, and therefore will lead to the development of more high-quality preconditioners tailored to this important field.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Presentation Presented at 25th Biennial Conference on Numerical Analysis, Glasgow, Scotland, 25-28 Jun 2013. Strath2013.pdf 2013