Dimitri P. Bertsekas

Dimitri P. Bertsekas

Past Awards

2018
John von Neumann Theory Prize: Awardee(s)
2018 - Awardee(s)
Citation:

The 2018 INFORMS John von Neumann theory prize is awarded to Dimitri P. Bertsekas and John N. Tsitsiklis for contributions to Parallel and Distributed Computation as well as Neurodynamic Programming.  Working together and independently, Bertsekas and Tsitsiklis have made seminal contributions to both these fields. They unified ideas and built solid theoretical foundations while these fields were still relatively nascent, thus greatly enhancing subsequent development of rigorous theory.
Their monograph Parallel and Distributed Computation: Numerical Methods represents a significant achievement in the field. The work builds on and extends the authors’ extensive previous work in this area, identifying the tolerance of algorithms to asynchronous implementations and a number of positive convergence results. An antecedent work of particular significance to the operations research community is the paper by Tsitsiklis, Bertsekas and Athans which provides seminal analysis of asynchronous implementations of deterministic and stochastic gradient algorithms. This line of inquiry has recently found application in the analysis of descent algorithms for neural network training and other machine learning problems. Their work in distributed computation has also had significant impact on the areas of distributed network control and distributed detection.
Their monograph Neuro-Dynamic Programming helped provide a unified theoretical treatment of the wide variety of reinforcement learning algorithms by building connections to the dynamic programming and distributed computation literature. This has proven extremely valuable in bringing theoretical rigor to a field of rapid, empirical innovation.  The authors’ contributions in this area go beyond providing a theoretical foundation that other could build on. The authors have made significant original contributions to value function learning, temporal difference methods and actor-critic algorithms.
The work of Bertsekas and Tsitsiklis is characterized by its innovation, depth and clarity, and it has had tremendous impact as evident from the large number of citations. Their two joint monographs are among their individual five most cited works, making the award of a joint prize particularly appropriate. Bertsekas and Tsitsiklis have brought the fields of computer science and operations research closer together through unifying theory.



2014
Optimization Society Khachiyan Prize: Awardee(s)
2014 - Awardee(s)
Citation:

The 2014 recipients of the INFORMS Optimization Society Khachiyan Prize, for their remarkable life-time achievements in the area of optimization, are Clóvis C. Gonzaga, Professor of Mathematics at the Federal University of Santa Catarina, Florianópolis, Brazil, and Dimitri Bertsekas, McAfee Professor of Engineering at the Massachusetts Institute of Technology.

Clóvis C. Gonzaga has been working on continuous optimization for the last 40 years. He was one of the founders of the Systems and Computation Dept. at the Federal University of Rio de Janeiro, where he was the first person in Brazil to teach non-linear programming. He worked simultaneously on graph search methods, continuous optimization and on optimal power systems. He was responsible for the software used in Brazil for many years to plan the expansion of the Brazilian power transmission system.

During his remarkable career, Clóvis Gonzaga has grown to be one of the world's foremost experts in the area of continuous optimization, with main interest in the fundamental problems of Interior Point methods (IPMs). Since the mid 80's, as one of the leading developer of IPMs, Gonzaga is among the most recognized optimization researchers. His 1989 seminal paper, "An algorithm for solving linear programming problems in O(n^3L) operations," contains the analysis of a path-following method that till today yields the best complexity bound for solving linear optimization problems. His 1992 SIAM Review paper "Path-following methods for linear programming" is among the most influential papers that inspired and motivated many researchers.

While Gonzaga has remained to play a key role in the developments of IPMs, recently he also worked on augmented Lagrangean methods, on filter methods for constrained non-linear optimization, and on fast steepest descent methods. He has recently developed steepest descent algorithms for the minimization of convex quadratic functions with the same performance bound as Krylov space methods.

Clóvis Gonzaga has been active in teaching and spreading the interest for continuous optimization worldwide. He is a SIAM fellow, a member of the Brazilian Academy of Sciences and of the World Academy of Sciences, and received the Great Cross of the Brazilian Order of Scientific Merit. He was a plenary or semi-plenary speaker in several prime conferences, such as ISMP (twice), SIOPT, IFIP, IFORS, ICIAM.

Dimitri Bertsekas has made fundamental contributions to multiple areas of optimization including theory, computation, and applications.  He has also contributed to optimization knowledge broadly through the clarity of exposition in his many books on optimization topics and the accomplishments of his students who have in turn made significant advances in the field.

Professor Bertsekas's theoretical contributions include his resolving the question of conditions for a consistent recursive form for dynamic programming with uncountable state spaces through the introduction of universally measurable spaces.  He also helped establish the theoretical foundation for Lagrangian methods in nonlinear programming with general convergence results, duality theory, and procedures and bounds for nonconvex formulations.  His more recent theoretical work includes a comprehensive view of the basic properties underlying dynamic programming and a geometric interpretation of duality and general optimality conditions with algorithmic implications.

In algorithmic development, Professor Bertsekas was a pioneer in network optimization through his development of the classes of auction and relaxation algorithms. These methods led not only to some of the most efficient algorithms in practice but to many new theoretical discoveries in the field.  In addition, Professor Bertsekas's work includes the exposition of the generalized alternate direction method that has recently become a foundation for work in machine learning and statistical inference in large data sets.

In addition to his many specific research contributions, Professor Bertsekas's books have exposed many researchers, practitioners, and students in a wide range of fields to the principles of optimization.  His work has had a profound influence on numerous domains such as signal processing, communications, power systems, transportation, logistics, and economics.  His many students have expanded his work even more broadly, adding to his continued and lasting impact on the field.

Video recordings

The two winners of the Khachiyan prize were invited to give a short talk (about 15 minutes) at the INFORMS Annual Meeting. Below are links to the recordings of these talks.

Selection committee

Tamás Terlaky (chair), Daniel Bienstock, Immanuel Bomze, John Birge

Clóvis C. Gonzaga and Dimitri Bertsekas are awarded the 2014 Khachiyan Prize.



2009
Saul Gass Expository Writing Award: Winner(s)
Citation:

The Committee for the Expository Writing Award is pleased to name Dimitri P. Bertsekas as the 2009 recipient. Professor Bertsekas is a prolific author, renowned for his books on topics spanning dynamic programming and stochastic control, convex analysis, parallel computation, data networks, and linear and nonlinear programming. These books are supported by an extensive record of journal publications which have made numerous seminal contributions. He communicates difficult mathematical concepts with unusual clarity, thereby reaching a broad audience across many disciplines.

His writing is perhaps best exemplified by his books on dynamic programming and stochastic control. His most recent contribution, Dynamic Programming and Optimal Control, offers an elegant and thorough treatment of the concepts of stochastic control with the clarity of an introductory text, while providing students with the foundation to understand optimization over time in a range of applications. This book includes an extensive chapter on approximate dynamic programming that builds on his earlier work, Neuro-Dynamic Programming (with John Tsitsiklis). This earlier work was the first book to bridge the literature on stochastic approximation and dynamic programming, thus integrating the rapidly growing field of reinforcement learning with Markov decision processes in a rigorous and accessible way.

A significant dimension of Professor Bertsekas’ writing is his ability to bridge the multiple disciplines spanned by his books. His contributions to distributed computation led to the concepts of synchronous and asynchronous algorithms for Markov decision processes. He has contributed insights into the properties of approximate dynamic programming algorithms over restricted spaces by drawing on his deep understanding of linear algebra developed in his work on mathematical programming and convex analysis. These contributions exemplify a style of “scholarship through writing” that enables a deep exploration and unification of new fields of research which has become a hallmark of Professor Bertsekas’ distinguished career.

Professor Bertsekas’ writing communicates rigorous mathematics in a clear, accessible style, as evidenced by an extraordinary 30,000 citations to date. This style, which he has shared in his presentation “Ten simple rules for mathematical writing,” available online at his M.I.T. website, emphasizes clarity with precision. This makes his books useful as both introductory texts as well as advanced research references. It is for this reason that the Expository Writing Committee (Nicholas G. Hall, Garrett J. van Ryzin and Warren B. Powell) is pleased to name Dimitri P. Bertsekas as the recipient of the 2009 INFORMS Expository Writing Award.



1997
INFORMS Computing Society Prize: First Place