The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry
Authors: Lagarias J. C. 
Published: June 2012

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

H

{\mathsf {H}}

be a set of linear programming constraints

{
⟨

a

j

,

x

⟩
≥

b
j

:
1
≤
j
≤
m
}

\{ \langle {{\mathbf {a}}_j},{\mathbf {x}}\rangle \geq {b_j}:1 \leq j \leq m\}

on

R

n

{{\mathbf {R}}^n}

such that its polytope of feasible solutions

P

H

{P_{\mathsf {H}}}

is bounded and contains

0

{\mathbf {0}}

in its interior. The projective Legendre transform mapping

ψ

H

{\psi _{\mathsf {H}}}

is given by
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi Subscript sans-serif upper H Baseline left-parenthesis bold x right-parenthesis equals StartFraction phi Subscript sans-serif upper H Baseline left-parenthesis bold x right-parenthesis Over m plus mathematical left-angle phi Subscript sans-serif upper H Baseline left-parenthesis bold x right-parenthesis comma bold x mathematical right-angle EndFraction comma sans-serif w sans-serif h sans-serif e sans-serif r sans-serif e phi Subscript sans-serif upper H Baseline left-parenthesis bold x right-parenthesis equals minus sigma-summation Underscript j equals 1 Overscript m Endscripts StartFraction bold a Subscript j Baseline Over mathematical left-angle bold a Subscript j Baseline comma bold x mathematical right-angle minus b Subscript j Baseline EndFraction period">

ψ

H

(

x

)
=

ϕ

H

(

x

)

m
+
⟨

ϕ

H

(

x

)
,

x

⟩

,

w
h
e
r
e

ϕ

H

(

x

)
=
−

∑

j
=
1

m

a

j

⟨

a

j

,

x

⟩
−

b
j

.

{\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

ϕ

H

(
x
)

{\phi _{\mathsf {H}}}(x)

is the Legendre transform coordinate mapping introduced in part II.

ψ

H

(

x

)

{\psi _{\mathsf {H}}}({\mathbf {x}})

is a one-to-one and onto mapping of the interior of the feasible solution polytope

Int
⁡
(

P

H

)

\operatorname {Int} ({P_{\mathsf {H}}})

to the interior of its polar polytope

Int
⁡
(

P

H

∘

)

\operatorname {Int} (P_{\mathsf {H}}^\circ )

. The set of projective scaling trajectories with objective function

⟨

c

,

x

⟩
−

c
0

\langle {\mathbf {c}},{\mathbf {x}}\rangle - {c_0}

are mapped under

ψ

H

{\psi _{\mathsf {H}}}

to the set of straight line segments in

Int
⁡
(

P

H

∘

)

\operatorname {Int} (P_{\mathsf {H}} ^\circ )

passing through the boundary point

−

c

/

c
0

- {\mathbf {c}}/{c_0}

of

P

H

∘

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

Int
⁡
(

P

H

)

\operatorname {Int} ({P_{\mathsf {H}}})

, which is isometric to Hilbert geometry on the interior of the polar polytope

P

H

∘

P_{\mathsf {H}}^\circ

.