A new criterion for tractability of multivariate problems

Tractability of multivariate problems studies their complexity with respect to the number of variables, d$d$, and the accuracy of the solution ε$\epsilon$. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy.     

On tractability of approximation in special function spaces

We consider approximation problems for a special space of d$d$ variate functions. We show that the problems have small number of active variables, as it has been postulated in the past using concentration of measure arguments. We also show that, depending on the norm for measuring the error, the problems are strongly polynomially or quasi-polynomially tractable even in the model of computation where functional evaluations have the cost exponential in the number of active variables.     

Uniform weak tractability of multivariate problems with increasing smoothness

We study d$d$-variate approximation problems with varying regularity with respect to successive variables. The varying regularity is described by a sequence of real numbers _{rk}k∈N${\left\{r_k\right\}}_{k\in \mathbb{N}}$ satisfying

0≤_r1≤_r2≤_r3≤?.$0\le r_1\le r_2\le r_3\le ?\text{.}$

We mainly consider algorithms that use finitely many continuous linear functionals. In the worst case setting we study approximation problems defined over suitable Korobov and Sobolev spaces. In the average case setting we study approximation problems defined over the space of continuous functions C([0,1]^d)$C\left({[0,1]}^d\right)$ equipped with a zero-mean Gaussian measure whose covariance operator is given by an Euler or Wiener integrated process. We establish necessary and sufficient conditions on uniform weak tractability of those problems in terms of their regularity parameters _{rk}k∈N${\left\{r_k\right\}}_{k\in \mathbb{N}}$.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

A note on the complexity and tractability of the heat equation

We wish to solve the heat equation u_t=Δu-qu in I^d×(0,T), where I is the unit interval and T is a maximum time value, subject to homogeneous Dirichlet boundary conditions and to initial conditions u(·,0)=f over I^d. We show that this problem is intractable if f belongs to standard Sobolev spaces, even if we have complete information about q. However, if f and q belong to a reproducing kernel Hilbert space with finite-order weights, we can show that the problem is tractable, and can actually be strongly tractable.     

On the worst case complexity of potential reduction algorithms for linear programming

There are several classes of interior point algorithms that solve linear programming problems in O(√nL) iterations. Among them, several potential reduction algorithms combine both theoretical (O(√nL) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(√nL) is tight for several potential reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least Θ(√nL) iterations to find an optimal solution. The research of the author was partially supported by a Presidential Young Investigator Award DDM-9158118 with matching funds from Draper Laboratory.     

Generalized Tractability for Multivariate Problems Part II: Linear Tensor Product Problems, Linear Information, and Unrestricted Tractability

We continue the study of generalized tractability initiated in our previous paper “Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information”, J. Complex. 23:262–295, 2007. We study linear tensor product problems for which we can compute linear information which is given by arbitrary continuous linear functionals. We want to approximate an operator S _d given as the d-fold tensor product of a compact linear operator S ₁ for d=1,2,…, with ‖S ₁‖=1 and S ₁ having at least two positive singular values. Let n(ε,S _d ) be the minimal number of information evaluations needed to approximate S _d to within ε∈[0,1]. We study generalized tractability by verifying when n(ε,S _d ) can be bounded by a multiple of a power of T(ε ⁻¹,d) for all (ε ⁻¹,d)∈Ω⊆[1,∞)×ℕ. Here, T is a tractability function which is non-decreasing in both variables and grows slower than exponentially to infinity. We study the exponent of tractability which is the smallest power of T(ε ⁻¹,d) whose multiple bounds n(ε,S _d ). We also study weak tractability, i.e., when . In our previous paper, we studied generalized tractability for proper subsets Ω of [1,∞)×ℕ, whereas in this paper we take the unrestricted domain Ω ^unr=[1,∞)×ℕ. We consider the three cases for which we have only finitely many positive singular values of S ₁, or they decay exponentially or polynomially fast. Weak tractability holds for these three cases, and for all linear tensor product problems for which the singular values of S ₁ decay slightly faster than logarithmically. We provide necessary and sufficient conditions on the function T such that generalized tractability holds. These conditions are obtained in terms of the singular values of S ₁ and mostly asymptotic properties of T. The tractability conditions tell us how fast T must go to infinity. It is known that T must go to infinity faster than polynomially. We show that generalized tractability is obtained for T(x,y)=x ^1+ln y . We also study tractability functions T of product form, T(x,y)=f ₁(x)f ₂(x). Assume that a _i =lim inf  _x→∞(ln ln f _i (x))/(ln ln x) is finite for i=1,2. Then generalized tractability takes place iff

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

Complexity of multilinear problems in the worst case setting

This is the first of two papers on multilinear problems, and it is devoted to the worst case setting. A second paper will analyze the average case setting. We show how to reduce the analysis of multilinear problems to linear subproblems. In particular, it is proven that adaption can help by a factor of at most k and k-linear problems. The error of multilinear algorithms is analyzed and optimality properties of spline algorithms for the Hilbert case are established. We illustrate our analysis with an example of a multilinear problem from signal processing.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

The curvature integral and the complexity of linear complementarity problems

In this paper, we propose a predictor—corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date.Corresponding author.This author's research was partially supported by Research Grant No. RP920068, National University of Singapore, Singapore.