Combinatorial Algorithm for Quadratic Programs with Laplacian Structure
Abstract
An algorithm is presented that uses a mostly combinatorial approach
to solve a family of convex quadratic programs over box
constraints. It is proved that for convex programs with the required
structure, the algorithm converges in a finite number of
iterations. Moreover, each iteration requires, at most, one
function evaluation. On synthetic problems with thousands of
variables, our implementation determines the optimal solution in
seconds.