Course Meeting Times
Lectures: 1 session / week, 2 hours / session
Course Overview
15.099 Topic for Fall 2003: Randomized Methods for (Continuous) Deterministic Optimization
In keeping with the tradition of the last twenty-some years, the Readings in Optimization seminar will focus on an advanced topic of interest to a portion of the MIT optimization community. As has been the case for many previous versions of this seminar, we often choose a topic that is of current interest (perhaps even "hot") in the optimization community, or that is topical in practice. Randomized methods for deterministic optimization certainly meets the first criterion (if not the second as well).
In contrast to conventional optimization algorithms whose iterates are computed and analyzed deterministically, randomized methods rely on stochastic processes and random number/vector generation as part of the algorithm and/or its analysis. Consider the simplex method, for example. One can develop a randomized version of the simplex method by choosing incoming columns or entire bases according to some stochastic process. For more general nonlinear optimization problems, a simple randomized algorithm would be to base the search direction on a randomly chosen vector; the distribution of the vector might be iteration-dependent, of course. There are very sophisticated randomized algorithms for convex and non-convex optimization that rely on recently-developed methods for approximately generating uniformly distributed random variables on convex sets. In terms of complexity analysis, many randomized algorithms have excellent properties: they solve problems to a high accuracy in polynomial time with high probability or their expected running time is polynomial. Of course, these sorts of statements are vague until we define "high probability", etc. In the seminar, we will study some very recent papers on this topic, many by MIT faculty, as well as some older papers from the existing literature that are only now receiving attention.
Seminar Format
The seminar will meet once a week for two hours. In each session, one or more students or a faculty member will have the responsibility to lead the discussion. Typically, each session will cover one or two papers from the literature (published or working papers). Student discussion leaders have responsibility for preparing a conference quality presentation (with overheads) and for preparing a handout of transparencies for the class. Therefore, the seminar also provides a friendly setting for developing presentation skills and practicing teaching. The seminar is intended to be an informal forum for discussion and for interaction among the student and faculty participants, and works best when everyone contributes. (Indeed, in the past the seminar has been most successful when it is "alive" and several individuals are adding to the discussion leader's presentation by suggesting material on the board.) Since we are collectively exploring an advanced topic, the discussion leader need not feel that he or she must have a complete grasp of everything being presented — often coming to class with questions about a technical point leads to the most lively discussion and the greatest learning.
Grades
Since this is an advanced seminar, grading and distinguishing between student performance is not very important (at least to me). Students who make an honest effort to make good presentations and to contribute to the best of their ability will receive a good grade (an A).
Session Coverage
Since this is an informal seminar, we do not typically keep to any fixed schedule. If we find that we need more time for a paper once we are discussing it, then we will typically extend the discussion to the next session and delay subsequent sessions. Or, if someone discovers some new material that we might like to discuss, then we might add that to the agenda. The calendar provides an outline of the coverage for the course sessions.