The Beale-Orchard-Hays Prize
Grab Senior Data Scientist Dr. Liuqin Yang (along with Professor Defeng Sun and Professor Kim-Chuan Toh) wins the 2018 Beale-Orchard-Hays Prize, the highest honor in the field of Computational Mathematical Optimization. This is the first time an Asian team wins the Beale-Orchard-Hays Prize. The award is presented once every three years by Mathematical Optimization Society in memory of Martin Beale and William Orchard-Hays, pioneers in computational mathematical optimization. Previous winners include world leading figures in computational optimization such as Professor Stephen P. Boyd and Professor William J. Cook.
Mathematical optimization is widely used in many fields, for example, vast majority of the models in machine learning are essentially optimization problems.
The award-winning paper and software
The award was presented at the opening ceremony of the 23rd International Symposium for Mathematical Programming (ISMP) in France in July 2018. ISMP takes place every three years and is the flagship conference in the field of mathematical optimization. The prize was awarded for a paper and the software SDPNAL+ that it refers.
The software is designed for solving semidefinite programming (SDP) but the optimization methods presented in the paper can be applied to more general mathematical optimization problems. SDP is an important subfield of mathematical optimization and its applications are growing rapidly. Many practical problems in operations research and machine learning can be modeled or approximated as SDP problems.
Traditional optimization methods can only solve small and medium scale (say, matrix dimension is less than 2000 and the number of constraints is less than 5000) SDP. Fortunately, large-scale SDP can be solved efficiently by SDPNAL+ now. Numerical experiments in the paper and other benchmark tests show that SDPNAL+ is a state-of-the-art solver for large-scale SDP and it is the only viable software to solve many large-scale SDPs at present. The largest SDP problem that is solved has matrix dimension 9261 and the number of constraints more than 12 million, which boosts the solvable scale to thousands of times. In particular, the prize jury chair Dr. Michael Grant presented a concrete example shared by the nominator. It takes 122 hours for the traditional solver to solve a problem in a cluster with 56 cores CPU and 128 GPUs while SDPNAL+ solves it within 1.5 hours in a normal desktop PC.
Applications in data science and Grab
The novel technology of the software SDPNAL+ also contributes to data science and AI (Artificial Intelligence) community. Mathematical optimization is the essential foundation of machine learning and AI. Many large-scale machine learning problems can be solved by the algorithms used in the software, for example, Lasso problems, support vector machine and deep learning. Consequently, the novel technology can be applied to voice search, voice-activated assistants, face perception, automatic translation, cancer detection, and so on.
Grab is a leading technology company that offers ride-hailing, ride sharing and logistics services in Southeast Asian. It is also a data-driven company and millions of rides are booked on the app daily. Grab needs to solve a lot of large-scale optimization problems, e.g., allocation optimization, carpool optimization and logistics optimization; and a lot of large-scale machine learning problems, e.g., supply and demand forecasting. The optimization technology has been used in Grab to speed up the key algorithms to hundreds of times faster and achieve a cost reduction of millions of dollars.
A significant project we are working on in Grab is allocation optimization system, which matches the passengers and the drivers in an optimal way. The drivers are always moving, and we need to choose the optimal driver for each passenger based on distance and many other factors to maximize the system efficiency and user experience. The allocation efficiency can be increased to dozens of times by using the optimization techniques. Thousands of requests are booked in Grab each minute on average and we need to allocate the bookings every few seconds by dozens of millions of computations. The computational optimization techniques can accelerate the allocation algorithms to run hundreds of times faster.
The text of the award citation is below:
Liuqin Yang, Defeng Sun and Kim-Chuan Toh, SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Mathematical Programming Computation, 7 (2015), 331-366.
Biography of the winners
Professor Kim-Chuan Toh is a Provost’s Chair Professor at the Department of Mathematics, National University of Singapore (NUS). He is one of the world’s leading figures in computational optimization and the winner of the 2017 INFORMS Optimization Society Farkas Prize for his fundamental contributions to the theory, practice, and application of convex optimization. His current research focuses on designing efficient algorithms and software packages for large-scale machine learning problems and matrix optimization problems.
Professor Defeng Sun is Chair Professor of Applied Optimization and Operations Research, The Hong Kong Polytechnic University. He is one of the world’s leading figures in semismooth Newton methods for optimization. He currently focuses on building up the new field of matrix optimization and establishing the foundation for the next generation methodologies for big data optimization and applications.
Dr. Liuqin Yang is Senior Data Scientist at Grab and a computational optimization expert. He obtained his PhD degree in Mathematics from NUS in 2015 under the direction of Professor Toh and Professor Sun. The award-winning paper and software SDPNAL+ is one of his PhD research topics. He has published three papers in the top optimization journals. Currently, he works on big data optimization, machine learning and business applications in data science.