A Study of Indicators for Identifying Zero Variables in Interior Point Methods
Abstract
In this study we are 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. In this work we first give a formal presentation of the notion of indicators for identifying zero variables, and then study various indicators proposed in the literature for use with interior-point methods for linear programming. We present both theory and experimentation that speaks strongly against the use of the variables as indicators; perhaps the most frequently used indicator in the literature. Our study implies that an indicator proposed by Tapia in 1980 is particularly effective in the context of primal-dual interior-point methods. We also study the local rate of convergence for several indicators.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1993
- Accession Number
- ADA452703
Entities
People
- A. S. El-bakry
- Richard A. Tapia
- Yinglong Zhang
Organizations
- Rice University