Complexity of Weighted Approximation over

We study approximation of univariate functions defined over the reals. We assume that the rth derivative of a function is bounded in a weighted L_p norm with a weight ψ. Approximation algorithms use the values of a function and its derivatives up to order r−1. The worst case error of an algorithm is defined in a weighted L_q norm with a weight ρ. We study the worst case (information) complexity of the weighted approximation problem, which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weights ψ and ρ, as well as the parameters r, p, and q for the weighted approximation problem to have finite complexity. We also provide conditions which guarantee that the complexity of weighted approximation is of the same order as the complexity of the classical approximation problem over a finite interval. Such necessary and sufficient conditions are also provided for a weighted integration problem since its complexity is equivalent to the complexity of the weighted approximation problem for q=1.     

Worst case tractability of linear problems in the presence of noise: Linear information

We study the worst case tractability of multivariate linear problems defined on separable Hilbert spaces. Information about a problem instance consists of noisy evaluations of arbitrary bounded linear functionals, where the noise is either deterministic or random. The cost of a single evaluation depends on its precision and is controlled by a cost function. We establish mutual interactions between tractability of a problem with noisy information, the cost function, and tractability of the same problem, but with exact information.     

An informational approach to the global optimization of expensive-to-evaluate functions

In many global optimization problems motivated by engineering applications, the number of function evaluations is severely limited by time or cost. To ensure that each evaluation contributes to the localization of good candidates for the role of global minimizer, a sequential choice of evaluation points is usually carried out. In particular, when Kriging is used to interpolate past evaluations, the uncertainty associated with the lack of information on the function can be expressed and used to compute a number of criteria accounting for the interest of an additional evaluation at any given point. This paper introduces minimizers entropy as a new Kriging-based criterion for the sequential choice of points at which the function should be evaluated. Based on stepwise uncertainty reduction, it accounts for the informational gain on the minimizer expected from a new evaluation. The criterion is approximated using conditional simulations of the Gaussian process model behind Kriging, and then inserted into an algorithm similar in spirit to the Efficient Global Optimization (EGO) algorithm. An empirical comparison is carried out between our criterion and expected improvement, one of the reference criteria in the literature. Experimental results indicate major evaluation savings over EGO. Finally, the method, which we call IAGO (for Informational Approach to Global Optimization), is extended to robust optimization problems, where both the factors to be tuned and the function evaluations are corrupted by noise.     

Asymptotic near optimality of the bisection method

Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1] such thatf(0)0 andf(1)0. It is known that the error of the bisection method usingn function evaluations is 2^–(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is forn fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values.One may then ask whether bisection is nearly optimal in theasymptotic worst case sense, that is,possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.     

Average case complexity of linear multivariate problems I. Theory

We study the average case complexity of linear multivariate problems, that is, the approximation of continuous linear operators on functions of d variables. The function spaces are equipped with Gaussian measures. We consider two classes of information. The first class Λ^std consists of function values, and the second class Λ^all consists of all continuous linear functionals. Tractability of a linear multivariate problem means that the average case complexity of computing an ε-approximation is O((1/)^p) with p independent of d. The smallest such p is called the exponent of the problem. Under mild assumptions, we prove that tractability in Λ^all is equivalent to tractability in Λ^std and that the difference of the exponents is at most 2. The proof of this result is not constructive. We provide a simple condition to check tractability in Λ^all. We also address the issue of how to construct optimal (or nearly optimal) sample points for linear multivariate problems. We use relations between average case and worst case settings. These relations reduce the study of the average case to the worst case for a different class of functions. In this way we show how optimal sample points from the worst case setting can be used in the average case. In Part II we shall apply the theoretical results to obtain optimal or almost optimal sample points, optimal algorithms, and average case complexity functions for linear multivariate problems equipped with the folded Wiener sheet measure. Of particular interest will be the multivariate function approximation problem.     

Gradient Estimation Using Lagrange Interpolation Polynomials

We use Lagrange interpolation polynomials to obtain good gradient estimations. This is e.g. important for nonlinear programming solvers. As an error criterion, we take the mean squared error, which can be split up into a deterministic error and a stochastic error. We analyze these errors using N-times replicated Lagrange interpolation polynomials. We show that the mean squared error is of order if we replicate the Lagrange estimation procedure N times and use 2d evaluations in each replicate. As a result, the order of the mean squared error converges to N ⁻¹ if the number of evaluation points increases to infinity. Moreover, we show that our approach is also useful for deterministic functions in which numerical errors are involved. We provide also an optimal division between the number of gridpoints and replicates in case the number of evaluations is fixed. Further, it is shown that the estimation of the derivatives is more robust when the number of evaluation points is increased. Finally, test results show the practical use of the proposed method. We thank Jack Kleijnen, Gül Gürkan, and Peter Glynn for useful remarks on an earlier version of this paper. We thank Henk Norde for the proof of Lemma 2.2.     

On novel classes of iterative methods for solving nonlinear equations

In this paper, we establish two new classes of derivative-involved methods for solving single valued nonlinear equations of the form f(x) = 0. The first contributed two-step class includes two evaluations of the function and one of its first derivative where its error analysis shows a fourth-order convergence. Next, we construct a three-step high-order class of methods including four evaluations per full cycle to achieve the seventh-order of convergence. Numerical examples are included to re-verify the theoretical results and moreover put on show the efficiency of the new methods from our classes.     

Linear information versus function evaluations for -approximation

We study algorithms for the approximation of functions, the error is measured in an L₂ norm. We consider the worst case setting for a general reproducing kernel Hilbert space of functions. We analyze algorithms that use standard information consisting in n function values and we are interested in the optimal order of convergence. This is the maximal exponent b for which the worst case error of such an algorithm is of order n^-b.Let p be the optimal order of convergence of all algorithms that may use arbitrary linear functionals, in contrast to function values only. So far it was not known whether p>b is possible, i.e., whether the approximation numbers or linear widths can be essentially smaller than the sampling numbers. This is (implicitly) posed as an open problem in the recent paper [F.Y. Kuo, G.W. Wasilowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory, to appear] where the authors prove that implies . Here we prove that the case and b=0 is possible, hence general linear information can be exponentially better than function evaluation. Since the case is quite different, it is still open whether b=p always holds in that case.     

Average errors for zero finding: Lower bounds for smooth or monotone functions

Summary We study zero finding for functions fromC ^r ([0, 1]) withf(0) f(1) < 0 and for monotone functions fromC([0, 1]). We show that a lower bound ⁿ with a constant holds for the average error of any method usingn function or derivative evaluations. Here the average is defined with respect to conditionalr-fold Wiemer measures or Ulam measures, and the error is understood in the root or residual sense. As in the worst case, we therefore cannot obtain superlinear convergence even for classes of smooth functions which have only simple zeros.     

A Hausdorff-type distance,a directional derivative of a set-valued map and applications in set optimization

Abstract

In this paper, we follow Kuroiwa’s set approach in set optimization, which proposes to compare values of a set-valued objective map F with respect to various set order relations. We introduce a Hausdorff-type distance relative to an ordering cone between two sets in a Banach space and use it to define a directional derivative for F. We show that the distance has nice properties regarding set order relations and the directional derivative enjoys most properties of the one of a scalar single-valued function. These properties allow us to derive necessary and/or sufficient conditions for various types of maximizers and minimizers of F.     

A cubically convergent Newton-type method under weak conditions

Under weak conditions, we present an iteration formula to improve Newton's method for solving nonlinear equations. The method is free from second derivatives, permitting f^′(x)=0 in some points and per iteration it requires two evaluations of the given function and one evaluation of its derivative. Analysis of convergence demonstrates that the new method is cubically convergent. Some numerical examples illustrate that the algorithm is more efficient and performs better than classical Newton's method.     

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.     

A univariate global search working with a set of Lipschitz constants for the first derivative

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f ′(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. Algorithms working with a number of Lipschitz constants for f ′(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm. This research was supported by the RFBR grant 07-01-00467-a and the grant 4694.2008.9 for supporting the leading research groups awarded by the President of the Russian Federation.     

Derivative free multipoint iterative methods for simple and multiple roots

A one-parameter family of derivative free multipoint iterative methods of orders three and four are derived for finding the simple and multiple roots off(x)=0. For simple roots, the third order methods require three function evaluations while the fourth order methods require four function evaluations. For multiple roots, the third order methods require six function evaluations while the fourth order methods require eight function evaluations. Numerical results show the robustness of these methods.     

Exponential lower bounds for finding Brouwer fix points

The computation of Brouwer fixed points is a central tool in economic modeling. Although there have been several algorithms for computing a fixed point of a Brouwer map, starting with Scarf's algorithm of 1965, the question of worst-case complexity was not addressed. It has been conjectured that Scarf's algorithm has typical behavior that is polynomial in the dimension. Here we show that any algorithm for computing the Brouwer fixed point of a function based on function evaluations (a class that includes all known general purpose algorithms) must in the worst case perform a number of function evaluations that is exponential in both the number of digits of accuracy and the dimension. Our lower bounds are very close to the known upper bounds.     

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.     

Iterative method generated by inverse interpolation with additional evaluations

An improvement of the iterative methods based on one point iteration function, with or without memory, using n points with the same amount of information in each point and generated by the inverse polynomial interpolation is given. The adaptation of the strategy presented here gives a new iteration function with a new evaluation of the function which increases the local order of convergence dramatically. This method is generalized to r evaluations of the function. This method for the computation of solutions of nonlinear equations is interesting when it is necessary to get high precision because it provides a lower cost when we use adaptive multi-precision arithmetics. AMS subject classification 65H05     

Complexity of Weighted Approximation over

We study approximation of multivariate functions defined over ^d. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms (f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted L_q norm with a weight function ρ. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weight ρ and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q=1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over was studied.     

Regularity of the Level Set Flow

We showed earlier that the level set function of a monotonic advancing front is twice differentiable everywhere with bounded second derivative and satisfies the equation classically. We show here that the second derivative is continuous if and only if the flow has a single singular time where it becomes extinct and the singular set consists of a closed C¹ manifold with cylindrical singularities. © 2017 Wiley Periodicals, Inc.     

Worst Case Complexity of Problems with Random Information Noise

We study the worst case complexity of solving problems for which information is partial and contaminated by random noise. It is well known that if information is exact then adaption does not help for solving linear problems, i.e., for approximating linear operators over convex and symmetric sets. On the other hand, randomization can sometimes help significantly. It turns out that for noisy information, adaption may lead to much better approximations than nonadaption, even for linear problems. This holds because, in the presence of noise, adaption is equivalent to randomization. We present sharp bounds on the worst case complexity of problems with random noise in terms of the randomized complexity with exact information. The results obtained are applied to thed-variate integration andL_∞-approximation of functions belonging to Hölder and Sobolev classes. Information is given by function evaluations with Gaussian noise of variance σ². For exact information, the two problems are intractable since the complexity is proportional to (1/ε)^qwhereqgrows linearly withd. For noisy information the situation is different. For integration, the ε-complexity is of order σ²/ε²as ε goes to zero. Hence the curse of dimensionality is broken due to random noise. for approximation, the complexity is of order σ²(1/ε)^q+2ln(1/ε), and the problem is intractable also with random noise.