A simple polynomial-time rescaling algorithm for solving linear programs

ABSTRACT

The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function. ). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.

REFERENCES

• 1: S. Agmon, The relaxation method for linear inequalities, Canadian J. of Math., 6(3), 382--392, 1954.
• 2: Dimitris Bertsimas , Santosh Vempala, Solving convex programs by random walks, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509926]
• 3: Avrim Blum , John Dunagan, Smoothed analysis of the perceptron algorithm for linear programming, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.905-914, January 06-08, 2002, San Francisco, California
• 4: A. Blum, A. Frieze, R. Kannan, and S. Vempala, A polynomial-time algorithm for learning noisy linear threshold functions, Algorithmica, 22(1), 35--52, 1998.
• 5: Tom Bylander, Learning linear threshold functions in the presence of classification noise, Proceedings of the seventh annual conference on Computational learning theory, p.340-347, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181176]
• 6: E. Cohen, Learning noisy perceptrons by a perceptron in polynomial time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.514, October 19-22, 1997
• 7: F. Cucker and D. Cheung, A new condition number for linear programming, Mathematical Programming, Series A, 91(1), 163--174, 2001.
• 8: V. Chvatal, Linear Programming, W. H. Freeman, 1983.
• 9: J. Dunagan, S. Teng, and D. A. Spielman, Smoothed Analysis of Renegar's Condition Number for Linear Programming, SIAM Conference on Optimization, 2002.
• 10: R. M. Freund and S. Mizuno: "Interior Point Methods: Current Status and Future Directions," in High Performance Optimization, H. Frenk et al. (eds. ), Kluwer Academic Publishers, pp. 441-466, 2000.
• 11: R. M. Freund and J. R. Vera, Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system, Math. Programming, 86, 225--260, 1999.
• 12: Jurgen Forster, A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity, Proceedings of the 16th Annual Conference on Computational Complexity, p.100, June 18-21, 2001
• 13: L. Grotchel, L. Lovasz, and A. Schrijver, Geometric algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.
• 14: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 15: L. G. Khachiyan, A polynomial algorithm in linear programming, (in Russian), Doklady Akedamii Nauk SSSR, 244, 1093--1096, 1979 (English translation: Soviet Mathematics Doklady, 20, 191--194, 1979).
• 16: Perceptrons: An Introduction to Computational Geometry, The MIT Press, 1969
• 17: J. Renegar, Incorporating condition measures into the complexity theory of linear programming, SIAM Journal on Optimization, 5(3), 506--524, 1995.
• 18: F. Rosenblatt, Principles of Neurodynamics, Spartan Books, 1962.
• 19: Rocco A. Servedio, Perceptron, Winnow, and PAC Learning, SIAM Journal on Computing, v.31 n.5, p.1358-1369, 2002 [doi>10.1137/S0097539798340928]
• 20: Rocco A. Servedio, Smooth Boosting and Learning with Malicious Noise, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.473-489, July 16-19, 2001
• 21: Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Mathematical Programming: Series A and B, v.73 n.3, p.291-341, June 30, 1996 [doi>10.1007/BF02592216]
• 22: D. B. Yudin and A. S. Nemirovski, Evaluation of the information complexity of mathematical programming problems, (in Russian), Ekonomika i Matematicheskie Metody 12, 128--142, 1976 (English translation: Matekon 13, 2, 3--45, 1976).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
linear programming, perceptron, polynomial time