Browsing by Author "Shi, Peter"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Combinatorial Algorithm for Quadratic Programs with Laplacian Structure
    (Utilitas Mathematica, 2016) Kruk, Serge; Nierman, Ryan; Shi, Peter
    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.