Condition measures and properties of the central trajectory of a linear program
Nunez, Manuel A. (Chapman University (Orange, Estats Units d'Amèrica). School of Business and Economics)
Freund, Robert M. (Sloan School of Management)

Fecha: 1998
Resumen: 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 scale-invariant reciprocal of a closely-related measure (rho)(d) called the "distance to ill-posedness". (The distance to ill-posedness 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 ill-posedness (rho)(d), the norm of the data d and the dimensions m and n.
Derechos: Tots els drets reservats.
Lengua: Anglès
Documento: Article ; recerca ; Versió publicada
Materia: Linear Programming ; Condition measures ; Central trajectory ; Analytic center ; Interior-point methods ; Approximate data ; Approximate solutions ; Perturbation theory
Publicado en: Mathematical Programming, vol. 83 n. 1 (1998) p. 1-28, ISSN 0025-5610



28 p, 1.1 MB
 Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2006-03-13, última modificación el 2023-06-03



   Favorit i Compartir