Calmness of partially perturbed linear systems with an application to interior point methods

M.J. Cánovas, J.A.J. Hall, M.A. López and J. Parra


In this paper we develop point-based formulas for the calmness modulus of feasible set mappings associated with partially perturbed linear inequality systems. This is done exclusively in terms of the nominal problem's data, not involving data in a neighborhood, since the expressions for the calmness moduli are given in terms of such nominal data.

As an application, the paper provides an estimation of the speed of convergence of the central path method in linear programming. The result gives an interesting insight into not only the componentwise convergence of the complementarity products, but the componentwise convergence of primal and dual solutions in the context of non-degeneracy.

Key words: Calmness, local error bounds, variational analysis, linear programming, feasible set mapping, interior point methods.

PDF CaHaLoPa16.pdf
Submitted to Linear Algebra and its Applications