On degeneracy in linear programming and related problems |
| |
| Authors: | George Karen Osborne M R |
| |
| Institution: | (1) School of Information Sciences, University of Canberra, Canberra, Australia;(2) Mathematical Sciences School, Australian National University, Australia |
| |
| Abstract: | Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are reported. These are obtained using a careful implementation of the projected gradient algorithm 11]. These are compared with results obtained using a steepest descent approach which can be implemented by means of a closely related projected gradient method, and which is not affected by degeneracy in principle. However, the problem of correctly identifying degenerate active sets occurs with both algorithms. The numerical results favour the more standard projected gradient procedure which resolves the degeneracy explicitly. Extension of both methods to general polyhedral convex function minimization problems is sketched. |
| |
| Keywords: | Recursive resolution projected gradient algorithm steepest descent method generating model problems l
1 estimation minimizing polyhedral convex functions |
| 本文献已被 SpringerLink 等数据库收录！ |
|
