John von Neumann Theory Prize

This award recognizes their seminal and profound contributions to the theoretical foundations of optimization. Through their work in the domains of integer programming and polynomial optimization, respectively, Chvátal and Lasserre developed the mathematical theory and corresponding computational approaches to tackle hard computational problems that compute strengthened bounds via tractable convex relaxations. The notions of Chvátal rank and the Lasserre hierarchy each have impact well beyond their initial research spheres and are simultaneously elegant mathematics and the foundations for new algorithmic approaches.

Vašek Chvátal's body of theoretical research work has brought elegance to the field of operations research, and in particular linear and integer programming, algorithms, complexity, graph theory, and computation, that is unmatched. It is easy to select Chvátal's 1973 cutting-plane paper ``Edmonds polytopes and a hierarchy of combinatorial problems'' as one of the top papers in the history of integer programming, in which Chvátal shed new light on Gomory’s fractional cutting planes for solving integer programs and, even more importantly, introduced the concept of the rank of valid inequalities and polyhedra. This new idea of rank provided the structure to understand the difficult task of creating integral polyhedral from relaxations and impacted the subsequent development of theory and algorithms. His slogan combinatorics = number theory + linear programming became the rallying cry for researchers in the following decades, when cutting planes went on to be the most important component of the expansion and increased depth of the field. In the area of algorithms, Chvátal's 1979 paper ``A greedy heuristic for the set-covering problem'' introduced an amazing dual argument, showing a logarithmic optimality ratio for a simple greedy algorithm. The LP-duality line-of-thought is now a central tool in the area of approximation methods for NP-hard problems. In complexity theory, Chvátal introduced the notion of cutting-plane proofs that has become an important model of computation. In 1988, he also co-authored, with Szemerédi, the influential paper ``Many hard examples for resolution,'' describing the use of randomization to create a class of satisfiability problems that is difficult for the resolution proof system. Chvátal and Szemerédi do not construct specific examples of their class, but rather show that with high probability a random example is difficult. This is an elegant blueprint for a possible attack on P versus NP itself. In the early 1990s, Chvátal turned his research focus to computational work, tackling the traveling salesman problem with the concrete aim of solving large instances to exact optimality. In 1973, he introduced the concept of comb inequalities that had taken the cutting-plane approach to the TSP to new heights in the 1970s and 1980s. In this new work, Chvátal succeeded in bringing to bear on the TSP many of the further ideas he had developed in his general studies of integer programming, algorithms, and complexity. This research, together with Applegate, Bixby, and Cook, is described in the 2007 Lanchester Prize winning book The Traveling Salesman: A Computational Study. Their Concorde code gradually worked through the entire TSPLIB challenge set, including the exact solution of an instance consisting of 85,900 cities from a VLSI application. This success is a primary example of the power of sophisticated mathematical tools to solve seemingly intractable optimization models.

Jean Lasserre’s fundamental work on optimization has provided the mathematical framework to solve an important class of optimization problems--polynomial optimization--in which one aims to minimize a polynomial function subject to polynomial inequality constraints, which has been applied in areas ranging from control theory to machine learning-inspired clustering problems, and computer vision to quantum cryptography. Lasserre’s paper, “Global optimization with polynomials and the problem of moments,” created the field of polynomial optimization, and outlined the major tools and underlying mathematics of virtually all work in the area that followed. These problems are non-convex, very hard to solve, and previous work settled for finding only a local optimum. Lasserre introduced an ingenious new method based on reformulating the problem as a convex optimization problem over the set of measures having a prescribed support; next he devised a scheme of hierarchical approximations for the original problem based on exploiting necessary conditions for sequences of moments of measures. He not only proved the convergence of the bounds to the optimum value of the original hard problem, but also used this as the basis for an effective computational method for computing global optimizers, relying on the fact that these hierarchical bounds can be computed via semidefinite programming. This is a landmark achievement in the development of the mathematics of optimization. A key aspect of this paper was the use of techniques from real algebraic geometry to derive certificates of positivity using representations by sums of squared polynomials. Building on this in his subsequent paper, “A sum of squares approximation of nonnegative polynomials,” Lasserre gave an elegant new proof of the central element in this theory: any nonnegative polynomial can be approximated by sums of squares. Combining convex duality theory and a moment-theoretic result, he constructed approximating polynomials that are both simple and explicit. One consequence is a vast simplification of his original relaxation hierarchy; this simplification has enabled it to be integrated in a plethora of new directions, where one important exemplar is in the theory of approximations for NP-hard discrete optimization problems, where the “Lasserre hierarchy” is at the heart of current work to both prove and disprove the unique games conjecture. This work was also Lasserre’s starting point for further generalizations, such as his work on the generalized moment problem, which significantly extends the reach of these methods.