Name
Title | ||
|---|---|---|
On the complexity of following the central path of linear programs by linear extrapolation II |
Abstract | ||
|---|---|---|
A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, d) of steps needed to go from an initial pointx(R) to a final pointx(d), R>d>0, by an integral of the local “weighted curvature” of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr?0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constma log(R/d), wherea a = 1/4 ora = 3/8 (note thata = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only fora ? 1/3. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BF01582904 | Math. Program. |
Keywords | DocType | Volume |
linear program,linear extrapolation,central path,lower bound | Journal | 52 |
Issue | ISSN | Citations |
3 | 0025-5610 | 21 |
PageRank | References | Authors |
3.03 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| G. Sonnevend | 1 | 21 | 3.03 |
| J. Stoer | 2 | 155 | 51.88 |
| G. Zhao | 3 | 21 | 3.03 |