Readings in optimization

Lectures: 1 session / week, 2 hours / session

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.

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.

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).

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.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare