A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
-
- Renato D. C. Monteiro
- AT&T Bell Laboratories, Holmdel, New Jersey 07733
-
- Ilan Adler
- Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
-
- Mauricio G. C. Resende
- AT&T Bell Laboratories, Murray Hill, New Jersey 07974
書誌事項
- 公開日
- 1990-05
- DOI
-
- 10.1287/moor.15.2.191
- 公開者
- Institute for Operations Research and the Management Sciences (INFORMS)
この論文をさがす
説明
<jats:p> We describe an algorithm for linear and convex quadratic programming problems that uses power series approximation of the weighted barrier path that passes through the current iterate in order to find the next iterate. If r ≥ 1 is the order of approximation used, we show that our algorithm has time complexity O(n<jats:sup>½(1 + 1/</jats:sup><jats:sup>r</jats:sup>)L<jats:sup>(1 + 1/</jats:sup><jats:sup>r</jats:sup><jats:sup>)</jats:sup>) iterations and O(n<jats:sup>3</jats:sup> + n<jats:sup>2</jats:sup>r) arithmetic operations per iteration, where n is the dimension of the problem and L is the size of the input data. When r = 1, we show that the algorithm can be interpreted as an affine scaling algorithm in the primal-dual setup. </jats:p>
収録刊行物
-
- Mathematics of Operations Research
-
Mathematics of Operations Research 15 (2), 191-214, 1990-05
Institute for Operations Research and the Management Sciences (INFORMS)