Combinatorial Algorithm for Quadratic Programs with Laplacian Structure
Description
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.
Date
2016
Subject
Optimization