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
Read More: http://epubs.siam.org/doi/abs/10.1137/130930522
| Original language | English |
|---|---|
| Pages (from-to) | 1122-1137 |
| Number of pages | 16 |
| Journal | SIAM Journal on Optimization |
| Volume | 24 |
| Issue number | 3 |
| Early online date | 5 Aug 2014 |
| DOIs | |
| Publication status | Published - 2014 |