Condition measures and properties of the central trajectory of a linear program |
| |
Authors: | Manuel A Nunez Robert M Freund |
| |
Institution: | (1) School of Business and Economics, Chapman University, 333 N. Glassell Str., 92866 Orange, CA, USA;(2) Sloan School of Management, MIT, 02139 Cambridge, MA, USA |
| |
Abstract: | Given a data instanced=(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 instanced=(A, b, c), where C(d) is a scale-invariant reciprocal of a closely-related measure ρ(d) called the “distance to ill-posedness”. (The distance to ill-posedness essentially measures how close the data instanced=(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 datad=(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 ρ(d), the norm of the data ‖d‖, and the dimensionsm andn. |
| |
Keywords: | Linear Programming Condition measures Central trajectory Analytic center Interior-point methods Approximate data Approximate solutions Perturbation theory |
本文献已被 SpringerLink 等数据库收录! |
|