Crash start of interior point methods

Research output: Contribution to journalArticlepeer-review

Abstract

The starting point used by an interior point algorithm for linear and convex quadratic programming may significantly influence the behaviour of the method. A widely used heuristic to construct such a point consists of dropping variable nonnegativity constraints and computing a solution which minimizes the Euclidean norm of the primal (or dual) point while satisfying the appropriate primal (or dual) equality constraints, followed by shifting the variables so that all their components are positive and bounded away from zero. In this Short Communication a new approach for finding a starting point is proposed. It relies on a few inexact Newton steps performed at the start of the solution process. A formal justification of the new heuristic is given and computational results are presented to demonstrate its advantages in practice. Computational experience with a large collection of small- and medium-size test problems reveals that the new starting point is superior to the old one and saves 20–40% of iterations needed by the primal-dual method. For larger and more difficult problems this translates into remarkable savings in the solution time.
Original languageEnglish
Pages (from-to)308-314
Number of pages12
JournalEuropean Journal of Operational Research
Volume255
Issue number1
Early online date20 May 2016
DOIs
Publication statusPublished - 16 Nov 2016

Fingerprint

Dive into the research topics of 'Crash start of interior point methods'. Together they form a unique fingerprint.

Cite this