Solving the 'Curses of Dimensionality'

By Teresa Riordan
February 05, 2008

Approximate Dynamic Programming: Solving the Curses of DimensionalityJohn Wiley & Sons recently published Approximate Dynamic Programming: Solving the Curses of Dimensionality by Warren Powell, professor of operations research and financial engineering.

The book describes Powell’s novel method of melding two approaches—math programming and dynamic programming—to solve problems that involve decisions with a high degree of uncertainty. These problems arise in a variety of industries, including transportation, energy and the financial sector.

Powell compared his technique to Groundhog Day, the movie starring Bill Murray as a TV weatherman who experiences the same day over and over and gradually learns from experience to become a better human being.

Dynamic programming is often dismissed as impractical for problems with high degrees of uncertainty because of something known as “the curse of dimensionality,” the exponential increase in difficulty that occurs each time a new dimension is introduced to a mathematical problem.

Powell says that problems in his field of operations research often are so complex that they have not one but three curses of dimensionality. He discovered he could tame these curses by yoking dynamic programming to math programming, a problem-solving technique used in optimization.

“This book shows how to use math programming in an iterative framework where you make decisions and then simulate how well they work,” said Powell. “The trick is then learning from these decisions so that you make better decisions the next time.”

The book should appeal to a wide audience within the field. “It can be used as a textbook in undergraduate or graduate courses, or for practitioners who want to learn about recent advances in this exciting area,” said Diego Klabjan, an associate professor in industrial engineering and management sciences at Northwestern University.