Dimitris Bertsimas
Abstract
Minimizing a convex function over a convex set in n-dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It extends naturally to minimizing quasi-convex functions and to other generalizations.
- Bertsimas, D., and Tsitsiklis, J. 1997. Introduction to Linear Optimization, Athena Scientific. Google Scholar
- Dyer, M., Frieze, A., and Kannan, R. 1991. A random polynomial time algorithm for estimating the volumes of convex bodies. J. ACM 38, 1--17. Google Scholar
- Gardner, R. J. 2002. The Brunn--Minkowski inequality. Bull. AMS 39, 3, 355--405.Google Scholar
- Grötschel, M., Lovász, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.Google Scholar
- Grötschel, M., Lovász, L., and Schrijver, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.Google Scholar
- Grunbaum, B. 1960. Partitions of mass-distributions and convex bodies by hyperplanes. Pacific J. Math. 10, 1257--1261.Google Scholar
- Jerrum, M., Sinclair, A., Vigoda, E. 2001. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In Proceedings of the 33rd Annual ACM STOC. ACM, New York, 712--721. Google Scholar
- Kalai, A., and Vempala, S. 2002. Efficient algorithms for universal portfolios. J. Mach. Learn. Res. 3, 423--440. Google Scholar
- Kannan, R., and Lovász, L. 1999. Faster mixing via average conductance. In Proceedings of the 31st Annual ACM STOC. ACM, New York, 282--287. Google Scholar
- Kannan, R., Lovász, L., and Simonovits, M. 1997. Random walks and and an O*(n5) volume algorithm for convex sets. Rand. Struct. Algor. 11, 1--50. Google Scholar
- Kannan, R., Mount, J., and Tayur, S. 1995. A randomized algorithm to optimize over certain convex sets. Math. Oper. Res. 20, 3, 529--549. Google Scholar
- Karp, R. M., and Papadimitriou, C. H. 1982. On linear characterization of combinatorial optimization problems. SIAM J. Comput. 11, 620--632.Google Scholar
- Khachiyan, L. G. 1979. A polynomial algorithm in linear programming (in Russian). Doklady Aked. Nauk SSSR, 244, 1093--1096. (English translation: Soviet Mathematics Doklady, 20, 191--194, 1979.)Google Scholar
- Levin, A. Yu. 1965. On an algorithm for the minimization of convex functions (in Russian). Doklady Aked. Nauk SSSR 160, 1244--1247. (English translation: Soviet Mathematics Doklady, 6, 286--290, 1965.)Google Scholar
- Lovász, L. 1998. Hit-and-run mixes fast. Math. Prog. 86, 443--461.Google Scholar
- Lovász, L., and Simonovits, M. 1993. Random walks in convex bodies and an improved volume algorithm. Rand. Struct. Algor. 4, 259--412.Google Scholar
- Padberg, M. W., and Rao, M. R. 1981. The Russian method for linear programming. III: Bounded integer programming. Research Report 81-39, New York University, Graduate School of Business Administration, New York.Google Scholar
- Prekopa, A. 1973. On logarithmic concave measures and functions. Acta Sci. Math. Szeged 34, 335--343.Google Scholar
- Rudelson, M. 1999. Random vectors in the isotropic position. J. Funct. Anal. 164, 60--72.Google Scholar
- Schneider, R. 1993. Convex Bodies: The Brunn--Minkowski Theory. Cambridge University Press, Cambridge.Google Scholar
- Vaidya, P. M. 1996. A new algorithm for minimizing convex functions over convex sets. Math. Prog. 73, 291--341. Google Scholar
- Yudin, D. B., and Nemirovski, A. S. 1976. Evaluation of the information complexity of mathematical programming problems (in Russian). Ekonomika i Matematicheskie Metody 12, 128--142, (English translation: Matekon 13, 2, 3--45, 1976).Google Scholar
Index Terms
- Solving convex programs by random walks
Recommendations
Solving convex programs by random walks
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computingIn 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 ...
Pseudorandom generators from polarizing random walks
CCC '18: Proceedings of the 33rd Computational Complexity ConferenceWe propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1, 1]n. ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Comments