Stochastic Optimization and Control
625.743

Course Description and Philosophy
Analysts, engineers, and managers are often faced with making tradeoffs between different factors in order to achieve desirable outcomes. Choosing these tradeoffs in the "best" way is the essence of optimization and learning. Stochastic search and optimization plays an increasing role in the analysis and control of modern systems as a way of: (i) coping with inherent system noise, (ii) providing algorithms that are relatively insensitive to modeling uncertainty, and (iii) providing algorithms that are able to find a global solution from among multiple local solutions.

This course introduces the fundamental issues in stochastic search and optimization with special emphasis on cases where classical deterministic techniques (linear and nonlinear programming, etc.) are inappropriate. These cases include many important practical problems, which will be discussed throughout the course (e.g., neural network training, global optimization, simulation-based optimization, nonlinear control, image processing, discrete-event systems, experimental design, etc.). Discrete and continuous optimization problems will be considered. Algorithms for global and local optimization problems will be discussed. Approaches such as random search, recursive least squares, Kalman filtering, stochastic approximation, simulated annealing, evolutionary and genetic algorithms, machine learning, and multiple comparisons are discussed.

The course will cover the relationships among algorithms and provide some guidance about which algorithms are appropriate for which problems. The emphasis will be on rigorous analysis and interpretation, with the aim of giving the students the tools to help sort through competing and conflicting claims in the literature. A student who successfully completes this course will be in a position to implement the algorithms and/or critically evaluate the implementations of others in a wide variety of practical problems.

The grade for the course will be based on a combination of performance on homework and final project. Homework will be assigned most weeks and will be due the following class. There are no in-class tests.

This course is co-listed in the Applied and Computational Mathematics and Electrical Engineering Programs of JHU Part-Time Engineering; it may serve as an elective in other JHU programs subject to adviser approval.

Subjects to be covered
1. Basic issues in search and optimization; stochastic vs. deterministic methods; no free lunch theorems, summary of classical methods of optimization and their limitations; review of multivariate analysis and matrix algebra (Chapter 1 and Appendix A).
2. Introduction to random search; Monte Carlo methods; discussion of probabilistic convergence and review of basic statistical tests (Chapter 2 and Appendices B and C).
3. Nonlinear simplex method; continued review of probabilistic convergence and basic statistical tests (Chapter 2 and Appendices B and C).
4. Recursive methods for linear systems: least mean squares, recursive least squares, and Kalman filter (Chapter 3).
5. Root-finding and gradient-based stochastic approximation (Robbins-Monro) (Chapter 4).
6. Stochastic gradient-based stochastic approximation (Chapter 5).
7. Gradient-free stochastic approximation with emphasis on the finite-difference (FDSA) method (Chapter 6)
8. Simultaneous perturbation stochastic approximation (SPSA): efficiency and theoretical analysis; implementation (link to supplementary information on SPSA)
9. Simulated annealing and related methods (Chapter 8 and Appendix E).
10. Evolutionary computation with emphasis on genetic algorithms (Chapter 9).
11. Evolutionary computation (continued): evolution strategies and theory for genetic algorithms (Chapter 10)
12. Machine learning via temporal difference methods (Chapter 11)
13. Statistical multiple comparisons for selecting the best of several options (discrete optimization) (Chapter 12)
14. Student presentations of final reports and discussions of other projects

Prerequisites
Students should come into the class with a working knowledge of probability and statistics at the beginning graduate level  (e.g., 625.403) and knowledge of multivariate calculus and basic matrix algebra. Previous optimization experience is not required. Some assignments will require the use of a computer; the student is free to use any programming language with which he/she is comfortable (the instructor will use MATLAB and will occasionally pass out MATLAB code). Students are encouraged to contact the instructor for additional information.

Instructor
James C. Spall joined the Johns Hopkins University Applied Physics Laboratory in 1983 and was appointed to the Principal Professional Staff in 1991.  He is also Chair of the JHU Applied and Computational Mathematics Program. Dr. Spall has published over 100 articles in the areas of statistics and control and holds two U.S. patents. For the year 1990, he received the Hart Prize as principal investigator of the most outstanding Independent Research and Development project at JHU/APL. Among other appointments, he is an Associate Editor at Large for the IEEE Transactions on Automatic Control and a contributing editor for the Current Index to Statistics. He is the editor and co-author for the book Bayesian Analysis of Time Series and Dynamic Models (Marcel Dekker) and is the author of the course textbook Introduction to Stochastic Search and Optimization (Wiley). Dr. Spall has received numerous research and publications awards and is a Fellow of IEEE, a member of the American Statistical Association, and a Fellow of the engineering honor society Tau Beta Pi. The perspective Dr. Spall will bring to the course balances the theoretical aspects of the field with the practical requirements for using search and optimization algorithms for solving real problems.
E-mail the instructor.

Course Section, Location, and Time
 

625.743.31

Applied Physics Laboratory (K4)

Thursday

4:30-7:10

Computer Lab Requirements
Some homework assignments require the use of a computer.  Students are free to use whatever system and software is convenient. The instructor uses PC-based MATLAB.

Textbook
The textbook for this course is Introduction to Stochastic Search and Optimization by J. C. Spall  (Wiley, 2003) (ISBN:  0-471-33052-3).  The text will be available approximately midway through the course  In the interim, students will receive handouts of relevant material from the book.  A comprehensive collection of supplementary reference literature is on reserve in the Gibson Library at APL. These papers are largely optional reading, but are provided to indicate other perspectives and to provide more detailed information on certain subjects than are available in the textbook.  Many of these papers are at a more advanced level than the material in the course. Some students may find these papers useful in carrying out the final class project.

Return to Part-Time Engineering
Return to Whiting School of Engineering
Return to JHUniverse
Applied Math

updated January 2003