Details

Autor(en) / Beteiligte

• Hung, Pi-Fang
• Ye, Yinyu

Titel

An Asymptotical $O(\sqrt{n} L)$-Iteration Path-Following Linear Programming Algorithm That Uses Wide Neighborhoods

Ist Teil von

• SIAM journal on optimization, 1996-08, Vol.6 (3), p.570-586

Ort / Verlag

Philadelphia: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1996

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Path-following linear programming (LP) algorithms generate a sequence of points within certain neighborhoods of a central path $\mathcal{C}$ which prevent iterates from prematurely getting too close to the boundary of the feasible region. Depending on the norm used, these neighborhoods include $\mathcal{N}_2 ( \beta ),\mathcal{N}_\infty ( \beta )$, and $\mathcal{N}_\infty^- ( \beta )$ where $\beta \in (0,1)$ and \[ \mathcal{C} \subset \mathcal{N}_2 ( \beta ) \subset \mathcal{N}_\infty ( \beta ) \subset \mathcal{N}_\infty^- ( \beta )\quad {\text{for each}}\quad\beta \in ( 0,1). \] A paradox is that among all existing (infeasible or feasible) path-following algorithms, the theoretical iteration complexity, $O(\sqrt{n} L)$, of small-neighborhood $(\mathcal{N}_2 )$ algorithms is significantly better than the complexity, $O(nL)$, of wide-neighborhood $(\mathcal{N}_\infty^- )$ algorithms. In practice, wide-neighborhood algorithms outperform small-neighborhood ones by a big margin. Here, $n$ is the number of LP variables and $L$ is the LP data length. In this paper, we present an $O(n^{\frac{n + 1}{2n}} L)$-iteration (infeasible) primal-dual high-order algorithm that uses wide neighborhoods. Note that this iteration bound is asymptotically $O(\sqrt{n} L)$, i.e., the best bound for small-neighborhood algorithms, as $n$ increases.