Booth Id:
SOFT044
Category:
Systems Software
Year:
2024
Finalist Names:
Wei, Michelle (School: The Harker School)
Abstract:
A fundamental class of problems in mathematical optimization is second-order cone programming (SOCP), which provides a generalized framework to solve problems in a wide range of fields.
While progress has been made in other areas of convex optimization, advancement in SOCP has been slow in the last 30 years due to the computational costs involved with high-dimensional constraints. To address this challenge, this research made several key innovations. First, because it is highly computationally expensive to compute the exact search direction in the algorithm at each iteration, I developed a technique to maintain an approximate solution, significantly lowering the computational cost. However, high-dimensional constraints still create a bottleneck even with this approximation technique. To overcome this, I designed a novel method to decompose large constraints, converting the problem into another SOCP with smaller constraints. This key step greatly speeds up the runtime, and it is also a significant theoretical contribution that may be applied to other forms of conic programming. Combining approximation techniques with cone-splitting, the new algorithm I designed outperforms the previous best SOCP algorithm by a factor of a square root of the number of constraints. I mathematically proved that the new approach converges to the optimal solution in matrix multiplication time, reaching the theoretical limit.
I developed and tested a software SOCP solver, laying the groundwork for researchers to build upon theoretical advancements. The new solution sets the stage for significant performance improvement across various fields, such as machine learning, operations research, energy, transportation, and finance.