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
相关论文
共 50 条
  • [1] CONVEX HULLS OF RANDOM-WALKS
    SNYDER, TL
    STEELE, JM
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1993, 117 (04) : 1165 - 1173
  • [2] CONVEX MINORANTS OF RANDOM WALKS AND LEVY PROCESSES
    Abramson, Josh
    Pitman, Jim
    Ross, Nathan
    Uribe Bravo, Geronimo
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2011, 16 : 423 - 434
  • [3] Distributed Random Walks
    Das Sarma, Atish
    Nanongkai, Danupon
    Pandurangan, Gopal
    Tetali, Prasad
    JOURNAL OF THE ACM, 2013, 60 (01)
  • [4] Random Walks On Finite Convex Sets Of Lattice Points
    Balint Virag
    Journal of Theoretical Probability, 1998, 11 : 935 - 951
  • [5] Random walks on finite convex sets of lattice points
    Virág, B
    JOURNAL OF THEORETICAL PROBABILITY, 1998, 11 (04) : 935 - 951
  • [6] Solving Electrical Networks to incorporate Supervision in Random Walks
    Sachan, Mrinmaya
    Hovy, Dirk
    Hovy, Eduard
    PROCEEDINGS OF THE 22ND INTERNATIONAL CONFERENCE ON WORLD WIDE WEB (WWW'13 COMPANION), 2013, : 109 - 110
  • [7] CoBRa: convex hull based random walks for salient object detection
    Singh, Vivek Kumar
    Kumar, Nitin
    MULTIMEDIA TOOLS AND APPLICATIONS, 2022, 81 (21) : 30283 - 30303
  • [8] CoBRa: convex hull based random walks for salient object detection
    Vivek Kumar Singh
    Nitin Kumar
    Multimedia Tools and Applications, 2022, 81 : 30283 - 30303
  • [9] SOLVING QUADRATIC MATRIX EQUATIONS ARISING IN RANDOM WALKS IN THE QUARTER PLANE
    Bini, Dario A.
    Meini, Beatrice
    Meng, Jie
    SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2020, 41 (02) : 691 - 714
  • [10] Distributed Computation of Sparse Cuts via Random Walks
    Das Sarma, Atish
    Molla, Anisur Rahaman
    Pandurangan, Gopal
    PROCEEDINGS OF THE 16TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, 2015,
12345