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

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

**ABSTRACT**

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(*N*^{1/2} * (1+(1/*R*))) * *L*^{(1+(1/R))}
) iterations and O(*N*^{3} + *N*^{2} * *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.

Go back

Mauricio G.C. Resende's Home PageLast modified: 11