On Wolfe's Method for Resolving Degeneracy in Linearly Constrained Optimization

Roger Fletcher (Lead / Corresponding author)

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Wolfe [J. Soc. Indust. Appl. Math., 11 (1963), pp. 205--211] describes a novel and very useful method for resolving degeneracy in the Simplex method for Linear Programming (LP). The simplicity and reliability of the method makes it an excellent choice in this author's opinion. The method is described here in the context of an active set method (ASM) format for LP. The method solves recursively generated subproblems that are smaller than the original, which contributes to efficiency. Data structures are described that enable the recursive aspect of the method to be implemented very easily with minimal storage overhead. The method is extended to solve a general form of linearly constrained optimization problem that includes quadratic programming (QP) and allows simple bounds on the variables and both equation and inequality general linear constraints. Issues of round-off error are discussed and heuristics are described that have proved to be very reliable in practice. The method is further extended to QP problems in which general linear constraints are handled as $L_1$ terms in the objective function.


Read More: http://epubs.siam.org/doi/abs/10.1137/130930522
Original languageEnglish
Pages (from-to)1122-1137
Number of pages16
JournalSIAM Journal on Optimization
Volume24
Issue number3
Early online date5 Aug 2014
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'On Wolfe's Method for Resolving Degeneracy in Linearly Constrained Optimization'. Together they form a unique fingerprint.

  • Cite this