We begin with a study of the infeasibility measures for linear programming problems. For this purpose, we consider feasibility problems in Karmarkar's standard form. Our main focus is on the complexity measures which can be used to bound the amount of computational effort required to solve systems of linear inequalities and related problems in certain ways. We propose a new complexity measure that is particularly well-suited for the generalized Tardos' scheme for the real number data model. We prove that the new measure is between Ye's (smallest large variable) measure and $\chibar$. We present geometric interpretations of the complexity measures and then turn to the sensitivity analyses and the computation of the directional derivatives of the complexity measures. For this purpose, various sets of allowed perturbations are identified (depending on the complexity measure) using the minimal and maximal sign vectors of the subspaces involved. Finally, we consider the generalization of infeasibility certificates to convex optimization problems in conic form. We present a geometric generalization of a condition measure proposed by Cheung-Cucker. We derive various new relationships amongst the existing and new complexity measures in this context.
Citation
Research Report CORR 2002-10, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, May 2002