An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
Clóvis C. Gonzaga, Michael J. Todd · SIAM Journal on Optimization · 1992
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Optimization · Society for Industrial and Applied Mathematics · article · 1992
Abstract
An algorithm based on reducing a suitable potential function for linear programming is described. At each iteration, separate scalings are applied to the primal and dual problems, and a step is taken in either the primal or the dual space. It is shown that a constant reduction can always be achieved, leading to a bound of $O(n^{1/2} L)$ iterations. Moreover, it is also shown that a reduction of $\Omega (n^{1/4} )$ can usually be obtained, so that $O(n^{1/4} L)$ iterations are expected to suffice. Finally, it is proved that no general algorithm taking either primal or dual steps and guaranteeing the reduction of such a potential function can achieve R-order of convergence greater than one.
Open the resolved locator · 10.1137/0802017
Metadata licence: OpenAlex metadata (CC0)