Advanced Search

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
90C20 Quadratic 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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]