A Newton method for linear programming. (English) Zbl 1140.90467
Summary: A fast Newton method is proposed for solving linear programs with a very large \((\approx 10^6)\) number of constraints and a moderate \((\approx 10^2)\) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if m[ge]n and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.
MSC:
| 90C05 | Linear programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C53 | Methods of quasi-Newton type |
References:
| [1] | MANGASARIAN, O. L., A Finite Newton Method for Classification Problems, Report 01–11, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 2001; see also Optimization Methods and Software, Vol. 17, 913–929, 2002 and ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/01–11.ps. · Zbl 1065.90078 |
| [2] | FUNG, G., and MANGASARIAN, O. L., Finite Newton Method for Lagrangian Support Vector Machine Classification, Report 02–01, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 2002; see also Neurocomputing, Vol. 55, 39–55, 2003, and ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/02–01.ps. |
| [3] | MANGASARIAN, O. L., Normal Solutions of Linear Programs, Mathematical Programming Study, Vol. 22, 206–216, 1984. · Zbl 0588.90058 · doi:10.1007/BFb0121017 |
| [4] | MANGASARIAN, O. L., and DE LEONE, R., Error Bounds for Strongly Convex Programs and (Super) Linearly Convergent Iterative Schemes for the Least 2-Norm Solution of Linear Programs, Applied Mathematics and Optimization, Vol. 17, 1–14, 1988. · Zbl 0645.90062 · doi:10.1007/BF01448356 |
| [5] | MANGASARIAN, O. L., and MEYER, R. R., Nonlinear Perturbation of Linear Programs, SIAM Journal on Control and Optimization, Vol. 17, 745–752, 1979. · Zbl 0432.90047 · doi:10.1137/0317052 |
| [6] | GOLIKOV, A. I., and EVTUSHENKO, Y. G., Search for Normal Solutions in Linear Programming, Computational Mathematics and Mathematical Physics, Vol. 14, 1694–1714, 2000. · Zbl 1030.90052 |
| [7] | KANZOW, C., QI, H., and QI, L., On the Minimum Norm Solution of Linear Programs, Preprint, University of Hamburg, Hamburg, Germany, 2001; see also Journal of Optimization Theory and Applications (to appear) and http://www.math.uni-hamburg.de/home/kanzow/paper.html. · Zbl 1043.90046 |
| [8] | CPLEX Optimization, Incline Village, Nevada, Using the CPLEX(TM) Linear Optimizer and CPLEX(TM) Mixed Integer Optimizer (Version 2.0), 1992. |
| [9] | CLARKSON, K. L., Las Vegas Algorithms for Linear and Integer Programming, Journal of the Association for Computing Machinery, Vol. 42, 488–499, 1995. · Zbl 0885.65063 · doi:10.1145/201019.201036 |
| [10] | KRISHNAN, K., and MITCHELL, J., A Linear Programming Approach to Semidefinite Programming Problems, Working Paper, Rensselaer Polytechnic Institute, Troy, NY, 2001. |
| [11] | PINAR, M. C., Piecewise-Linear Pathways to Optimal Solution Set in Linear Programming, Journal of Optimization Theory and Applications, Vol. 93, 619–634, 1997. · Zbl 0873.90066 · doi:10.1023/A:1022651331550 |
| [12] | HIRIART-URRUTY, J. B., STRODIOT, J. J., and NGUYEN, V. H., Generalized Hessian Matrix and Second-Order Optimality Conditions for Problems with C L1 Data, Applied Mathematics and Optimization, Vol. 11, 43–56, 1984. · Zbl 0542.49011 · doi:10.1007/BF01442169 |
| [13] | FACCHINEI, F., Minimization of SC 1 Functions and the Maratos Effect, Operations Research Letters, Vol. 17, 131–137, 1995. · Zbl 0843.90108 · doi:10.1016/0167-6377(94)00059-F |
| [14] | SMITH, P. W., and WOLKOWICZ, H., A Nonlinear Equation for Linear Programming, Mathematical Programming, Vol. 34, 235–238, 1986. · Zbl 0593.90049 · doi:10.1007/BF01580588 |
| [15] | FIACCO, A. V., and MCCORMICK, G. P., Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, NY, 1968. · Zbl 0193.18805 |
| [16] | BERTSEKAS, D. P., Nonlinear Programming, 2nd Edition, Athena Scientific, Belmont, Massachusetts, 1999. |
| [17] | MANGASARIAN, O. L., Parallel Gradient Distribution in Unconstrained Optimization, SIAM Journal on Control and Optimization, Vol. 33, 1916–1925, 1995; see also ftp://ftp.cs.wisc.edu/tech-reports/reports/1993/tr1145.ps. · Zbl 0843.90111 · doi:10.1137/S0363012993250220 |
| [18] | ARMIJO, L., Minimization of Functions Having Lipschitz-Continuous First Partial Derivatives, Pacific Journal of Mathematics, Vol. 16, 1–3, 1966. · Zbl 0202.46105 · doi:10.2140/pjm.1966.16.1 |
| [19] | LEE, Y. J., and MANGASARIAN, O. L., SSVM: A Smooth Support Vector Machine, Computational Optimization and Applications, Vol. 20, 5–22, 2001; see also Report 99–03, Data Mining Institute, University of Wisconsin, 1999 and ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/99–03.ps. |
| [20] | LUCIDI, S., A New Result in the Theory and Computation of the Least-Norm Solution of a Linear Program, Journal of Optimization Theory and Applications, Vol. 55, 103–117, 1987. · Zbl 0622.90053 · doi:10.1007/BF00939047 |
| [21] | MANGASARIAN, O. L., Nonlinear Programming, SIAM, Philadelphia, Pennsylvania, 1994. |
| [22] | MURPHY, P. M., and AHA, D. W., UCI Machine Learning Repository, 1992; see also www.ics.uci.edu/\(\sim\)mlearn/MLRepository.html. |
| [23] | ODEWAHN, S., STOCKWELL, E., PENNINGTON, R., HUMPHREYS, R., and ZUMACH, W., Automated Star/Galaxy Discrimination with Neural Networks, Astronomical Journal, Vol. 103, 318–331, 1992. · doi:10.1086/116063 |
| [24] | MANGASARIAN, O. L., Generalized Support Vector Machines, Advances in Large Margin Classifiers, Edited by A. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, MIT Press, Cambridge, Massachusetts, 135–146, 2000; see also ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98–14.ps. |
| [25] | CRISTIANINI, N., and SHAWE-TAYLOR, J., An Introduction to Support Vector Machines, Cambridge University Press, Cambridge, Massachusetts, 2000. · Zbl 0994.68074 |
| [26] | SMOLA, A., and SCHÖLKOPF, B., Learning with Kernels, MIT Press, Cambridge, Massachusetts, 2002. · Zbl 1019.68094 |
| [27] | VAPNIK, V. N., The Nature of Statistical Learning Theory, 2nd Edition, Springer, New York, NY, 2000. · Zbl 0934.62009 |
| [28] | BRADLEY, P. S., and MANGASARIAN, O. L., Feature Selection via Concave Minimization and Support Vector Machines, Machine Learning, Proceedings of the 15th International Conference (ICML ’98), Edited by J. Shavlik, and M. Kaufmann, San Francisco, California, 82–90, 1998; see also ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98–03.ps. |
| [29] | MANGASARIAN, O. L., Arbitrary-Norm Separating Plane, Operations Research Letters, Vol. 24, 15–23, 1999; see also ftp://ftp.cs.wisc.edu/math-prog/tech-reports/97–07r.ps. · Zbl 1028.90037 · doi:10.1016/S0167-6377(98)00049-2 |
| [30] | JOACHIMS, T., Making Large-Scale Support Vector Machine Learning Practical, Advances in Kernel Methods -; Support Vector Learning, Edited by B. Schölkopf, C. J. C. Burges, and A. J. Smola, MIT Press, Cambridge, Massachusetts, 169–184, 1999. |
| [31] | MANGASARIAN, O. L., and MUSICANT, D. R., Lagrangian Support Vector Machines, Journal of Machine Learning Research, Vol. 1, 161–177, 2001; see also ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00–06.ps. · Zbl 0997.68108 |
| [32] | FUNG, G., and MANGASARIAN, O. L., A Feature Selection Newton Method for Support Vector Machine Classification, Report 02–03, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 2002; see also Computational Optimization and Applications (to appear) and ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/02–03.ps. |
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.
