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 条
  • [21] Random walks on random simple graphs
    Hildebrand, M
    RANDOM STRUCTURES & ALGORITHMS, 1996, 8 (04) : 301 - 318
  • [22] Bootstrap random walks
    Collevecchio, Andrea
    Hamza, Kais
    Shi, Meng
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2016, 126 (06) : 1744 - 1760
  • [23] Disordered Random Walks
    Mauricio P. Pato
    Brazilian Journal of Physics, 2021, 51 : 238 - 243
  • [24] Collisions of random walks
    Barlow, Martin T.
    Peres, Yuval
    Sousi, Perla
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2012, 48 (04): : 922 - 946
  • [25] Random Walks, Bisections and Gossiping in Circulant Graphs
    Mans, Bernard
    Shparlinski, Igor
    ALGORITHMICA, 2014, 70 (02) : 301 - 325
  • [26] Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks
    Zakhar Kabluchko
    Alexander Marynych
    Probability Theory and Related Fields, 2022, 184 : 969 - 1028
  • [27] Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks
    Kabluchko, Zakhar
    Marynych, Alexander
    PROBABILITY THEORY AND RELATED FIELDS, 2022, 184 (3-4) : 969 - 1028
  • [28] Collisions of random walks in reversible random graphs
    Hutchcroft, Tom
    Peres, Yuval
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2015, 20 : 2 - 6
  • [29] Random random walks on the integers mod n
    Dai, JJ
    Hildebrand, MV
    STATISTICS & PROBABILITY LETTERS, 1997, 35 (04) : 371 - 379
  • [30] EINSTEIN RELATION FOR RANDOM WALKS IN RANDOM ENVIRONMENT
    Guo, Xiaoqin
    ANNALS OF PROBABILITY, 2016, 44 (01) : 324 - 359
12345