On the Robustness of Interior Methods

It is well known that interior methods for linear programming perform
very poorly (and even fail) if the starting point is unfavorable. To
overcome this problem it is common practice to employ heuristics for
choosing the initial point, initial slacks and multipliers. These heurisitics
are not always successful, and it would be desirable to guarantee the
effectiveness of interor methods in all circumstances. Moreover, these
heuristics, which routinely choose very large initial estimates, are
not appropriate for
nonlinear programming problems, where the initial point must be chosen
in the region of interest.

In this work we study the reasons for the poor performance of interior
iterations from certain regions. We attribute the difficulties to a design
feature common to most (if not all) interior approaches, namely the lack of
coordination between the Newton direction and the imposition of non-negativity
constraints. We investigate two strategies for overcoming the problem, and
contrast their properties with that of standard approaches. We conclude by
testing the computational effectiveness of the new strategies in the
solution of linear, quadratic and nonlinear programming problems.