Curvature of the Central Path in Linear Programming

Overview:
 The field of optimization is ubiquitous to countless applications in engineering and sciences. Within the past 3 decades, the field of convex optimization was revolutionized with the introduction of the so-called Interior Point Methods (IPM). These methods allow solving many large-scale optimization problems very efficiently and already found ways into a number of leading commercial numerical software packages like CPLEX, Gurobi, Mosek, etc. Despite reach and beautiful theory of these methods, some essential gaps in our understanding of convex optimization still exist. For example, a question of whether a linear optimization problem can be solved in strongly polynomial time is cited by the Fields medalist Stephen Smale as one of the top mathematical problems for the XXI century.

Central path – a real analytic curve underlying the complexity analysis of majority of IPM – has first drawn the attention of researchers since the very inception of IPM some 20+ years ago. It is believed that the complexity and thus the numerical efficiency of IPM are intimately connected to the geometric properties of the path. Despite that, the geometric-algebraic properties of the path are still poorly understood, even for linear optimization. Specifically, we still do not have a full understanding of the worst-case total curvature of the central path, which in turn holds one the greater promises for further algorithmic improvements. Some connections to IPM algorithm complexity were established over the course of 3 decades of IPM theory development. However, insofar all of the previous attempts – Sonnevend’s curvature surrogate, Vavasis-Ye crossover events, Tsuchiya-Monteiro analysis of the two – fall short of connecting with the true geometric curvature, in large part due to the fact that the curvature itself remained elusive. Interestingly, despite a well-grounded interest in understanding the true curvature of the path, no major advancements were made until 2000, when a novel set of methods largely borrowing on algebraic geometry – tools mostly uncommon in large optimization community – was used for the first time.

In early 2000 Dedieu, Malajovich and Shub established first pivotal result towards understanding the total curvature of the path, essentially bounding the average curvature with the number of embedding dimensions. In 2008 in the work of Deza, Terlaky and Zinchenko, a few pivotal observations were made regarding the worst-case curvature and a relationship to the combinatorial structure of the underlying polytope was hypothesized. Using more algebraic techniques, some refinements of these results soon followed in work of De Loera, Sturmfels and Vinzant in 2010. In 2014, using the techniques of tropical geometry, in a unexpected break-through work of Allamigeon, Benchimol, Gaubert and Joswig it was shown that in fact the total curvature of the path may grow exponential in the dimension. The latter result not only disproves a number of pre-existing conjectures, but possibly even sheds light on possibility of the existence of strongly-polynomial IPM-based method for linear programming.

Objectives:
 Our goal is to give tight bounds on the worst-case curvature of the central path, at least in low dimensions and / or a family of special polytopes. To this extant, the objectives are:
 (1) improve worst-case lower bound construction to account for the number of inequalities in generic dimension,
 (2) identify a set of most promising techniques used for such constructions, and attempt to reconcile tropical and convex geometry perspectives on the problem,
 (3) bound the total curvature of the path in dimension 2 with 3-5 inequalities,
 (4) investigate if any of the methods extend to larger hyperplane arrangements, and
 (5) identify a special family of polytopes (like transportation polytopes) where further tight curvature estimates can be made.

We believe that the timing and tools are finally right to make progress towards extending our understanding of this challenging and important problem. By bringing together a diverse group of mathematicians working in the area and having the necessary broad and otherwise uncommon expertise, including convex geometry, algebraic and tropical geometry, convex optimization and IPM theory, we hope that indeed the progress in understanding the worst-case path curvature will be made, at least in low dimensions. We view BIRS FRG as the unique and the right opportunity for our group to achieve our goals.