Solving convex programs by random walks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving convex programs by random walks

Full text

Pdf (287 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 2B table of contents

Pages: 109 - 115

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Dimitris Bertsimas	MIT, Cambridge MA
Santosh Vempala	MIT, Cambridge MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 26, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.509926 What is a DOI?

ABSTRACT

In breakthrough developments about two decades ago, L. G. Khachiyan [14] showed that the Ellipsoid method solves linear programs in polynomial time, while M. Grötschel, L. Lovász and A. Schrijver [4, 5] extended this to the problem of minimizing a convex function over any convex set specified by a separation oracle. In 1996, P. M. Vaidya [21] improved the running time via a more sophisticated algorithm. We present a simple new algorithm for convex optimization based on sampling by a random walk; it also solves for a natural generalization of the problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
	2	J. Bourgain, "Random points in isotropic convex sets," Convex geometric analysis, 53--58, (MATH). Sci. Res. Inst. Publ., 34, Cambridge Univ. Press, Cambridge, 1999.
	3	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
	4	M. Grötschel, L. Lovász, and A. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1, 169--197, 1981.
	5	M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988.
	6	B. Grunbaum. "Partitions of mass-distributions and convex bodies by hyperplanes," Pacific J. (MATH). 10, 1257--1261, 1960.
	7	Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
	8	A. Kalai , S. Vempala, Efficient algorithms for universal portfolios, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.486, November 12-14, 2000
	9	R. Kannan and L. Lovász, "Faster mixing via average conductance," Proc. STOC, 1995.
	10	R. Kannan, L. Lovász and M. Simonovits. "Isoperimetric problems for convex bodies and a localization lemma," Discrete Computational Geometry 13, 541--559, 1995.
	11	Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
	12	Ravi Kannan , John Mount , Sridhar Tayur, A randomized algorithm to optimize over certain convex sets, Mathematics of Operations Research, v.20 n.3, p.529-549, Aug. 1995 [doi>10.1287/moor.20.3.529]
	13	R. M. Karp and C. H. Papadimitriou, "On linear characterization of combinatorial optimization problems," Siam J. Comp., 11, 620--632, 1982.
	14	L. G. Khachiyan, "A polynomial algorithm in linear programming," (in Russian), Doklady Akedamii Nauk SSSR, 244, 1093--1096, 1979 (English translation: Soviet (MATH)ematics Doklady, 20, 191--194, 1979).
	15	A. Yu. Levin, "On an algorithm for the minimization of convex functions," (in Russian), Doklady Akedemii Nauk SSSR, 160, 1244--1247, 1965 (English translation: Soviet (MATH)ematics Doklady, 6, 286-290, 1965).
	16	L. Lovász, "Hit-and-run mixes fast," (MATH)ematical Programming 86, 443-461, 1998.
	17	L. Lovász and M. Simonovits, "Random walks in convex bodies and an improved volume algorithm," Random Structures and Algorithms 4, 259-412, 1993.
	18	M. W. Padberg and M. R. Rao, "The Russian method for linear programming III: Bounded integer programming," Research Report 81-39, New York University, Graduate School of Business Administration, New York, 1981.
	19	A. Prekopa, "On logarithmic concave measures and functions," Acta Sci. (MATH). Szeged}, 34, 335--343, 1973.
	20	M. Rudelson, "Random vectors in the isotropic position," J. Funct. Anal. 164, 60--72, 1999.
	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 (MATH)ematical programming problems", (in Russian), Ekonomika i Matematicheskie Metody 12, 128--142, 1976 (English translation: Matekon 13, 2, 3-45, 1976).

CITED BY 4

	John Dunagan , Santosh Vempala, A simple polynomial-time rescaling algorithm for solving linear programs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Jason H. Cantarella , Erik D. Demaine , Hayley N. Iben , James F. O'Brien, An energy-driven approach to linkage unfolding, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Klaus Brinker, Active learning of label ranking functions, Proceedings of the twenty-first international conference on Machine learning, p.17, July 04-08, 2004, Banff, Alberta, Canada
	Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia