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 honour in the field of Computational Mathematical Optimisation. This is the first time an Asian team wins the Beale-Orchard-Hays Prize. The award is presented once every three years by Mathematical Optimisation Society in memory of Martin Beale and William Orchard-Hays, pioneers in computational mathematical optimisation. Previous winners include world leading figures in computational optimisation such as Professor Stephen P. Boyd and Professor William J. Cook.

Mathematical optimisation is widely used in many fields, for example, vast majority of the models in machine learning are essentially optimisation 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 optimisation. The prize was awarded for a paper and the software SDPNAL+ that it refers.

In the photo, from left to right: Dr. Michael Grant, prize jury chair; Dr. Liuqin Yang; Professor Defeng Sun; Professor Kim-Chuan Toh; Professor Karen Aardal, chair of Mathematical Optimisation Society. In the photo, from left to right: Dr. Michael Grant, prize jury chair; Dr. Liuqin Yang; Professor Defeng Sun; Professor Kim-Chuan Toh; Professor Karen Aardal, chair of Mathematical Optimization Society.

The software is designed for solving semidefinite programming (SDP) but the optimisation methods presented in the paper can be applied to more general mathematical optimisation problems. SDP is an important subfield of mathematical optimisation and its applications are growing rapidly. Many practical problems in operations research and machine learning can be modelled or approximated as SDP problems.

Traditional optimisation 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 optimisation 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 optimisation problems, e.g., allocation optimisation, carpool optimisation and logistics optimisation; and a lot of large-scale machine learning problems, e.g., supply and demand forecasting. The optimisation 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 optimisation 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 maximise the system efficiency and user experience. The allocation efficiency can be increased to dozens of times by using the optimisation 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 optimisation techniques can accelerate the allocation algorithms to run hundreds of times faster.

Prize Citation

The text of the award citation is below:

Liuqin Yang, Defeng Sun and Kim-Chuan Toh, SDPNAL+: a majorised 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 optimisation and the winner of the 2017 INFORMS Optimisation Society Farkas Prize for his fundamental contributions to the theory, practice, and application of convex optimisation. His current research focuses on designing efficient algorithms and software packages for large-scale machine learning problems and matrix optimisation problems.

Professor Defeng Sun is Chair Professor of Applied Optimisation and Operations Research, The Hong Kong Polytechnic University. He is one of the world’s leading figures in semismooth Newton methods for optimisation. He currently focuses on building up the new field of matrix optimisation and establishing the foundation for the next generation methodologies for big data optimisation and applications.

Dr. Liuqin Yang is Senior Data Scientist at Grab and a computational optimisation 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 optimisation journals. Currently, he works on big data optimisation, machine learning and business applications in data science.