Edinburgh Research Explorer

A New Unblocking Technique to Warmstart Interior Point Methods Based on Sensitivity Analysis

Research output: Contribution to journalArticlepeer-review

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://epubs.siam.org/doi/abs/10.1137/060678129
Original languageEnglish
Pages (from-to)1184-1210
Number of pages27
JournalSiam journal on optimization
Volume19
Issue number3
DOIs
Publication statusPublished - 2008

Abstract

One of the main drawbacks associated with Interior Point Methods (IPMs) 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 modi. cation 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, Comput. Optim. Appl., 38 (2007), pp. 371-399]. 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 and 60% of interior point iterations, consistently outperforming similar approaches reported in current optimization literature.

    Research areas

  • interior-point methods, warm-start, quadratic programming, WARM-START STRATEGIES, CUTTING-PLANE SCHEME, PROGRAMS, SOLVER

Download statistics

No data available

ID: 533936