INFORMS News: Goldfarb, Nocedal share von Neumann Prize

p46_Photo Caption(s):
Presenter Avishai Mandelbaum (left) congratulates Donald Goldfarb (center) as INFORMS President Brian Denton (right) looks on.
The 2017 John von Neumann Theory Prize of INFORMS was awarded to Donald Goldfarb and Jorge Nocedal for their “fundamental contributions, theoretical and practical, that have, and continue to have, a significant impact on the field of optimization.” The award citation also noted that Goldfarb, a professor of industrial engineering and operations research at Columbia University, and Nocedal, a professor of industrial engineering and management sciences at Northwestern University, have made “seminal contributions to the theory and applications of nonlinear theory and applications of nonlinear optimization over the past several decades. These contributions cover a full range of topics, going from modeling, to mathematical analysis, to breakthroughs in scientific computing. Their work on the variable metric methods (BFGS and L-BFGS, respectively) has been extremely influential.”

Prize committee chair Avishai Mandelbaum made the presentation at the 2017 INFORMS Annual Meeting in Houston. The prize recognizes scholars who have made fundamental, sustained contributions to theory in operations research and the management sciences.

The citation read in part:

Goldfarb’s deep research contributions tie together the theoretical and the very practical in traditional linear and nonlinear programming, interior point methods, and the newly in vogue methods developed for signal processing and machine learning – and doing all that through a unique understanding of the fundamental issues in each and all of these areas.

His contributions to the field are exceptionally broad, very influential and long-lasting, beginning with the famous Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm for nonlinear optimization in the 1960s, then the revolutionary steepest edge simplex method for linear programming in the 1980s and in the last decade first-order methods for large-scale convex optimization. The primal and dual steepest edge simplex algorithms, devised by Goldfarb with Reid and Forrest, respectively, are the most widely used variants of the simplex method. Goldfarb’s work provides the theoretical foundation for many variants of this method implemented in most state-of-the-art commercial linear programming solvers. The Goldfarb-Idnani dual active set method for quadratic programming (QP) is one of the most widely used QP methods.

Nocedal made seminal contributions to the area of unconstrained and constrained nonlinear optimization that have fundamentally reshaped this field. This includes the development of L-BFGS methods, extending interior point methods to non-convex constrained optimization, co-authoring a highly influential book in nonlinear optimization, and recently illuminating the interface between optimization and machine learning via efficient and effective second-order methods.

In the 1980s, Nocedal invented the L-BFGS optimization algorithm, the limited memory version of the BFGS method. This opened the door to solving vastly larger unconstrained and box-constrained nonlinear optimization problems than previously possible; Nocedal’s L-BFGS algorithm requires storage that is only a small multiple of the number of variables, whereas the original BFGS method required a quadratic amount of storage. The L-BFGS algorithm has had an immense practical impact, which is difficult to overstate.

Nocedal was also instrumental in extending the interior-point revolution beyond convex optimization. In the late 1990s, he and his collaborators proposed the first theoretically sound algorithm for nonlinear and nonconvex optimization problems. This algorithm was practical and, importantly, did not rely on strong assumptions.