Optimization algorithms take a problem—the best airline route from Chicago to Atlanta, for example—and consider variables, like air traffic and wind, before presenting the optimal solution.
Nocedal developed L-BFGS after realizing that an existing optimization algorithm called BFGS could not be applied to problems with numerous variables. He tried to solve this throughout graduate school and succeeded only after becoming a faculty member and realizing the algorithm could not retain everything it learned, because that would exceed the capacity of every computer. Instead, it needed to retain only a limited amount of relevant information, called limited memory—the “L” in L-BFGS.
“My modification of the algorithm allowed it to solve problems with millions of variables,” says Nocedal, Walter P. Murphy Professor of Industrial Engineering and Management Sciences. But this was before big data and its usefulness were widely understood. Nocedal kept refining it based on his increasingly deeper understanding of the problem. In the 1990s, the algorithm became popular with weather forecasters, and when machine-learning research took off 20 years later, the use of the algorithm accelerated.
Now, most everyone in the field of machine learning knows the term L-BFGS. Recently, the algorithm was used as part of the Google DeepMind project to help determine the 3D shapes of proteins—a breakthrough that could lead to major advances in biology and drug discovery. It was also used early in the pandemic by the federal government to model the COVID-19 pandemic’s trajectory.
In the 1990s, Nocedal also began developing another nonlinear optimization algorithm called KNITRO. This algorithm took even longer to develop than L-BFGS and could solve more complicated problems with more restrictions. He and his graduate students ultimately commercialized the algorithm as software. Now, KNITRO is widely used in the energy, finance, economics, and robotics sectors.
Enabling New Technologies with Ipopt
We’re developing enabling technologies. Not only are our algorithms used in all these different industries, they also make it possible for scientists and engineers to do new research. Andreas WächterProfessor of Industrial Engineering & Management Sciences
KNITRO has a companion in Ipopt, the nonlinear optimization algorithm developed by Wächter using a different algorithm than KNITRO. Wächter, professor of industrial engineering and management sciences, began developing the algorithm in the late 1990s when he was a chemical engineering graduate student. He continued working on Ipopt at IBM, where it became an open-source project.
For years, he used math, theory, and computer programming to test and refine Ipopt. When it was translated into the C++ programming language, it became known as the go-to open-source nonlinear optimization algorithm.
Wächter regularly hears about new applications of the algorithm—running trains, optimizing power grids, building chemical plants, developing airline routes, enhancing medical imaging, and even creating models of black holes.
“We’re developing enabling technologies,” he says. “Not only are our algorithms used in all these different industries, they also make it possible for scientists and engineers to do new research.”
Both Nocedal and Wächter continue to develop new algorithms. The future, Nocedal says, lies in algorithms that can deal with uncertainty. One rich source of new problems is in machine learning where optimization must be performed in the presence of uncertainty in the data. Given the explosive growth of artificial intelligence, the demand for more capable optimization algorithms will only increase with time.
