Stochastic Approximation Methods for Constrained and Unconstrained Systems

I. Introduction.- 1.1. General Remarks.- 1.2. The Robbins-Monro Process.- 1.3. A “Continuous” Process Version of Section 2.- 1.4. Regulation of a Dynamical System; a simple example.- 1.5. Function Minimization: The Kiefer-Wolfowitz Procedure.- 1.6. Constrained Problems.- 1.7. An Economics Example.- II. Convergence w.p.1 for Unconstrained Systems.- 2.1. Preliminaries and Motivation.- 2.2. The Robbins-Monro and Kiefer-Wolfowitz Algorithms: Conditions and Discussion.- 2.3. Convergence Proofs for RM and KW-like Procedures.- 2.3.1. A Basic RM-like Procedure.- 2.3.2. One Dimensional RM and Accelerated RM Procedures.- 2.3.3. A Continuous Parameter RM Procedure.- 2.3.4. The Basic Kiefer-Wolfowitz Procedure.- 2.3.5. Random Directions KW Methods.- 2.4. A General Robbins-Monro Process: “Exogenous Noise”.- 2.4.1. The Case of Bounded h(•,•).- 2.4.2. Unbounded h(•,•): Exogenous Noise.- 2.5. A General RM Process; State Dependent Noise.- 2.5.1. Extensions and Localizations of Theorem 2.5.2.- 2.6. Some Applications.- 2.7. Mensov-Rademacher Estimates.- III. Weak Convergence of Probability Measures.- IV. Weak Convergence for Unconstrained Systems.- 4.1. Conditions and General Discussion.- 4.2. The Robbins-Monro and Kiefer-Wolfowitz Procedures.- 4.2.1. The Basic Robbins-Monro Procedure.- 4.2.2. The One-Dimensional Robbins-Monro Procedure.- 4.2.3. The Kiefer-Wolfowitz Procedure.- 4.2.4. A Case Where the Limit Satisfies a Generalized ODE.- 4.2.5. A Continuous Parameter KW Procedure.- 4.3. A General Robbins-Monro Process: Exogenous Noise.- 4.4. A General RM Process: State Dependent Noise.- 4.5. The Identification Problem.- 4.6. A Counter-Example to Tightness.- 4.7. Boundedness of {Xn} and Tightness of {Xn(•)}.- V. Convergence w.p.1 For Constrained Systems.- 5.1. A Penalty-Multiplier Algorithm for Equality Constraints.- 5.1.1. A Basic RM-like Algorithm, Conditions and Discussion.- 5.1.2. The Noise Condition, Discussion and Generalization.- 5.1.3. Boundedness of {Xn}.- 5.1.4. Proof of the Main Theorem.- 5.1.5. Constrained Function Minimization and Other Extensions.- 5.2. A Lagrangian Method for Inequality Constraints.- 5.2.1. The Algorithm and Conditions.- 5.2.2. The Convergence Theorem 18.- 5.2.3. A Non-Convergent but Useful Algorithm.- 5.2.4. An Application to the Identification Problem.- 5.3. A Projection Algorithm.- 5.4. A Penalty-Multiplier Method for Inequality Constraints.- VI. Weak Convergence: Constrained Systems.- 6.1. A Multiplier Type Algorithm for Equality Constraints.- 6.1.1. Boundedness of {Xn}.- 6.1.2. The Noise Condition, Discussion.- 6.1.3. The Convergence Theorem.- 6.2. The Lagrangian Method.- 6.3. A Projection Algorithm.- 6.4. A Penalty-Multiplier Algorithm for Inequality Constraints.- VII. Rates of Convergence.- 7.1. The Problem Formulation.- 7.2. Conditions and Discussions.- 7.3. Rates of Convergence for Case 1, the KW Algorithm.- 7.4. Discussion of Rates of Convergence for Two KW Algorithms.