The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry

This paper studies projective scaling trajectories, which are the trajectories obtained by following the infinitesimal version of Karmarkar's linear programming algorithm. A nonlinear change of variables, projective Legendre transform coordinates, is introduced to study these trajectories. The projective Legendre transform mapping has a coordinate-free geometric interpretation in terms of the notion of "centering by a projective transformation." Let ${\mathsf{H}}$ be a set of linear programming constraints $\{ \langle {{\mathbf{a}}_j},{\mathbf{x}}\rangle \geq {b_j}:1 \leq j \leq m\}$ on ${{\mathbf{R}}^n}$ such that its polytope of feasible solutions ${P_{\mathsf{H}}}$ is bounded and contains ${\mathbf{0}}$ in its interior. The projective Legendre transform mapping ${\psi _{\mathsf{H}}}$ is given by

$${\psi _{\mathsf{H}}}({\mathbf{x}}) = \frac{{{\phi _{\mathsf{H}}}(... ...{{{\mathbf{a}}_j}}} {{\langle {{\mathbf{a}}_j},{\mathbf{x}}\rangle - {b_j}}}.}$$

Here ${\phi _{\mathsf{H}}}(x)$ is the Legendre transform coordinate mapping introduced in part II. ${\psi _{\mathsf{H}}}({\mathbf{x}})$ is a one-to-one and onto mapping of the interior of the feasible solution polytope $\operatorname{Int} ({P_{\mathsf{H}}})$ to the interior of its polar polytope $\operatorname{Int} (P_{\mathsf{H}}^\circ )$. The set of projective scaling trajectories with objective function $\langle {\mathbf{c}},{\mathbf{x}}\rangle - {c_0}$ are mapped under ${\psi _{\mathsf{H}}}$ to the set of straight line segments in $\operatorname{Int} (P_{\mathsf{H}} ^\circ )$ passing through the boundary point $- {\mathbf{c}}/{c_0}$ of $P_{\mathsf{H}} ^\circ$. As a consequence the projective scaling trajectories (for all objective functions) can be interpreted as the complete set of "geodesics" (actually distinguished chords) of a projectively invariant metric geometry on $\operatorname{Int} ({P_{\mathsf{H}}})$, which is isometric to Hilbert geometry on the interior of the polar polytope $P_{\mathsf{H}}^\circ$.