haku: @indexterm complexity / yhteensä: 120
viite: 60 / 120
| Tekijä: | Peng, J. Roos, C. Terlaky, T. |
| Otsikko: | A new class of polynomial primal-dual methods for linear and semidefinite optimization |
| Lehti: | European Journal of Operational Research
2002 : DEC, VOL. 143:2, p. 234-256 |
| Asiasana: | OPTIMIZATION METHOD STUDY COMPLEXITY |
| Kieli: | eng |
| Tiivistelmä: | The authors propose a new class of primal-dual methods for linear optimization (LO). By using some new analysis tools, the authors prove that the large-update method for LO based on the new search direction has a polynomial complexity of O (n'4/(4+p)log(n/e)) iterations, where p is between [0,2] is a parameter used in the system defining the search direction. If p = 0, the authors' results reproduce the well-known complexity of the standard primal-dual Newton method for LO. At each iteration, the authors' algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented. The paper provides a substantial list of references on this subject. |
SCIMA