On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method.(English)Zbl 0624.90062
The barrier function method is applied to linear programming problems using a projected Newton search direction for the solution of subproblems. The relationship between the presented algorithm and Karamarkar’s projective method is discussed. It turns out that if both of these methods are applied to the same problem using the same initial point, then by using special parameter values in the barrier method one can achieve that the iterates are identical.
Algorithmic details are outlined and the performance on a standard as well as a degenerate test set is summarized. Conclusions pro and contra the barrier method are also discussed.
Algorithmic details are outlined and the performance on a standard as well as a degenerate test set is summarized. Conclusions pro and contra the barrier method are also discussed.
Reviewer: B.Strazicky
Cite
Full Text:DOI
References:
| [1] | M. Benichou, J.M. Gauthier, G. Hentges and G. Ribière, ”The efficient solution of large-scale linear programming problems–some algorithmic techniques and computational results,”Mathematical Programming. 13 (1977) 280–322. ·Zbl 0384.90084 ·doi:10.1007/BF01584344 |
| [2] | J.L. Bentley,Writing Efficient Programs (Prentice-Hall, Englewood Cliffs, NJ, 1982). ·Zbl 0517.68013 |
| [3] | R.P. Brent,Algorithms for Minimization without Derivatives (Prentice-Hall, Englewood Cliffs, NJ, 1973). ·Zbl 0245.65032 |
| [4] | G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963). |
| [5] | J.J. Dongarra and E. Grosse, ”Distribution of mathematical software via electronic mail,”SIGNUM Newsletter 20 (1985) 45–47. ·doi:10.1145/1057947.1057951 |
| [6] | I.S. Duff and J.K. Reid, ”MA27–a set of Fortran subroutines for solving sparse symmetric sets of linear equations,” Report AERE R-10533, Computer Science and Systems Division, AERE Harwell, (Harwell, England, 1982). |
| [7] | I.S. Duff and J.K. Reid, ”The multifrontal solution of indefinite sparse symmetric linear equations,”ACM Transactions on Mathematical Software 9 (1983) 302–325. ·Zbl 0515.65022 ·doi:10.1145/356044.356047 |
| [8] | S.C. Eisenstat, M.C. Gursky, M.H. Schultz and A.H. Sherman, ”Yale sparse matrix package I: The symmetric codes,”International Journal of Numerical Methods in Engineering 18 (1982) 1145–1151. ·Zbl 0492.65012 ·doi:10.1002/nme.1620180804 |
| [9] | J. Eriksson, ”A note on solution of large sparse maximum entropy problems with linear equality constraints,”Mathematical Programming 18 (1980) 146–154. ·Zbl 0431.90068 ·doi:10.1007/BF01588310 |
| [10] | J. Eriksson, ”Algorithms for entropy and mathematical programming,” Ph.D. Thesis, Linköping University, (Linköping, Sweden, 1981). ·Zbl 0464.62027 |
| [11] | J. Eriksson, ”An iterative primal-dual algorithm, for linear programming,” Report LiTH-MAT-R-1985-10, Department of Mathematics, Linköping University (Linköping, Sweden, 1985). |
| [12] | S. Erlander, ”Entropy in linear programs–an approach to planning,” Report LiTH-MAT-R-77-3, Department of Mathematics, Linköping University (Linköping, Sweden, 1977). |
| [13] | A.V. Fiacco, ”Barrier methods for nonlinear programming,” in: A. Holzman, ed.,Operations Research Support Methodology (Marcel Dekker, New York, NY, 1979) pp. 377–440. |
| [14] | A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (John Wiley and Sons, New York, 1968). ·Zbl 0193.18805 |
| [15] | R. Fletcher,Practical Methods of Optimization, Volume 2 (John Wiley and Sons, Chichester, 1981). ·Zbl 0474.65043 |
| [16] | R. Fletcher and A.P. McCann, ”Acceleration techniques for nonlinear programming,” in: R. Fletcher, ed.,Optimization (Academic Press, London, 1969) pp. 203–213. ·Zbl 0194.47704 |
| [17] | R. Fourer, ”Solving staircase linear programs by the simplex method, 1: Inversion,”Mathematical Programming 23 (1982) 274–313. ·Zbl 0487.90076 ·doi:10.1007/BF01583795 |
| [18] | K.R. Frisch, ”The logarithmic potential method of convex programming,” University Institute of Economics (Oslo, Norway, 1955). |
| [19] | K.R. Frisch, ”Linear dependencies and a mechanized form of the multiplex method for linear programming,” University Institute of Economics (Oslo, Norway, 1957). ·Zbl 0084.15803 |
| [20] | O. Garcia, ”FOLPI, a forestry-oriented linear programming interpreter,” Reprint 1728, New Zealand Forest Service (Christchurch, New Zealand, 1984). |
| [21] | D.M. Gay, ”Solving sparse least-squares problems,” Presentation, Department of Operations Research, Stanford University (Stanford, CA, 1985). |
| [22] | J.A. George and J.W.H. Liu,Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, NJ, 1981). ·Zbl 0516.65010 |
| [23] | J.A. George and E. Ng, ”A new release of SPARSPAK–the Waterloo sparse matrix package,”SIGNUM Newsletter 19 (1984) 9–13. ·doi:10.1145/1057931.1057933 |
| [24] | P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”Sparse matrix methods in optimization,”SIAM Journal on Scientific and Statistical Computing 5 (1984) 562–589. ·Zbl 0559.65042 ·doi:10.1137/0905041 |
| [25] | P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”A note on nonlinear approaches to linear programming,” Report SOL 86-7, Department of Operations Research, Stanford University (Stanford, CA, 1986a). ·Zbl 0624.90062 |
| [26] | P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”Maintaining LU factors of a general sparse matrix,” Report SOL 86-8, Department of Operations Research, Stanford University (Stanford, CA, 1986b). [To appear inLinear Algebra and its Applications.] ·Zbl 0618.65019 |
| [27] | P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London, 1981). |
| [28] | M.T. Heath, ”Numerical methods for large sparse linear least squares problems,”SIAM Journal on Scientific and Statistical Computing 5 (1984) 497–513. ·Zbl 0575.65030 ·doi:10.1137/0905037 |
| [29] | J.K. Ho and E. Loute, ”A set of staircase linear programming test problems,”Mathematical Programming 20 (1981) 245–250. ·Zbl 0448.90036 ·doi:10.1007/BF01589349 |
| [30] | A.J. Hoffman, M. Mannos, D. Sokolowsky, and N. Wiegmann, ”Computational experience in solving linear programs,”Journal of the Society for Industrial and Applied Mathematics 1 (1953) 17–33. ·Zbl 0053.41805 ·doi:10.1137/0101002 |
| [31] | P. Huard, ”Resolution of mathematical programming with nonlinear constraints by the method of centres,” in: J. Abadie, ed.,Nonlinear Programming (North-Holland, Amsterdam, 1967) pp. 207–219. ·Zbl 0157.49701 |
| [32] | K. Jittorntrum,Sequential Algorithms in Nonlinear Programming, Ph.D. Thesis, Australian National University (Canberra, Australia, 1978). ·Zbl 0403.65026 |
| [33] | K. Jittorntrum and M.R. Osborne, ”Trajectory analysis and extrapolation in barrier function methods,”Journal of Australian Mathematical Society Series B 20 (1978) 352–369. ·Zbl 0403.65026 ·doi:10.1017/S0334270000001715 |
| [34] | N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Proceedings of the 16th Annual ACM Symposium on the Theory of Computing (1984a) 302–311. ·Zbl 0557.90065 |
| [35] | N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984b) 373–395. ·Zbl 0557.90065 ·doi:10.1007/BF02579150 |
| [36] | L.G. Khachiyan, ”A polynomial algorithm in linear programming,”Doklady Akademiia Nauk SSSR Novaia Seriia 244 (1979) 1093–1096. [English translation inSoviet Mathematics Doklady 20 (1979) 191–194.] ·Zbl 0414.90086 |
| [37] | J.W.H. Liu, ”Modification of the minimum-degree algorithm by multiple elimination,”ACM Transactions on Mathematical Software 11 (1985) 141–153. ·Zbl 0568.65015 ·doi:10.1145/214392.214398 |
| [38] | I.J. Lustig, ”A practical approach to karmarkar’s algorithm,” Report SOL 85-5, Department of Operations Research, Stanford University (Stanford, CA, 1985). |
| [39] | R. Mifflin, ”On the convergence of the logarithmic barrier function method,” in: F. Lootsma, ed.,Numerical Methods for Non-Linear Optimization (Academic Press, London, 1972) pp. 367–369. ·Zbl 0268.90060 |
| [40] | R. Mifflin, ”Convergence bounds for nonlinear programming algorithms,”Mathematical Programming 8 (1975) 251–271. ·Zbl 0326.90055 ·doi:10.1007/BF01580447 |
| [41] | C.B. Moler, Private communication (1985). |
| [42] | W. Murray and M.H. Wright, ”Efficient linear search algorithms for the logarithmic barrier function,” Report SOL 76-18, Department of Operations Research, Stanford University (Stanford, CA, 1976). |
| [43] | B.A. Murtagh and M.A. Saunders, ”MINOS 5.0 user’s guide,” Report SOL 83-20, Department of Operations Research, Stanford University (Stanford, CA, 1983). |
| [44] | J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, NY, 1970). ·Zbl 0241.65046 |
| [45] | C.C. Paige and M.A. Saunders, ”LSQR: An algorithm for sparse linear equations and sparse least-squares,”ACM Transactions on Mathematical Software 8 (1982a) 43–71. ·Zbl 0478.65016 ·doi:10.1145/355984.355989 |
| [46] | C.C. Paige and M.A. Saunders, ”Algorithm 583. LSQR: Sparse linear equations and least squares problems,”ACM Transactions on Mathematical Software 8 (1982b) 195–209. ·doi:10.1145/355993.356000 |
| [47] | M.J. Todd and B.P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,” Report 648, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1985). ·Zbl 0621.90048 |
| [48] | J.A. Tomlin, ”An experimental approach to Karmarkar’s projective method for linear programming,” Manuscript, Ketron Inc. (Mountain, View, CA, 1985). [To appear inMathematical Programming Studies.] ·Zbl 0634.90044 |
| [49] | J.A. Tomlin and J.S. Welch, ”Formal optimization of some reduced linear programming problems,”Mathematical Programming 27 (1983) 232–240. ·Zbl 0535.90059 ·doi:10.1007/BF02591947 |
| [50] | C.B. Tompkins, ”Projection methods in calculation,” in: H.A. Antosiewicz, ed.,Proceedings of the Second Symposium in Linear Programming (United States Air Force, Washington, DC, 1955) pp. 425–448. |
| [51] | C.B. Tompkins, ”Some methods of computational attack on programming problems, other than the simplex method,”Naval Research Logistics Quarterly 4 (1957) 95–96. ·doi:10.1002/nav.3800040116 |
| [52] | R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”A modification of Karmarkar’s linear programming algorithm,” Manuscript, AT&T Bell Laboratories (Holmdel, NJ, 1985). ·Zbl 0626.90056 |
| [53] | J. von Neumann, ”On a maximization problem,” Manuscript, Institute for Advanced Study (Princeton, NJ, 1947). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
