Combinatorial Algorithm for Quadratic Programs with Laplacian Structure

Date

2016

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

Citation