J. Gondzio and A. Grothey
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. Recently there has been renewed interest in the subject.
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. Several techniques have been proposed to address this issue. Most of these aim to lead the iterate back into the interior of the feasible region - we classify them as either ``modification steps'' or ``unblocking steps'' depending on whether the modification is taking place before solving the modified problem to prevent future problems, or during the solution if and when problems become apparent.
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.
The relative performance of a selection of different warmstarting techniques suggested in the literature and the new proposed unblocking by sensitivity analysis is evaluated on the warmstarting test set based on a selection of NETLIB problems proposed by Benson and Shanno. Warmstarting techniques are also applied in the context of solving nonlinear programming problems as a sequence of quadratic programs solved by interior point methods. We also apply the warmstarting technique to the problem of finding the complete efficient frontier in portfolio management problems (a problem with 192 million variables - to our knowledge the largest problem to date solved by a warmstarted IPM). We find that the resulting best combined warmstarting strategy manages to save between 50\%-60\% of interior point iterations, consistently outperforming similar approaches reported in current optimisation literature.
Key words: Interior Point Methods, Warm Starts, Large Scale Optimization, Linear Programming, Quadratic Programming.