Stochastic Approximation and Recursive Algorithms and Applications (2nd ed.) [Kushner & Yin 2003-07-17].pdf

(3037 KB) Pobierz
Stochastic Mechanics
Random Media
Signal Processing and Image Synthesis
Applications of
Mathematics
Stochastic Modelling
Mathematical Economics and Finance
and Applied Probability
Stochastic Optimization
Stochastic Control
Stochastic Models in Life Sciences
35
B. Rozovskii
M. Yor
D. Dawson
D. Geman
G. Grimmett
I. Karatzas
F. Kelly
Y. Le Jan
B. Øksendal
G. Papanicolaou
E. Pardoux
Edited by
Advisory Board
Harold J. Kushner G. George Yin
Stochastic Approximation
and Recursive Algorithms
and Applications
Second Edition
With 31 Figures
Harold J. Kushner
Division of Applied Mathematics
Brown University
Providence, RI 02912, USA
Harold_Kushner@Brown.edu
Managing Editors
B. Rozovskii
Center for Applied Mathematical Sciences
Denney Research Building 308
University of Southern California
1042 West Thirty-sixth Place
Los Angeles, CA 90089, USA
rozovski@math.usc.edu
M. Yor
´
`
´
Laboratoire de Probabilites et Modeles Aleatoires
´
Universite de Paris VI
175, rue du Chevaleret
75013 Paris, France
G. George Yin
Department of Mathematics
Wayne State University
Detroit, MI 48202, USA
gyin@math.wayne.edu
Cover illustration:
Cover pattern by courtesy of Rick Durrett, Cornell University, Ithaca, New York.
Mathematics Subject Classification (2000): 62L20, 93E10, 93E25, 93E35, 65C05, 93-02, 90C15
Library of Congress Cataloging-in-Publication Data
Kushner, Harold J. (Harold Joseph), 1933–
Stochastic approximation and recursive algorithms and applications / Harold J. Kushner,
G. George Yin.
p. cm. — (Applications of mathematics ; 35)
Rev. ed. of: Stochastic approximation algorithms and applications, c1997.
ISBN 0-387-00894-2 (acid-free paper)
1. Stochastic approximation. 2. Recursive stochastic algorithms. 3. Recursive algorithms.
I. Kushner, Harold J. (Harold Joseph), 1933–. Stochastic approximation algorithms and
applications. II. Yin, George, 1954– III. Title. IV. Series.
QA274.2.K88 2003
519.2—dc21
2003045459
ISBN 0-387-00894-2
Printed on acid-free paper.
©
2003, 1997 Springer-Verlag New York, Inc.
All rights reserved. This work may not be translated or copied in whole or in part without the
written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York,
NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use
in connection with any form of information storage and retrieval, electronic adaptation, computer
software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identified as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
Printed in the United States of America.
9 8 7 6 5 4 3 2 1
SPIN 10922088
2.09 using Springer’s svsing.sty macro.
Typesetting: Pages created by the authors in
www.springer-ny.com
Springer-Verlag New York Berlin Heidelberg
A member of BertelsmannSpringer Science+Business Media GmbH
To Our Parents,
Harriet and Hyman Kushner
and
Wanzhen Zhu and Yixin Yin
Preface and Introduction
The basic stochastic approximation algorithms introduced by Robbins and
Monro and by Kiefer and Wolfowitz in the early 1950s have been the subject
of an enormous literature, both theoretical and applied. This is due to the
large number of applications and the interesting theoretical issues in the
analysis of “dynamically defined” stochastic processes. The basic paradigm
is a stochastic difference equation such as
θ
n+1
=
θ
n
+
n
Y
n
,
where
θ
n
takes
its values in some Euclidean space,
Y
n
is a random variable, and the “step
size”
n
>
0 is small and might go to zero as
n
→ ∞.
In its simplest form,
θ
is a parameter of a system, and the random vector
Y
n
is a function of
“noise-corrupted” observations taken on the system when the parameter is
set to
θ
n
.
One recursively adjusts the parameter so that some goal is met
asymptotically. This book is concerned with the qualitative and asymptotic
properties of such recursive algorithms in the diverse forms in which they
arise in applications. There are analogous continuous time algorithms, but
the conditions and proofs are generally very close to those for the discrete
time case.
The original work was motivated by the problem of finding a root of
a continuous function
g
(θ), where the function is not known but the ex-
¯
perimenter is able to take “noisy” measurements at any desired value of
θ.
Recursive methods for root finding are common in classical numerical
analysis, and it is reasonable to expect that appropriate stochastic analogs
would also perform well.
In one classical example,
θ
is the level of dosage of a drug, and the
function
g
(θ), assumed to be increasing with
θ,
is the probability of success
¯
at dosage level
θ.
The level at which
g
(θ) takes a given value
v
is sought.
¯

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin