CONDITION MEASURES AND PROPERTIES OF THE CENTRAL TRAJECTORY OF A LINEAR PROGRAM

Citation
Ma. Nunez et Rm. Freund, CONDITION MEASURES AND PROPERTIES OF THE CENTRAL TRAJECTORY OF A LINEAR PROGRAM, Mathematical programming, 83(1), 1998, pp. 1-28
Citations number
32
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming","Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
ISSN journal
00255610
Volume
83
Issue
1
Year of publication
1998
Pages
1 - 28
Database
ISI
SICI code
0025-5610(1998)83:1<1:CMAPOT>2.0.ZU;2-U
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 li near program are inherently related to the condition number C(d) of th e data instance d = (A, b, c), where C(d) is a scale-invariant recipro cal of a closely-related measure p(d) called the ''distance to ill-pos edness'', (The distance to ill-posedness essentially measures how clos e the data instance d = (A, b, c) is to being primal or dual infeasibl e.) We present lower and upper bounds on sizes of optimal solutions al ong the central trajectory, and on rates of change of solutions along the central trajectory, as either the barrier parameter mu 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 associate d with the linear program, namely the condition number C(d), the dista nce to ill-posedness p(d), the norm of the data parallel to d parallel to, and the dimensions m and n. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.