As published in LIDS/ALL 2013
Dimitri Bertsekas’ forty-four years of contributions to areas such as optimization theory, data networks, dynamic programming, and large-scale computation proves nearly impossible to measure. His 15 books take too long to summarize. But a few words capture his skill and passion: the language of mathematics. He ‘translates’ and ‘formulates’ and ‘expresses’ complex problems into a language of rules and numbers.
After spending his youth in Athens, Greece and earning his masters at George Washington University, Dimitri arrived at MIT in 1969 and completed his PhD thesis in systems science in two years. There, he witnessed a transition from a narrow focus on control theory to a much broader focus on systems analysis and its set of applications, which included data networks and power, communication, and transportation systems. It was a time when computation was primitive. As Dimitri thinks back to them, he chuckles. “At that time, a computer had 64,000 bits of memory—that’s 64 kilobits, not megabits, not gigabits like we have now,” he says. “The idea of moving messages between computers with those capabilities was mind boggling.” Though he could never have predicted the complexity of today’s networks, he has always been able to see through to their underlying mathematical structure.
In the years that followed, computational resources expanded and data networks multiplied in complexity. With this transformation, along came the observation that all networks similarly feature things—messages, cars, trains, electricity—moving in coordination along networks that cannot sustain a load beyond a certain point. Dimitri notes that when he attempts to optimize traffic or communication networks, he finds identical mathematics. “By studying the mathematical signatures of these problems, you tend to build an understanding uncluttered by their real world characteristics.”
Dimitri encountered his most sustained intellectual focus, optimization theory, during his first faculty position at Stanford University’s Engineering-Economic Systems Department. There, he met his greatest intellectual influence, mathematical scientist David Luenberger, who was one of the early pioneers of modern optimization. The then-emerging field involves making decisions as close to the best way possible in the face of uncertainty, such as calculating the most lucrative investment. “It was an exotic field when I started,” Dimitri says, “and now, optimization permeates just about every quantitative field. It has become the approach of choice in formulating problems.” Ever since, Dimitri has used the language of mathematics to create computational algorithms involving approximations, or attempts to get closer and closer to a solution reasonably fast.
Optimization algorithm design, plus a coincidental rainstorm, brought Dimitri one of his most important discoveries and vivid memories. It was a night in the late 1970s, when Dimitri lived in Illinois. This was during his second faculty position at the Electrical Engineering Department at the University of Illinois at Urbana-Champaign. A relentless storm was flooding his basement, forcing Dimitri to empty the room with a bucket for hours on end. In between bucket-fulls, Dimitri sat at a small desk and attempted to solve a certain optimization problem. But he didn’t have a single book to consult. “So I decided I would start from first principles,” says Dimitri, “solving the problem as a layman would.” It was there in the wet basement, with a pencil and paper, that Dimitri came up with ‘auction algorithms,’ a completely new set of approaches to solving classic optimization problems of both theoretical and practical natures.
An algorithm is a well-defined, step-by-step procedure for calculations. Dimitri’s auction algorithms solve network flow, transportation, and assignment problems, which are fundamental optimization problems that involve agents and tasks that need to be distributed among the agents in a way that minimizes the cost of each task. For one simple example, a bunch of grocery trucks need to make deliveries to restaurants as soon as possible, so the time it takes to make a delivery rings up a cost. The best solution is whatever arrangement of trucks to destinations will achieve the lowest cost. Auction algorithms provide an intuitive way to solve these kinds of problems because they are, as he once wrote, “couched in everyday experience.” As he sat in his basement thinking far outside the boundaries of theoretical literature, he produced an algorithm that operates like a real auction where people make competitive bids to naturally reach the best offers. These methods solved network-type optimization problems fast, and soon became a staple in the field. “Had I had books around me,” says Dimitri, “that idea would probably not have come to me. It was an important discovery, and happened under the most unpredictable of circumstances.”
In 1979, as Dimitri published his first auction algorithm, he began his career at MIT’s Laboratory for Information and Decision Systems (LIDS), where he still works as the McAfee Professor of Engineering. Dimitri soon hit it off with MIT’s Robert Gallager, who was then making a switch from information coding to data communications networks, essentially the progenitor of the Internet. This area offered Dimitri many opportunities to translate practical problems into the language of mathematics and implement optimization theory. It also provided fertile ground for the development of new computational models based on distributed large-scale computation.
At LIDS, where theory and practical application are closely linked, Dimitri is mostly methodologically oriented, but that doesn’t mean his research stays in his books. “LIDS is not an Ivory Tower of ideas,” he says. For example, the government often requires a cost benefit analysis for projects such as building bridges or constructing highways. “The cost and benefits can only be assessed through predictions from mathematical models,” he says, “which will eventually be solved using optimization networks like the ones that we deal with here on a more abstract level.” Students, he notes, are critical in this transfer of ideas from academia to real world problems, as they move from MIT to industry sectors.
Even as Dimitri uses the language of mathematics to express abstract ideas, he often engages with it on a literal level. “I have a kind of a pathology that few people have,” says Bertsekas. “I write a lot of books.” The 15 volumes, several of them influential textbooks, have given him ample opportunity to develop a very specific perspective on mathematical writing, which he notes is not the same as expository writing or really any other form of written language.
Writing, for Dimitri, consists of two written languages: English and math. English is rich and ambiguous; mathematical writing is contained and must always be unambiguous. And while expository and creative writing need excitement and varying sentence styles, “in mathematical writing, you want to make the interesting point stand out and everything else boring, even repetitive” he says. Such a composition style respects the fact that math writing is never read in one go. To truly absorb a mathematical concept, one must read the same section over and over, and eventually connect different parts together. He has created a guideline, “Ten Simple Rules for Mathematical Writing,” aimed towards students who are writing papers and dissertations.
Dimitri observes that the Stata Center, the Frank Gehry-designed architectural marvel and home of LIDS, truly reflects MIT’s spirit of innovation in a way like no other campus building. It’s a “photographer’s paradise” because the sloping metal surfaces change the way it reflects light and colors across the entire day. Several of Dimitri’s Stata Center photographs hang along the hallways of LIDS. In one, the mirror-like metal siding of the Center distorts the image of a neighboring brick building, so the reflection appears as melting orange liquid. At first glance, you will think it is a painting. Dimitri has photographed it in the way he creates his algorithms, abstracting a complex structure in order to see it in a whole new light.