Minimizing Quadratic Functions in Constant Time

Code

• github.com/hayasick/CTOQ
  none★ 3

Abstract

A sampling-based optimization method for quadratic functions is proposed. Our method approximately solves the following n-dimensional quadratic minimization problem in constant time, which is independent of n: z^*=_v R^nv, A v + nv, diag(d)v + nb, v, where A R^n n is a matrix and d,b R^n are vectors. Our theoretical analysis specifies the number of samples k(, ) such that the approximated solution z satisfies |z - z^*| = O( n^2) with probability 1-. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.

Reproductions