Paper Info
Title
On Long Step Path Following and SUMT for Linear and Quadratic Programming
Abstract
We consider a long step barrier algorithm for the minimization of a convex quadratic objective subject to linear inequality constraints. The algorithm is a dual version of a method developed by Anstreicher et al. [Algorithmica, 10 (1993), pp. 365-382], and requires O(nL) or O(root nL) iterations to solve a problem with n constraints, depending on how the barrier parameter is reduced. As a corollary of our analysis we demonstrate that the classical SUMT algorithm, exactly as implemented in 1968, solves linear and quadratic programs in O(root nL log L) iterations, with proper initialization and choice of parameters.
Year
DOI
Venue
1996
10.1137/0806003
SIAM JOURNAL ON OPTIMIZATION
Keywords
DocType
Volume
linear programming,quadratic programming,barrier function,long step path following,sequential unconstrained minimization technique
Journal
6
Issue
ISSN
Citations 
1
1052-6234
3
PageRank 
References 
Authors
0.47
1
1
Name
Order
Citations
PageRank
Kurt M. Anstreicher163386.40