Solving Second-Order Cone Programs in Matrix Multiplication Time
ISEF · 2024 Systems Software First Award
Overview
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.
Awards (5)
- First Award of $5,000 $5,000
- Regeneron Young Scientist Awards
- The Scientific and Technological Research Council of Türkiye TUBITAK: 1st Prize Award
- China Association for Science and Technology (CAST): Award of $1,200 $1,200
- National Security Agency Research Directorate : First Place Award “Principles of Security and Privacy”
Competition history
- ISEF 2024
Resources
Related projects
ISEF · 2022
Fast and Furious: Designing an Ultra-Efficient Hybrid Matrix Multiplication Algorithm
ISEF · 2025
Geometric Hyperplane Intersection Solver: A Matrix-Inversion-Free Framework Enhanced by Quantum and Evolutionary Algorithms
CWSF · 2026
HybridCSP
ISEF · 2019
An Optimized Multigrid Algorithm for Enabling Efficient Physical Simulations on Realistic Geometries
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair