An operator theoretic framework for analysis of large-scale quadratic programming

One of the fundamental problems in the area of large-scale constrained optimization problems is the study of the locality features of spatially distributed optimization problems, which can motivate the development of fast and well-conditioned distributed algorithms. We study the spatial locality features of large-scale, possibly infinite-dimensional, quadratic programming (QP) problems with linear inequality constraints. Examples of such problems include receding horizon control of spatially distributed linear systems with input and state constraints, optimal estimation of a parameter based on data collected in a sensor network, manifold learning of a large set of data in machine learning, etc. We propose a new approach for analysis of large-scale QP problems by blending tools from duality theory with operator theory. The class of spatially decaying matrices is introduced to capture couplings between optimization variables in the cost function and constraints. We show that the optimal solution of a large-scale convex QP is piece-wise affine- represented as convolution sums. More importantly, we prove that the kernel of each convolution sum decays in the spatial domain at a rate proportional to the inverse of the corresponding coupling function of the optimization problem. Simulations results are provided to verify our theoretical results.