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 条
  • [41] Dynamical properties of random walks
    Messaoudi, Ali
    Valle, Glauco
    STOCHASTICS AND DYNAMICS, 2019, 19 (03)
  • [42] Deterministic walks in random environments
    Bunimovich, LA
    PHYSICA D-NONLINEAR PHENOMENA, 2004, 187 (1-4) : 20 - 29
  • [43] RANDOM WALKS AND CHEMICAL NETWORKS
    Malyshev, V. A.
    Pirogov, S. A.
    Rybko, A. N.
    MOSCOW MATHEMATICAL JOURNAL, 2004, 4 (02) : 441 - 453
  • [44] Random walks on spatial networks
    Dou Fei-Ling
    Hu Yan-Qing
    Li Yong
    Fan Ying
    Di Zeng-Ru
    ACTA PHYSICA SINICA, 2012, 61 (17)
  • [45] Lamplighter Random Walks on Fractals
    Takashi Kumagai
    Chikara Nakamura
    Journal of Theoretical Probability, 2018, 31 : 68 - 92
  • [46] Random walks for image segmentation
    Grady, Leo
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2006, 28 (11) : 1768 - 1783
  • [47] Random walks on generalized lattices
    Salvatori, M
    MONATSHEFTE FUR MATHEMATIK, 1996, 121 (1-2): : 145 - 161
  • [48] Simplicial branching random walks
    Rosenthal R.
    Journal of Applied and Computational Topology, 2024, 8 (6) : 1751 - 1791
  • [49] Random walks through poetry
    Choi, Jeanne Devautour
    Boury, Samuel
    DIGITAL CREATIVITY, 2022, 33 (02) : 157 - 170
  • [50] Lamplighter Random Walks on Fractals
    Kumagai, Takashi
    Nakamura, Chikara
    JOURNAL OF THEORETICAL PROBABILITY, 2018, 31 (01) : 68 - 92
12345