Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0714.90060
Monteiro, Renato D.C.; Adler, Ilan; Resende, Maricio G.C.
A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension.
(English)
[J] Math. Oper. Res. 15, No.2, 191-214 (1990). ISSN 1526-5471; ISSN 0364-765X/e

The authors present a primal-dual path following algorithm for solving linear and convex quadratic programming problems based on the logarithmic barrier function approach [{\it A. V. Fiacco} and {\it G. P. McCormick}, Nonlinear programming: sequential unconstrained minimization techniques'' (1968; Zbl 0193.188)]. The present algorithm uses power series approximation of the path of solutions for the weighted barrier function family of problems associated with the given programming problem. They study the convergence properties of the algorithm and show that the complexity of the number of iterations depends on the order of approximation, say r. They also discuss the particular cases when $r=1$ and $r\to \infty$ and compare the convergence properties of the algorithm in these particular cases with those of some known polynomial-time primal-dual path following algorithms. No computational results for the algorithm are given.
[J.Parida]
MSC 2000:
*90C05 Linear programming
90-08 Computational methods (optimization)
90C25 Convex programming
90C60 Abstract computational complexity for math. programming problems

Keywords: power series approximation; primal-dual path following algorithm; logarithmic barrier function approach; convergence properties

Citations: Zbl 0193.188

Cited in: Zbl 0911.90252 Zbl 0719.90044

Highlights
Master Server