Condition Measures and Properties of the Central Trajectory of a Linear Program

Manuel A. Nunez and Robert M. Freund

The central trajectory of a linear program consists of the set of optimal solutions $x(\mu)$ and $(y(\mu), s(\mu))$ to the logarithmic barrier problems: \[ \begin{array}{cl} (P_{\mu}(d)): & \min \{ c^{T}x + \mu p(x) : Ax = b, x > 0\}, \\ (D_{\mu}(d)): & \max \{ b^{T}y - \mu p(s) : A^{T}y + s = c, s > 0\}, \end{array}\] where $p(u) = -\sum_{i=1}^{n} \ln (u_{i})$, is the logarithmic barrier function, $d = (A, b, c)$ is a data instance in the space of all data ${\cal D} = \{(A, b, c) : A \in \Re^{mn}, b \in \Re^{m}, c \in \Re^{n}\}$, and the parameter $\mu$ is a positive scalar considered independent of the data instance $d \in{\cal D}$.

This study shows that certain properties of solutions along the central trajectory of a linear program are inherently related to the condition number ${\cal C}(d)$ of the data instance $d=(A,b,c)$, where the condition number ${\cal C}(d)$ and a closely-related measure $\rho(d)$ called the ``distance to ill-posedness" were introduced by Renegar in a recent series of papers ~\cite{ren3,ren1,ren2}. In the context of the central trajectory problem, $\rho(d)$ essentially measures how close the data instance $d=(A,b,c)$ is to be being infeasible for $(P_{\mu}(d))$, and ${\cal C}(d)\ {\underline {\underline \Delta}}\ \|d\|/\rho(d)$ is a scale-invariant reciprocal of the distance to ill-posedness $\rho(d)$, and so ${\cal C}(d)$ goes to $\infty$ as the data instance $d=(A,b,c)$ approaches infeasibility. 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 $\mu$ changes or the data $d$ changes, where these bounds are all polynomial functions of $\mu$ and are linear or polynomial functions of the condition number ${\cal C}(d)$ and the related distance to ill-posedness $\rho(d)$ of the data instance $d=(A,b,c)$.

Technical Report, March, 1996.

Contact: rfreund@MIT.EDU