Solving convex programs by random walks

被引：127

作者：

Bertsimas, D

Vempala, S

机构：

[1] MIT, Sloan Sch Management, Cambridge, MA 02139 USA

[2] MIT, Ctr Operat Res, Cambridge, MA 02139 USA

[3] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

JOURNAL OF THE ACM | 2004年 / 51卷 / 04期

关键词：

convex programs; random walks; polynomial time; algorithms; theory;

D O I：

10.1145/1008731.1008733

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：540 / 556

页数：17

共 23 条

[1] [Anonymous], P 31 ANN ACM S THEOR
[2] Bertsimas D., 1997, Introduction to linear optimization
[3] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES
DYER, M
FRIEZE, A
KANNAN, R
[J]. JOURNAL OF THE ACM, 1991, 38 (01) : 1 - 17
[4] The Brunn-Minkowski inequality
Gardner, RJ
[J]. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2002, 39 (03) : 355 - 405
[5] THE ELLIPSOID METHOD AND ITS CONSEQUENCES IN COMBINATORIAL OPTIMIZATION
GROTSCHEL, M
LOVASZ, L
SCHRIJVER, A
[J]. COMBINATORICA, 1981, 1 (02) : 169 - 197
[6] Grotschel M, 2012, Geometric algorithms and combinatorial optimization, V2
[7] Grunbaum B., 1960, Pacific J. Math, V10, P1257, DOI [10.2140/pjm.1960.10.1257, DOI 10.2140/PJM.1960.10.1257]
[8] Jerrum M., 2001, P 33 ANN ACM S THEOR, P712
[9] Kalai A., 2002, J MACH LEARN RES, V3, P423
[10] Kannan R, 1997, RANDOM STRUCT ALGOR, V11, P1, DOI 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO

← 1 2 3 →