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 条
  • [31] Random Walks and Bisections in Random Circulant Graphs
    Mans, Bernard
    Shparlinski, Igor E.
    LATIN 2012: THEORETICAL INFORMATICS, 2012, 7256 : 542 - 555
  • [32] On the speed of Random Walks among Random Conductances
    Berger, Noam
    Salvi, Michele
    ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 2013, 10 (02): : 1063 - 1083
  • [33] Collisions of random walks in dynamic random environments
    Halberstam, Noah
    Hutchcroft, Tom
    ELECTRONIC JOURNAL OF PROBABILITY, 2022, 27
  • [34] MULTIPLE RANDOM WALKS IN RANDOM REGULAR GRAPHS
    Cooper, Colin
    Frieze, Alan
    Radzik, Tomasz
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) : 1738 - 1761
  • [35] Random walks on a fractal solid
    Kozak, JJ
    JOURNAL OF STATISTICAL PHYSICS, 2000, 101 (1-2) : 405 - 414
  • [36] Counting trees with random walks
    Iacobelli, Giulio
    Figueiredo, Daniel R.
    Barbosa, Valmir C.
    EXPOSITIONES MATHEMATICAE, 2019, 37 (01) : 96 - 102
  • [37] Evolutionary Image Transition and Painting Using Random Walks
    Neumann, Aneta
    Alexander, Bradley
    Neumann, Frank
    EVOLUTIONARY COMPUTATION, 2020, 28 (04) : 643 - 675
  • [38] RANDOM WALKS, CONDUCTANCE, AND RESISTANCE FOR THE CONNECTION GRAPH LAPLACIAN
    Cloninger, Alexander
    Mishne, Gal
    Oslandsbotn, Andreas
    Robertson, Sawyer J.
    Wan, Zhengchao
    Wang, Yusu
    SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2024, 45 (03) : 1541 - 1572
  • [39] Return of Fibonacci random walks
    Neunhaeuserer, Joerg
    STATISTICS & PROBABILITY LETTERS, 2017, 121 : 51 - 53
  • [40] Random Walks on the Folded Hypercube
    Chen, Hong
    Li, Xiaoyan
    Lin, Cheng-Kuan
    JOURNAL OF INTERNET TECHNOLOGY, 2019, 20 (06): : 1987 - 1994
12345