Optimization Online


Condition and complexity measures for infeasibility certificates of systems of linear inequalities and their sensitivity analysis

Hugo J. Lara (hogol***at***ucla.edu.ve)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: 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.

Keywords: linear inequality systems, linear programming, convex optimization, computational complexity, complexity measures, condition measures, interior-point methods

Category 1: Linear, Cone and Semidefinite Programming

Citation: Research Report CORR 2002-10, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, May 2002

Download: [Compressed Postscript]

Entry Submitted: 05/21/2002
Entry Accepted: 05/21/2002
Entry Last Modified: 05/21/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society