Combinatorial Algorithm for Quadratic Programs with Laplacian Structure
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.
Show full item record