On free variables in interior point methods

Csaba Meszaros

Interior point methods, especially the algorithms for linear programming problems are sensitive if unconstrained variables are presented in the problem. While replacing free variables by nonnegative ones may cause numerical instabilities, their implicit handling results in semidefinite scaling matrix during iterations. In the paper we investigate the effects if the scaling matrix is regularized during interior point iterations. Our analysis will prove that the effect of the regularization can be easily monitored and corrected if necessary. We described the regularization scheme primary for efficient handling of free variables, but similar analysis can be made for the case, when the small scaling factors are improved to larger ones. We will show the superiority of our approach over the variable replacement method on a set of test problems arising from water management application.

Departmental Technical Report DOC 97/4, Imperial College, London, UK.

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]