##
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