guest ::
login


Search  Submit  Help  Servei de Biblioteques  Sobre el DDD  Català English Español 
Home > Articles > Published articles > Condition measures and properties of the central trajectory of a linear program 
Date:  1998 
Abstract:  Given a data instance d = (A, b, c) of a linear program, we show that certain properties of solutions along the central trajectory of the linear program are inherently related to the condition number C(d) of the data instance d = (A, b, c), where C(d) is a scaleinvariant reciprocal of a closelyrelated measure (rho)(d) called the "distance to illposedness". (The distance to illposedness essentially measures how close the data instance d = (A, b, c) is to being primal or dual infeasible. ) We present lower and upper bounds on sizes of optimal solutions along the central trajectory, and on rates of change of solutions along the central trajectory, as either the barrier parameter µ or the data d = (A, b, c) of the linear program is changed. These bounds are all linear or polynomial functions of certain natural parameters associated with the linear program, namely the condition number C(d), the distance to illposedness (rho)(d), the norm of the data d and the dimensions m and n. 
Language:  Anglès. 
Document:  article ; recerca ; publishedVersion 
Subject:  Linear Programming ; Condition measures ; Central trajectory ; Analytic center ; Interiorpoint methods ; Approximate data ; Approximate solutions ; Perturbation theory 
Published in:  Mathematical Programming, vol. 83 n. 1 (1998) p. 128, ISSN 00255610 
28 p, 1.1 MB UAB restricted access 
The record appears in these collections:
Articles > Research articles
Articles > Published articles