AM Seminar: Fast and Parallelizable Numerical Algorithm for Solving Large-Scale Conic Optimization Problems

Muhammad Adil
Research Scientist
Palo Alto Research Center
Location
Virtual

Join us on Zoom: https://ucsc.zoom.us/j/97275336645?pwd=YjgvanV6RmZHdjY5dVUxTUJua0FrZz09

Description: Conic optimization has a wide range of applications in the areas of power systems, machine learning, operation research, and portfolio optimization. Interior point method (IPM) is the method of choice for solving conic problems and commercial solvers such as CPLEX, GUROBI, and MOSEK use IPM as their default algorithm. Although IPMs are robust and theoretically sound, they do not scale well for very large conic optimization programs. In this work, a parallelizable first-order numerical algorithm is proposed that is capable of solving large-scale conic optimization problems on distributed platforms such as graphics processing unit (GPU) with orders-of-magnitude time improvement. First-order methods are notorious for slow tail convergence and dealing with ill-conditioned problems. To remedy the slow convergence problem of first order methods, an adaptive conditioning heuristic is proposed to achieve a higher accuracy comparable to that of interior point methods. In order to exploit the sparsity in large scale problems, a matrix-free algorithm is proposed which computes the sparse factors only in first iterations and then reuse these factors in subsequent iterations. In comparison to existing matrix decomposition techniques such as LDL and QR decomposition, this decomposition technique is easy-to-compute and computationally efficient. Numerical experiments on a wide range of large-scale conic optimization problems demonstrate the scalability and computational advantages of the proposed algorithm compared to commercial and open-source state-of-the-art solvers. The proposed algorithm is applied to design a highly scalable and computationally efficient swarm motion planning tool for missions that involve swarm of space vehicles.

Speaker bio: Muhammad Adil is currently working as a research scientist at the Palo Alto Research Center (PARC). He earned his Ph.D. degree in electrical engineering at the University of Texas at Arlington in 2021. He received his B.S and M.S degrees in electrical engineering from the University of Engineering and Technology and Pakistan Institute of Engineering and Applied Sciences in 2012 and 2014. He worked as a summer intern for MathWorks and Boston Scientific Corporation during his PhD. His research interests include developing numerical algorithms for solving large scale optimization problems.