Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs
For researchers using gradient-based methods to solve combinatorial optimization problems, this work provides theoretical guarantees that prevent spurious local minima, making differentiable optimization a reliable local solver.
The paper identifies structural conditions on quadratic penalties that guarantee every local minimizer of the relaxed QUBO problem is binary and feasible, and demonstrates that gradient-based methods like projected gradient descent and Adam can reliably solve several combinatorial problems (e.g., open-pit mining, 0-1 knapsack, traveling salesman) under these conditions.
Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relaxed problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, 0--1 knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.