Author Spotlight

In Conversation With...
Jean Bernard Lasserre

Although he’s won two significant awards and a coveted European Research Council grant since 2014, Jean Lasserre is not resting on his laurels. With the grade of “Directeur de Recherche” at the Laboratory for Analysis and Architecture of Systems at the acclaimed National Center for Scientific Research in Toulouse, France, Lasserre is avidly studying the Generalized Problem of Moments to show how the SOS (Sum of Squares) hierarchy (or some of its variants) can help solve such problems, particularly as applied to nonconvex problems. Lasserre’s name is synonymous with the moment-SOS approach; indeed many people might be more familiar with the common name associated with this numerical scheme—the Lasserre Hierarchy. Lasserre’s research has been seminal to the optimization field, in particular to the specific issue of polynomial optimization.

In 2015, Lasserre was bestowed with the prestigious John von Neumann Theory Prize from INFORMS. The prize is awarded annually to scholars who have made fundamental, sustained contributions to theory in operations research and the management sciences. Lasserre’s 2001 [7] 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. His subsequent paper [9], “A sum of squares approximation of nonnegative polynomials,” provided an elegant new proof for another important result: Namely, any nonnegative polynomial can be approximated by a simple (and canonical) sum of squares (when higher degrees are allowed).

Lasserre’s relationship with the INFORMS journal Mathematics of Operations Research dates back to 2002, when his article, “Semidefinite Programming vs. LP Relaxations for Polynomial Programming” [8], was published. Since 2002, five papers by Lasserre have appeared in Mathematics of OR, and in 2014, Lasserre was appointed as an associate editor for the journal. In addition, Lasserre has contributed to the INFORMS flagship journals Management Science and Operations Research.

INFORMS reached out to Jean Lasserre in Fall 2016 to learn more about his recent awards, his predictions for the future of operations research (OR), and his advice for students entering this important field. What follows is the first in a series of interviews that will showcase the thought-leaders in the field of operations research.

INFORMS: Congratulations on winning the INFORMS von Neumann Prize. How has winning this award impacted your professional life?

LASSERRE: Well, it has certainly increased visibility of this methodology but I would be very proud if it will attract interest of a larger community in the Generalized Problem of Moments (GPM). Indeed the list of its important applications is almost endless...

INFORMS: How has the operations research field changed since you first entered it?

LASSERRE: One important (if not unique) goal of OR is to help solve practical problems with tools from applied mathematics, probability, statistics, and so forth. However, the focus now seems to be much more on “applications” than on “disciplines.” For instance “LP” [linear programming] and “Integer Programming” were two important flagships of OR, whereas now “Communication and Energy Networks” or the more fuzzy “Machine Learning,” “Deep Learning,” and “Big Data” are in the front of the scene.

INFORMS: How does your work impact real-world scenarios? How has it impacted the field of optimization?

LASSERRE: In optimization, we have introduced relatively recent, powerful results from real algebraic geometry (namely, positivity certificates) to provide a systematic numerical scheme (a hierarchy of semidefinite programs) to solve polynomial optimization problems (at the same time P. Parrilo [11] used sums of squares decompositions for testing copositivity of a matrix and for some control applications). This hierarchy has finite convergence generically and provides the first optimality conditions for polynomial optimization (with nonconvex analogue properties of the celebrated Karush–Kuhn–Tucker (KTT) [4,6] conditions in convex optimization). In the theoretical computer science community, it has provided an important tool (a “meta-algorithm”) to analyze hardness of approximation in combinatorial optimization and prove/disprove Khot’s [5] celebrated Unique Games Conjecture (UGC).

Concerning real-world scenarios, the impact is more nuanced. The Lasserre Hierarchy has played a critical role in helping solve nonconvex problems of relatively modest size (e.g., in control) and has shown promise for solving large-scale optimization problems with structured sparsity. Optimum Power Flow problems might be the first real-world (large-scale) scenario where this methodology can outperform other approaches.

INFORMS: What are current issues, trends, and challenges in the mathematics of OR field?

LASSERRE: With an obvious bias toward optimization, “nonconvexity” in the objective and/or in the feasible set of optimization problems is an important challenge when one is looking for the global optimum, even for modest size problems. In this respect, an important theoretical challenge is to understand the power and limitation of convex relaxations, especially for hard combinatorial optimization problems. This challenge is now central in the theoretical computer science (TCS) community and has already made its way into computer science courses at some prestigious universities.

Interestingly, in addition to optimization, Fourier analysis and techniques from quantum computing may also be appropriate and are explained and discussed in such courses. OR departments should introduce similar courses; for instance, powerful positivity certificates from real algebraic geometry (and their dual facet on the K-moment problem) should be taught in graduate courses. Why? Because even if their proof is nontrivial and requires sophisticated mathematics, these positivity certificates are (i) easily understood, (ii) simple to implement, and (iii) can be used in many applications across different area. This does not happen frequently!

Another challenging problem is the pure integer programming problem (IP). Indeed, simple examples of knapsack problems (one constraint and 5-10 variables!) provided by Aardal and Lenstra [1] can be very challenging and should temper the enthusiasm (and excess of confidence) that students, and perhaps, practitioners, tend to put on “IP solvers.” Again, powerful algebraic techniques (different from that above), already used by Gomory [3] in the 1960s, can help us understand why such problems can be difficult, even if their implementation in algorithms is still limited to modest problems (and can make practitioners laugh). Surprisingly, all basic ingredients of the simplex algorithm (basis, dual vector, reduced cost) are also hidden in a beautiful formula (e.g., due to Brion & Vergne, 1997 [2]) for integration and counting on a convex polytope. In my book [10], I have tried to popularize this point of view on LP, IP, integration, and counting, but with no success at all!

Students should not be afraid of learning basic ideas of real and functional analysis, integration and measure theory, algebraic geometry, lattice points, and tools like Laplace and Fenchel transforms, Cauchy residues, and so forth.

INFORMS: What current issues, trends, and challenges do you see in operations research more generally?

LASSERRE: The goal is to help solve real-world applications. Of course, large-scale problems are still a challenge, even though we can solve problems of much larger size than in the 1960s. It would be interesting to evaluate the respective roles that algorithms and computer power played in this achievement in the past 50 years.

Some important applications (e.g., in image and signal processing) address “inverse problems,” known to be typically ill-conditioned. New theoretical results have shown that standard (read: “old”) optimization techniques, such as minimizing sparsity-inducing norms, have proven extremely useful in solving large-scale problems. This, in turn, has boosted research and renewed interest in large-scale, first-order methods for structured convex problems. Other inverse problems also appear in optimal control and robotics (e.g., to understand human motion) and are challenging optimization problems.

Solving large-scale, semidefinite programs is another challenge. The early expectations of the 1980s—that powerful interior-point methods would solve such problems—have not materialized. In contrast to LP solvers, which can solve huge size problems, and despite some progress, the size limitation of problems that can be solved by the current semidefinite programming (SDP) solvers is much more severe than for LP solvers. This is a pity because, for example, the powerful family of semidefinite convex relaxations for solving polynomial optimization problems is then limited to problems of modest size (unless sparsity can be considered).

INFORMS: Can you explain in layperson language the definition of the “Lasserre hierarchy”?

LASSERRE: The Lasserre Hierarchy consists of replacing a difficult nonconvex polynomial optimization problem (i.e., with polynomial objective function and constraints) with a nested sequence of convex relaxations of increasing size. Each convex relaxation in the hierarchy is a semidefinite program that, in principle, can be solved efficiently (in time polynomial in its input size). However, as its size increases in the hierarchy, the convex relaxation becomes increasingly more difficult to solve. Fortunately, finite convergence eventually takes place generically.

INFORMS: What is the best advice you can give to students in your field?

LASSERRE: If they intend to pursue an academic career, they should favor topics (or disciplines) they like, rather than what’s fashionable. It is important to have fun and enjoy … and it helps spur creativity! I can’t resist quoting Dimitri Bertsekas, in his 2014 Khachiyan speech, “I resisted overly lengthy distractions in practical directions that were too specialized, as well as in mathematical directions that had little visible connection to the practical world.” This strategy, which also has worked for me, is good advice for a young researcher.

INFORMS: Speaking of the Khachiyan Prize, which the Optimization Society awarded to you in 2015, what were the achievements that contributed to you winning this prize.

LASSERRE: According to the citation of the Khachiyan prize, it recognizes my previous contributions in production planning and scheduling, in Markov control processes (and Markov chains) on Borel spaces (jointly with my colleague Onésimo Hernández-Lerma from Mexico). It also recognizes my more recent work on linking LP, IP, (linear) integration, and counting problems. When looking at these problems with the appropriate “glasses” (i.e., in appropriate algebra), these four seemingly different problems are essentially the same; and the basic ingredients of LP (basis, dual vector and reduced cost) play an important role. The Laplace and Z-transform are seen as analogues of the Legendre-Fenchel transform in the max-plus algebra.

INFORMS: What recent project have you been involved in that you are proud of?

LASSERRE: In 2014, I was awarded a prestigious ERC-Advanced Grant from the European Research Council for my TAMING project. One of its main goals is to develop (or provide alternatives to) the moment-SOS hierarchy, so as to help solve difficult nonconvex problems in important applications (e.g., the Optimal Power Flow problem). Such problems are viewed as examples of the Generalized Problem of Moments, and the list of important applications is endless!

INFORMS: If you had to work on only one project for the next year, what would it be?

LASSERRE: Study additional applications of the Generalized Problem of Moments and show that the SOS-hierarchy (or some of its variants) can help solve such problems.

INFORMS: What about your career might surprise us?

LASSERRE: Perhaps that I have spent all my time at the same CNRS lab and never thought about moving elsewhere. But, this is an opportunity to emphasize how grateful I am to CNRS for providing me with a unique research environment with (almost) total freedom. In academic research, the freedom to pursue your intellectual interests is the most important feature that an employer can provide.

INFORMS: And, finally, tell us something that not many people know about you.

LASSERRE: I am a huge fan of blues and rock music as well as big, powerful motorcycles!

References

[1] Aardal K, Lenstra, AK (2004) Hard equality constrained integer knapsacks. Math. Oper. Res. 29(3):724-738.
[2] Brion M, Vergne M (1997) Residue formulae, vector partition functions and lattice points in rational polytopes. J. Amer. Math. Soc. 10(4):797-833.
[3] Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2(4):451-558.
[4] Karush W (1939) Minima of Functions of Several Variables with Inequalities as Side Constraints, MSc Dissertation, Department of Mathematics, University of Chicago (Chicago, IL).
[5] Khot S (2002) On the power of unique 2-prover 1-round games. Proc. 34th ACM Symposium on Theory of Computing.
[6] Kuhn HW, Tucker AW (1951) Nonlinear programming. Proc. 2nd Berkeley Symposium (Berkeley: University of California Press), 481–492. [7] Lasserre J (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796-817. [8] Lasserre J (2002) Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. 27(2):347-360. http://dx.doi.org/10.1287/moor.27.2.347.322. [9] Lasserre J (2007) A sum of squares approximation of nonnegative polynomials. SIAM Rev. 49(4):651-669. [10] Lasserre J (2009) Linear and Integer Programming vs Linear Integration and Counting: A Duality Viewpoint (Springer, New-York). [11] Parrilo P (2000) Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology (Pasadena, CA).

For comments or more information about this series, please contact the Managing Editor, Stephanie Dean.