Each step of an interior point method for linear and non-linear optimization requires the solution of a system of equations which is symmetric and indefinite. Such a system is often called a saddle point or KKT problem. As the problem size increases, the use of direct methods to solve this system may become prohibitively expensive and iterative methods become a viable alternative.
We will propose the use of implicitly defined constraint preconditioners when (approximately) solving saddle point problems iteratively. These preconditioners only require the factorization of smaller sparse systems and can be shown to give favourable Krylov subspace properties as well as allowing us to use a conjugate gradient-based iterative method. However, they often require a preprocessing step which carries out a symmetric permutation of the saddle point problem. This permutation strongly relates to finding a nullspace basis of the linearized constraint space for the underlying optimization problem, but we would also like to take additional characteristics of the Hessian into account when forming the permutation. We will discuss the desirable properties of such a permutation and how this might be achieved. Numerical experiments comparing several possible methods will be presented.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
