2025/12/09 by Salloum, Hadi, Hildebrand, Roland, Nguyen, Nhat Trung +4
Computer Science · Mathematics · Engineering · #Stochastic Gradient Optimization Techniques #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques
paper · doi:10.48550/arxiv.2512.08852
We present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solving the conventional semi-definite programming (SDP) relaxation, which is computationally expensive, we employ a difference-of-convex (DC) optimization framework to efficiently approximate the SDP solution. The DC optimization produces candidate vectors that are then used within the GW randomized rounding scheme to generate high-quality binary solutions. Furthermore, we perform direct expectation minimization over manifolds of matrices with limited rank to further enhance the solution quality. Our method is benchmarked on real-world QUBO instances, including inverse kinematics problems, and compared against state-of-the-art solvers, such as quantum-inspired algorithms, demonstrating competitive approximation guarantees alongside substantial computational gains.