Andreas Grothey (University of Edinburgh)

Unblocking interior point warmstarts by sensitivity analysis
Wednesday 20 February 2008 at 15.30, JCMB 3218

Abstract

One of the main drawbacks associated with Interior Point Methods (IPM) is the perceived lack of an efficient warmstarting scheme which would enable the use of information from a previous solution of a similar problem.

A common problem with warmstarting for IPM is that an advanced starting point which is close to the boundary of the feasible region, as is typical, might lead to blocking of the search direction. A new "unblocking" strategy is suggested which attempts to directly address the issue of blocking by performing sensitivity analysis on the Newton step with the aim of increasing the size of the step that can be taken. This analysis is used in a new technique to warmstart interior point methods: we identify components of the starting point that are responsible for blocking and aim to improve these by using our sensitivity analysis.

Our method compares favourably with other warmstarting strategies on a selction of testproblems ranging from NETLIB to finding the efficient frontier of an asset liability management problem with 192 million variables. On average 50%-60% of iterations can be saved compared to a cold started IPM.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996