Combinatorial Algorithm for Quadratic Programs with Laplacian Structure
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Utilitas Mathematica
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.
Description
Keywords
Optimization