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

Abstract:

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 {x}})}} {{m + \langle {\phi _{\mathsf {H}}}({\mathbf {x}}),{\mathbf {x}}\rangle }},\quad {\mathsf {where}}{\phi _{\mathsf {H}}}({\mathbf {x}}) = - \sum \limits _{j = 1}^m {\frac {{{{\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$.