Minimizing Quadratic Functions in Constant Time

2016/08/25 by Hayashi, Kohei, Yoshida, Yuichi
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1608.07179

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

Related

• A Polynomial-Time Algorithm for Unconstrained Binary Quadratic\n Optimization
• Exact algorithms for quadratic optimization over roots of unity
• An Algorithm for Unconstrained Quadratically Penalized Convex Optimization
• On Minimization of a Quadratic Binary Functional
• A Flexible Algorithmic Framework for Strictly Convex Quadratic Minimization