Journal article
On Long Step Path Following and SUMT for Linear and Quadratic Programming
SIAM journal on optimization, Vol.6(1), pp.33-46
02/01/1996
DOI: 10.1137/0806003
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( \sqrt{n} L )$ 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( \sqrt{n} L\log L )$ iterations, with proper initialization and choice of parameters.
Details
- Title: Subtitle
- On Long Step Path Following and SUMT for Linear and Quadratic Programming
- Creators
- Kurt M Anstreicher
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.6(1), pp.33-46
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/0806003
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 02/01/1996
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380421502771
Metrics
7 Record Views