Condition, complexity, and round-off in linear programming problems

Abstract

Let A E IRmxn, b E IRm and c E IRn. A number of linear programming problems (LPs) are associated to the triple d = (A, b, c). For instance, the Primal Feasibility problem (PF), the Dual Feasibility problem (DF), the Homogenous Feasibility problem (HF), the Optimal Solution problem in Primal-Dual Form (OSPDF) and the Optimal Value problem (OV). Our work deals with the use of condition numbers as parameters in expressions giving bounds for the complexity and/or the accuracy of algorithms solving these problems. We introduce a condition number %(A) for the problem (HF). We charaterize it in terms of ill-posedness and compare it with an existing condition number CHF (A) (introduced by Renegar) for the same problem. We provide an upper bound for the expected value of log %(A) where the entries of A are i.i.d. with standard normal distribution. A similar bound holds for log CHF (A). We introduce a condition number X(d) for the problem (OSPDF). We give two charaterizations via distances to degeneracy and singularity. We also give an upper bound for the expected value of log X(d). We provide an algorithm solving the problem (OSPDF) with finite precision. The complexity of this algorithm grows bounded by a low degree polynomial in m, n and log X(d). Estimates for the round-off error of this algorithm are also provided in terms of m, n and log X(d). Different linear programming problems associated to the triple d = (A, b, c) have different notions of ill-posedness which, in turn, induce diferent condition numbers (understood as relative distances to ill-posedness). We introduce a linear programming problem (a complementary partition problem) and show that its associated distance to ill-posedness naturally captures the distances to ill-posedness of all the problems above.

Date of Award	15 Jul 2004
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Felipe CUCKER (Supervisor)