Solving convex programs by random walks

被引：133

作者：

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 [J].