×

zbMATH — the first resource for mathematics

A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. (English) Zbl 0714.90060
The authors present a primal-dual path following algorithm for solving linear and convex quadratic programming problems based on the logarithmic barrier function approach [A. V. Fiacco and 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.
Reviewer: J.Parida

MSC:
90C05 Linear programming
90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C25 Convex programming
90C60 Abstract computational complexity for mathematical programming problems
Citations:
Zbl 0193.188
PDF BibTeX XML Cite
Full Text: DOI Link