Rudiments of an average case complexity theory for piecewise-linear path following algorithms (Q1111475)

We examine the efficiency of PL path following algorithms in following \(F_ T^{-1}(0)\), where \(F_ T\) is the PL approximation, induced by the simplicial triangulation T, to a map f: \({\mathbb{R}}^ n\to {\mathbb{R}}^{n-1}\). In particular, we consider the problem of determining an upper bound on the expected number of pivots made per unit length of \(f^{-1}(0)\) that is approximated. We show that if the sizes of the simplices of T are ``sufficiently small'', where ``sufficiently small'' is an explicit given quantity dependent on measurements of how ``nice'' f is, then the average directional density of T, as introduced by Todd, really does give a good approximation to the expected number of pivots made, confirming what researchers have believed on intuitive grounds for a decade. Because what constitutes ``sufficiently small'' is a precisely given quantity, i.e., non-asymptotic, we are able to provide some rigorous justification for the claim that the expected number of pivots grows only polynomially in n, the number of variables. Several other issues are also examined.