Tractability of quasilinear problems. I: General results (Q880024)

Many problems in computational practice require to approximate operators \(S_d\) defined over classes of functions \(g\) of \(d\) variables, where \(d\) may be very large. One of the main goals of tractability studies is to prove that the minimal number of evaluations of \(g\) needed to approximate \(S_d(g)\) to within \(\varepsilon\) is polynomial in \(\varepsilon^{-1}\) and \(d\). In the most papers of this study it is assumed that \(S_d\) is linear. In this paper the authors extend this study to certain quasilinear multivariate problems. Namely, they wish to approximate \(S_d(f,g)\), where \(f\) and \(g\) are \(d\)-variate functions within a class \(\Lambda\), \(S_d(f,g)\) depends linearly on \(f\) and satisfies a Lipschitz condition with respect to both \(f\) and \(g\). Let card(\(\varepsilon,S_d,\Lambda\)) denote the minimal number of evaluations from the class \(\Lambda\) needed to find an \(\varepsilon\)-approximation of the operator \(S_d\). The problem is tractable if card(\(\varepsilon,S_d,\Lambda\)) depends polynomially on \(\varepsilon^{-1}\) and \(d\), and is strongly tractable if \(\varepsilon^{-1}\) bounded independently of \(d\) by a polynomials in \(\varepsilon^{-1}\). For product weights and finite-order weights, the authors prove tractability and strong tractability of general quasilinear problems, under appropriate assumptions. [For part II see Math. Comput. 76, No. 258, 745--776 (2007; Zbl 1135.65006).]