Continous analogue of Hirsch conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $P=\{x\in\mathbb R^d:a_i^Tx\leq b_i,\ 1\leq i\leq n\}$ be a bounded full-dimensional polytope with a strictly feasible point; the displayed inequality representation is part of the data. For $c\in\mathbb R^d\setminus\{0\}$ and $\mu>0$, its primal logarithmic-barrier central path is the unique point \[x(\mu)=\operatorname*{arg\,min}_{x\in\operatorname{int}P}\left(c^Tx-\mu\sum_{i=1}^n\log(b_i-a_i^Tx)\right).\] The total curvature is the total variation of its unit tangent, equivalently the integral $\int\|dT/ds\|_2\,ds$ along an arc-length parametrization, or the supremum of sums of turning angles of ordered inscribed polygonal paths. Let $\Lambda(d,n)$ be the supremum of this total curvature over all such $n$-inequality descriptions in dimension $d$ and all nonzero $c$.

Statement recorded in the supplied source.

Is the total curvature bounded linearly in the number of inequalities, uniformly over the dimension? That is, does an absolute constant $C$ exist such that \[\Lambda(d,n)\leq Cn\quad\text{for every admissible }d,n?\] This is the continuous Hirsch conjecture recorded in the source; the cited original research gives its historical counterexample context. [S2][S3]

Short English statement

Is the worst-case turning of the primal central path at most a constant times the number of defining inequalities, uniformly in dimension?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3098 (OPG-610). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Deza, Antoine; Terlaky, Tamas; Zinchenko, Yuriy, Continous analogue of Hirsch conjecture, Open Problem Garden, node 610. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/continous_analogue_of_hirsch_conjecture.
• S3 Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert and Michael Joswig, Long and winding central paths, arXiv:1405.4161v3 (2017). Introduction; Section2.3 (log-barrier central path); Section5 (totalcurvature). https://arxiv.org/pdf/1405.4161.