A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power  series extension

Renato D.C. Monteiro, Ilan Adler, and Mauricio G.C. Resende

Mathematics of Operations Research, vol. 15, pp. 191-214, 1990


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 greater or equal to 1 is the order of approximation used, we show that our algorithm has time complexity O(N1/2 * (1+(1/R))) * L(1+(1/R)) ) iterations and O(N3 + N2 * 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.

PDF file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 11 April 2007

Copyright Notice