Deeper Dive
A fundamental class of problems in mathematical optimization is second-order cone programming (SOCP). The widespread applications of SOCP extend to various areas, such as machine learning and operations research, spanning several industries, including information technology, finance, energy, and transportation. SOCP provides a generalized representation of several well-known convex optimization problems, including linear programs, convex quadratic programs, and quadratically constrained convex quadratic programs. Through a literature review, I discovered that a major breakthrough in convex optimization occurred in 1984 when Karmarkar introduced the Interior Point Method (IPM). This method iteratively computes a sequence of interior points within the problem space to reach the optimal solution through a Central Path. A decade later, in 1994, Nesterov and Nemirovski extended IPM to SOCP, reducing the complexity to O(n^(ω+0.5)), where n denotes the input size and ω represents the matrix multiplication exponent. While advancements have recently been made in several areas of convex optimization, progress in SOCP has remained slow in the past 30 years because of the complexity of high-dimensional constraints and the heavy computation cost associated with them.
As a generalization of Linear Programming (LP), it is natural to apply recent advancements in LP frameworks to solve SOCPs. However, the breakthroughs in IPM for LP are underpinned by inverse maintenance techniques, which take advantage of the block-diagonal structure of the Hessian matrix to simplify per-iteration updates into solving lower-dimensional linear systems. Making similar improvements to SOCP is challenging. Given the inherent nature of SOCPs, the sizes of the block matrices in the Hessian can vary significantly. Even updating a single high-dimension block does not change the time complexity. To address these challenges, my research designed several runtime-reducing strategies to produce an efficient new SOCP algorithm and mathematically proved its worst-case runtime as O(n^ω).
Mathematics is fundamentally about problem-solving, and the field of optimization focuses on solving problems efficiently. My research on Second-Order Cone Programming (SOCP) problems, an important topic within convex programming, has a wide range of applications: it can help optimize healthcare logistics, schedule public transportation, and distribute electrical power more effectively. By advancing the understanding and speed of solving these common and critical problems, my work can be used to improve the efficiency and sustainability of essential services that impact the lives of many people.