In this paper we describe methods for computing smoothing and near-interpolatory (variational) subdivided surfaces, including those surfaces that meet data to within prescribed tolerances. The theory is based on standard results from constrained optimization combined with existing variational interpolatory subdivision schemes. The particular functional considered later in the paper is a discretization of the thin-plate spline functional. This paper considers the characterization and computational algorithms – numerical and smoothness issues will be deferred to future work.