Michael J. Todd

Michael J. Todd

Past Awards

John von Neumann Theory Prize: Winner(s)

The 2003 John von Neumann Theory Prize is awarded by the Institute for Operations Research and the Management Sciences to Arkadi Nemirovski and Michael J. Todd in recognition of their seminal and profound contributions to continuous optimization.

Arkadi Nemirovski has made fundamental contributions in continuous optimization in the last thirty years that have significantly shaped the field. He developed (with D. Yudin) the theory of information-based complexity for convex optimization underlying the majority of modern results on efficient solvability of well-structured convex problems, which is described in their book "Problem complexity and method efficiency in optimization" (1983). This work led to the development of the ellipsoid algorithm (with Yudin) and the polynomial-time solvability of linear programming (by L. Khachiyan), and Nemirovski was the co-recipient (together with Yudin and Khachiyan) of the Fulkerson Prize from the Mathematical Programming Society and the American Mathematical Society in 1982. In the 1980s and 1990s Nemirovski did ground-breaking work in the theory and algorithmic implementation of interior-point polynomial-time methods for convex optimization. He developed (with Y. Nesterov) a general theory of polynomial-time interior-point methods that is described in their book "Interior-point polynomial algorithms in convex programming" (1994). In recognition of his contributions to convex optimization, Nemirovski was awarded the Dantzig Prize from the Mathematical Programming Society and the Society for Industrial and Applied Mathematics in 1991. He introduced and developed (with A. Ben-Tal) the theory of robust optimization as a way of dealing with data perturbations in convex optimization. This, along with applications of convex optimization to quadratically constrained, semidefinite, and geometric optimization problems, is described in their book "Lectures on modern convex optimization: analysis, algorithms; engineering applications" (2001). He continues to make significant contributions in almost all aspects of continuous optimization: complexity, numerical methods, stochastic optimization, and non-parametric statistics. Arkadi Nemirovski is also widely admired for his kindness, gracious humility, and his dedication to his students and colleagues.

Michael Todd has made fundamental contributions in a variety of different theoretical domains in continuous optimization. Much of his early work was in fixed-point methods, where he developed new triangulations for fixed-point algorithms and developed the critical measure of efficiency of triangulations (average directional density); in addition he made important contributions to combinatorial and pivot theory for fixed-point methods and related mathematical structures. Todd's work in linear programming includes one of the fundamental papers on probabilistic analysis of the simplex method, and the definitive reference on the ellipsoid algorithm (with R. Bland and D. Goldfarb). In the field of interior-point algorithms, Todd's many results include the first workable lower-bounding procedure for Karmarkar's algorithm (with B. Burrell); one of the first papers to utilize the primal-dual potential function (with Y. Ye); a nontrivial lower bound on the complexity of primal-dual algorithms (with Y. Ye), the homogeneous self-dual embedding for linear optimization (with S. Mizuno and Y. Ye); the theory of self-scaled cones and their application to primal-dual interior-point methods for convex optimization (with Y. Nesterov); and the widely-used interior-point software code SDPT3 (with K.C. Toh and R. Tütüncü). These and other research papers defined new and critical ways of thinking about the underlying theory of optimization, established the important issues in the field, and explored a variety of mathematical themes and algorithmic concepts. Todd was awarded the Dantzig Prize in 1988 by the Mathematical Programming Society and the Society for Industrial and Applied Mathematics. He is equally appreciated for his exceptional professional judgment and fairness in academic matters, his collegial friendship, the clarity of his exposition, and his energy and drive capped with a good sense of humor.