Minimizing Quadratic Functions in Constant Time

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^*=minv ∈ ℝnlanglev, A vrangle + nlanglev, diag(d)vrangle + nlangleb, vrangle, where A ∈ ℝn × n is a matrix and d,b ∈ ℝn are vectors. Our theoretical analysis specifies the number of samples k(δ, ε) such that the approximated solution z satisfies |z - z^*| = O(ε n2) with probability 1-δ. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.