Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

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


Author: J. C. Lagarias
Journal: Trans. Amer. Math. Soc. 320 (1990), 193-225
MSC: Primary 90C05
DOI: https://doi.org/10.1090/S0002-9947-1990-1058199-0
MathSciNet review: 1058199
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle {\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 $.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 90C05

Retrieve articles in all journals with MSC: 90C05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1990-1058199-0
Article copyright: © Copyright 1990 American Mathematical Society