A new finite continuation algorithm for linear programming

Date
1996
Authors
Madsen, K.
Nielsen, H. B.
Pınar, M. Ç.
Editor(s)
Advisor
Supervisor
Co-Advisor
Co-Supervisor
Instructor
Source Title
SIAM Journal on Optimization
Print ISSN
1052-6234
Electronic ISSN
1095-7189
Publisher
Society for Industrial and Applied Mathematics
Volume
6
Issue
3
Pages
600 - 616
Language
English
Journal Title
Journal ISSN
Volume Title
Series
Abstract

We describe a new finite continuation algorithm for linear programming. The dual of the linear programming problem with unit lower and upper bounds is formulated as an f\ minimization problem augmented with the addition of a linear term. This nondifferentiable problem is approximated by a smooth problem. It is shown that the minimizers of the smooth problem define a family of piecewise-linear paths as a function of a smoothing parameter. Based on this property, a finite algorithm that traces these paths to arrive at an optimal solution of the linear program is developed. The smooth problems are solved by a Newton-type algorithm. Preliminary numerical results indicate that the new algorithm is promising.

Course
Other identifiers
Book Title
Citation
Published Version (Please cite this version)