Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting

In this paper we discuss Sobolev bounds on functions that vanish at scattered points in a bounded, Lipschitz domain that satisfies a uniform interior cone condition. The Sobolev spaces involved may have fractional as well as integer order. We then apply these results to obtain estimates for continuous and discrete least squares surface fits via radial basis functions (RBFs). These estimates include situations in which the target function does not belong to the native space of the RBF.

     

Approximation in rough native spaces by shifts of smooth kernels on spheres

Within the conventional framework of a native space structure, a smooth kernel generates a small native space, and “radial basis functions” stemming from the smooth kernel are intended to approximate only functions from this small native space. Therefore their approximation power is quite limited. Recently, Narcowich et al. (J. Approx. Theory 114 (2002) 70), and Narcowich and Ward (SIAM J. Math. Anal., to appear), respectively, have studied two approaches that have led to the empowerment of smooth radial basis functions in a larger native space. In the approach of [NW], the radial basis function interpolates the target function at some scattered (prescribed) points. In both approaches, approximation power of the smooth radial basis functions is achieved by utilizing spherical polynomials of a (possibly) large degree to form an intermediate approximation between the radial basis approximation and the target function. In this paper, we take a new approach. We embed the smooth radial basis functions in a larger native space generated by a less smooth kernel, and use them to approximate functions from the larger native space. Among other results, we characterize the best approximant with respect to the metric of the larger native space to be the radial basis function that interpolates the target function on a set of finite scattered points after the action of a certain multiplier operator. We also establish the error bounds between the best approximant and the target function.     

Multiscale analysis in Sobolev spaces on bounded domains

We study a multiscale scheme for the approximation of Sobolev functions on bounded domains. Our method employs scattered data sites and compactly supported radial basis functions of varying support radii at scattered data sites. The actual multiscale approximation is constructed by a sequence of residual corrections, where different support radii are employed to accommodate different scales. Convergence theorems for the scheme are proven, and it is shown that the condition numbers of the linear systems at each level are independent of the level, thereby establishing for the first time a mathematical theory for multiscale approximation with scaled versions of a single compactly supported radial basis function at scattered data points on a bounded domain.     

服务台不可靠的重试排队系统均衡分析

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。     

Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions

We present a new strategy for the constrained global optimization of expensive black box functions using response surface models. A response surface model is simply a multivariate approximation of a continuous black box function which is used as a surrogate model for optimization in situations where function evaluations are computationally expensive. Prior global optimization methods that utilize response surface models were limited to box-constrained problems, but the new method can easily incorporate general nonlinear constraints. In the proposed method, which we refer to as the Constrained Optimization using Response Surfaces (CORS) Method, the next point for costly function evaluation is chosen to be the one that minimizes the current response surface model subject to the given constraints and to additional constraints that the point be of some distance from previously evaluated points. The distance requirement is allowed to cycle, starting from a high value (global search) and ending with a low value (local search). The purpose of the constraint is to drive the method towards unexplored regions of the domain and to prevent the premature convergence of the method to some point which may not even be a local minimizer of the black box function. The new method can be shown to converge to the global minimizer of any continuous function on a compact set regardless of the response surface model that is used. Finally, we considered two particular implementations of the CORS method which utilize a radial basis function model (CORS-RBF) and applied it on the box-constrained Dixon–Szegö test functions and on a simple nonlinearly constrained test function. The results indicate that the CORS-RBF algorithms are competitive with existing global optimization algorithms for costly functions on the box-constrained test problems. The results also show that the CORS-RBF algorithms are better than other algorithms for constrained global optimization on the nonlinearly constrained test problem.     

Least squares surface approximation to scattered data using multiquadratic functions

The paper documents an investigation into some methods for fitting surfaces to scattered data. The form of the fitting function is a multiquadratic function with the criteria for the fit being the least mean squared residual for the data points. The principal problem is the selection of knot points (or base points for the multiquadratic basis functions), although the selection of the multiquadric parameter also plays a nontrivial role in the process. We first describe a greedy algorithm for knot selection, and this procedure is used as an initial step in what follows. The minimization including knot locations and the multiquadric parameter is explored, with some unexpected results in terms of “near repeated” knots. This phenomenon is explored, and leads us to consider variable parameter values for the basis functions. Examples and results are given throughout.     

Scattered data fitting of Hermite type by a weighted meshless method

In many practical problems, it is often desirable to interpolate not only the function values but also the values of derivatives up to certain order, as in the Hermite interpolation. The Hermite interpolation method by radial basis functions is used widely for solving scattered Hermite data approximation problems. However, sometimes it makes more sense to approximate the solution by a least squares fit. This is particularly true when the data are contaminated with noise. In this paper, a weighted meshless method is presented to solve least squares problems with noise. The weighted meshless method by Gaussian radial basis functions is proposed to fit scattered Hermite data with noise in certain local regions of the problem’s domain. Existence and uniqueness of the solution is proved. This approach has one parameter which can adjust the accuracy according to the size of the noise. Another advantage of the weighted meshless method is that it can be used for problems in high dimensions with nonregular domains. The numerical experiments show that our weighted meshless method has better performance than the traditional least squares method in the case of noisy Hermite data.     

Iterative adaptive RBF methods for detection of edges in two-dimensional functions

Radial basis functions have gained popularity for many applications including numerical solution of partial differential equations, image processing, and machine learning. For these applications it is useful to have an algorithm which detects edges or sharp gradients and is based on the underlying basis functions. In our previous research, we proposed an iterative adaptive multiquadric radial basis function method for the detection of local jump discontinuities in one-dimensional problems. The iterative edge detection method is based on the observation that the absolute values of the expansion coefficients of multiquadric radial basis function approximation grow exponentially in the presence of a local jump discontinuity with fixed shape parameters but grow only linearly with vanishing shape parameters. The different growth rate allows us to accurately detect edges in the radial basis function approximation. In this work, we extend the one-dimensional iterative edge detection method to two-dimensional problems. We consider two approaches: the dimension-by-dimension technique and the global extension approach. In both cases, we use a rescaling method to avoid ill-conditioning of the interpolation matrix. The global extension approach is less efficient than the dimension-by-dimension approach, but is applicable to truly scattered two-dimensional points, whereas the dimension-by-dimension approach requires tensor product grids. Numerical examples using both approaches demonstrate that the two-dimensional iterative adaptive radial basis function method yields accurate results.     

Numerical differentiation for the second order derivatives of functions of two variables

A regularized optimization problem for computing numerical differentiation for the second order derivatives of functions with two variables from noisy values at scattered points is discussed in this article. We prove the existence and uniqueness of the solution to this problem, provide a constructive scheme for the solution which is based on bi-harmonic Green's function and give a convergence estimate of the regularized solution to the exact solution for the problem under a simple choice of regularization parameter. The efficiency of the constructive scheme is shown by some numerical examples.     

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Optimal combination of spatial basis functions for the model reduction of nonlinear distributed parameter systems

Spectral methods are among the most extensively used techniques for model reduction of distributed parameter systems in various fields, including fluid dynamics, quantum mechanics, heat conduction, and weather prediction. However, the model dimension is not minimized for a given desired accuracy because of general spatial basis functions. New spatial basis functions are obtained by linear combination of general spatial basis functions in spectral method, whereas the basis function transformation matrix is derived from straightforward optimization techniques. After the expansion and truncation of spatial basis functions, the present spatial basis functions can provide a lower dimensional and more precise ordinary differential equation system to approximate the dynamics of the systems. The numerical example shows the feasibility and effectiveness of the optimal combination of spectral basis functions for model reduction of nonlinear distributed parameter systems.     

加密网格点二元局部基插值样条函数

1.简介 由于在理论以及应用两方面的重要性,多元样条引起了许多人的注意([6],[7]),紧支撑光滑分片多项式函数对于曲面的逼近是一个十分有效的工具。由于它们的局部支撑性,它们很容易求值;由于它们的光滑性,它们能被应用到要满足一定光滑条件的情况下;由于它们是紧支撑的,它们的线性包有很大的逼近灵活性,而且用它们构造逼近方法来解决的系统是     

基于层次T网格的分片孔斯曲面重构

本文提出一种基于任意层次T网格的多项式(PHT)样条空间$S(3,3,1,1,T)$的一个新的曲面重构算法.该算法由分片插值于层次T网格上每个小矩形单元对应4个顶点的16个参数的孔斯曲面形式给出.对于一个给定的T网格和相应基点处的几何信息(函数值,两个一阶偏导数和混合导数值),可得到与$S(3,3,1,1,T)$的PHT样条曲面相同的结果,且曲面表达形式更简单,同时,在离散数据点的曲面拟合中,我们给出了自适应的曲面加细算法.数值算例显示,该自适应算法能够有效的拟合离散数据点.     

基于期望函数的土遗址锚固参数组合优化方法

针对土遗址锚固工程需求，提出了一种基于期望函数的锚固参数组合优化方法.该方法通过对锚固长度、锚孔直径等参数的组合优化,获得了最大锚固力与最小遗址伤害的良好平衡.试验设计为全因子试验，利用响应面方法构建分析模型，而后将统计中的期望函数法引入锚固参数优化中，建立了多重目标响应指标与锚固参数水平的关系.研究结果表明:当分别满足锚固力最大化和遗址伤害最小化目标时，相应的锚固参数取值间存在冲突；多重响应优化能够确定目标响应需求下锚固参数的可行域范围，方便工程设计人员根据实际工程条件对锚固参数进行可视化取值.     

Constrained optimization involving expensive function evaluations: A sequential approach

This paper presents a new sequential method for constrained nonlinear optimization problems. The principal characteristics of these problems are very time consuming function evaluations and the absence of derivative information. Such problems are common in design optimization, where time consuming function evaluations are carried out by simulation tools (e.g., FEM, CFD). Classical optimization methods, based on derivatives, are not applicable because often derivative information is not available and is too expensive to approximate through finite differencing.The algorithm first creates an experimental design. In the design points the underlying functions are evaluated. Local linear approximations of the real model are obtained with help of weighted regression techniques. The approximating model is then optimized within a trust region to find the best feasible objective improving point. This trust region moves along the most promising direction, which is determined on the basis of the evaluated objective values and constraint violations combined in a filter criterion. If the geometry of the points that determine the local approximations becomes bad, i.e. the points are located in such a way that they result in a bad approximation of the actual model, then we evaluate a geometry improving instead of an objective improving point. In each iteration a new local linear approximation is built, and either a new point is evaluated (objective or geometry improving) or the trust region is decreased. Convergence of the algorithm is guided by the size of this trust region. The focus of the approach is on getting good solutions with a limited number of function evaluations.     

Approximation on the sphere using radial basis functions plus polynomials

In this paper we analyse a hybrid approximation of functions on the sphere by radial basis functions combined with polynomials, with the radial basis functions assumed to be generated by a (strictly) positive definite kernel. The approximation is determined by interpolation at scattered data points, supplemented by side conditions on the coefficients to ensure a square linear system. The analysis is first carried out in the native space associated with the kernel (with no explicit polynomial component, and no side conditions). A more refined error estimate is obtained for functions in a still smaller space. Numerical calculations support the utility of this hybrid approximation.      

Radial basis functions under tension

We discuss multivariate interpolation with some radial basis function, called radial basis function under tension (RBFT). The RBFT depends on a positive parameter which provides a convenient way of controlling the behavior of the interpolating surface. We show that our RBFT is conditionally positive definite of order at least one and give a construction of the native space, namely a semi-Hilbert space with a semi-norm, minimized by such an interpolant. Error estimates are given in terms of this semi-norm and numerical examples illustrate the behavior of interpolating surfaces.     

Surface Reconstruction of 3D Scattered Data with Radial Basis Functions

We use Radial Basis Functions （RBFs） to reconstruct smooth surfaces from 3D scattered data. An object＇s surface is defined implicitly as the zero set of an RBF fitted to the given surface data. We propose improvements on the methods of surface reconstruction with radial basis functions. A sparse approximation set of scattered data is constructed by reducing the number of interpolating points on the surface. We present an adaptive method for finding the off-surface normal points. The order of the equation decreases greatly as the number of the off-surface constraints reduces gradually. Experimental results are provided to illustrate that the proposed method is robust and may draw beautiful graphics.     

Efficient Global Optimization of Expensive Black-Box Functions

In many engineering optimization problems, the number of function evaluations is severely limited by time or cost. These problems pose a special challenge to the field of global optimization, since existing methods often require more function evaluations than can be comfortably afforded. One way to address this challenge is to fit response surfaces to data collected by evaluating the objective and constraint functions at a few points. These surfaces can then be used for visualization, tradeoff analysis, and optimization. In this paper, we introduce the reader to a response surface methodology that is especially good at modeling the nonlinear, multimodal functions that often occur in engineering. We then show how these approximating functions can be used to construct an efficient global optimization algorithm with a credible stopping rule. The key to using response surfaces for global optimization lies in balancing the need to exploit the approximating surface (by sampling where it is minimized) with the need to improve the approximation (by sampling where prediction error may be high). Striking this balance requires solving certain auxiliary problems which have previously been considered intractable, but we show how these computational obstacles can be overcome.     

生理药动学模型参数估计问题

根据生理药动学模型的特点,把非线性药动学模型转化为线性模型,并验证线性模型的精确性.在此基础上,构造估计药动学模型参数的目标函数,并利用非线性优化算法求解模型参数.仿真结果表明,我们的算法具有快速、精确和稳定的特点.给出了一种快速估计复杂生理药动学模型参数的方法,这为解决复杂生理药动学模型的参数估计问题提供了一种有效工具.