Stochastic comparison algorithm for discrete optimization with estimation

被引：59

作者：

Gong, WB ^{[1
]}

Ho, YC

Zhai, WG

机构：

[1] Univ Massachusetts, Dept Elect & Comp Engn, Amherst, MA 01003 USA

[2] Harvard Univ, Div Appl Sci, Cambridge, MA 02138 USA

[3] Ascend Commun Inc, Westford, MA 01886 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2000年 / 10卷 / 02期

关键词：

discrete optimization; random search; time-inhomogeneous Markov chain;

D O I：

10.1137/S1052623495290684

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we study a class of discrete optimization problems, where the objective function for a given configuration can be expressed as the expectation of a random variable. In such problems, only samples of the random variables are available for the optimization process. An iterative algorithm called the stochastic comparison (SC) algorithm is developed. The convergence of the SC algorithm is established based on an examination of the quasi-stationary probabilities of a time-inhomogeneous Markov chain. We also present some numerical experiments.

引用

页码：384 / 404

页数：21

共 27 条

[21] CONVERGENCE AND FINITE-TIME BEHAVIOR OF SIMULATED ANNEALING [J].

MITRA, D ;

ROMEO, F ;

SANGIOVANNIVINCENTELLI, A .

ADVANCES IN APPLIED PROBABILITY, 1986, 18 (03) :747-771

[22]

Nelson B, 1994, P 1994 WINT SIM C

[23]

ROMEO F, 1991, ALGORITHMICA, V6, P302, DOI 10.1007/BF01759049

[24]

Rubinstein R. Y., 1986, MONTE CARLO OPTIMIZA

[25]

Santner T.J., 1984, DESIGN EXPT RANKING

[26] THEORY FOR AUTOMATIC LEARNING UNDER PARTIALLY OBSERVED MARKOV-DEPENDENT NOISE [J].

YAKOWITZ, S ;

JAYAWARDENA, T ;

LI, S .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1992, 37 (09) :1316-1324

[27] STOCHASTIC DISCRETE OPTIMIZATION [J].

YAN, D ;

MUKAI, H .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1992, 30 (03) :594-612

← 1 2 3 →