zbMATH — the first resource for mathematics

A study of indicators for identifying zero variables in interior-point methods. (English) Zbl 0801.65056
This study is concerned with constrained optimization problems where the only inequality constraints are nonnegativity constraints on the variables. In these problems, the ability to identify zero variables (binding constraints) early on in an iterative method is of considerable value and can be used to computational advantage.
This work first gives a formal presentation of the notion of indicators for identifying zero variables, and then studies especially the following three indicators proposed in the literature for use with interior-point methods for linear programming: The variables as indicators, a primal- dual indicator and the Tapia indicator.
Both theory and experimentation are presented that speak strongly against the use of the variables as indicators. This study implies that the Tapia indicator is more effective than the primal-dual indicator in identifying zero variables in the context of primal-dual interior point methods.
The authors study also the local rate of convergence for several indicators. In an appendix various indicators are catalogued that appear in the literature. 51 references are given.
Reviewer: J.Terno (Dresden)

65K05 Numerical mathematical programming methods
90C05 Linear programming
Full Text: DOI