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.
Key words: Interior Point Methods, Initial Point, Crash Start, Linear Programming, Quadratic Programming.