On the global convergence of trust region algorithms for unconstrained minimization

Many trust region algorithms for unconstrained minimization have excellent global convergence properties if their second derivative approximations are not too large [2]. We consider how large these approximations have to be, if they prevent convergence when the objective function is bounded below and continuously differentiable. Thus we obtain a useful convergence result in the case when there is a bound on the second derivative approximations that depends linearly on the iteration number.     

An algorithmic representation of fractional powers of positive operators

We are concerned with a new representation of fractional powers of operators by a series using exclusively contractive operators or operators with uniformly bounded powers. This representation is suitable for the construction of efficient approximations for which the error estimates are given and the convergence is investigated. The rate of convergence turns out to be exponential for bounded operators and polynomial for unbounded operators     

An efficient approximation for stochastic differential equations on the partition ofsymmetricalirst

In certain applications of stochastic differential equations a numerical solution must be found corresponding to a particular sample path of the driving process. The order of convergence of approximations based on regular samples of the path is limited, and some approximations are asymptotically efficient in that they minimise the leading coefficient in the expansion of mean-square errors as power series in the sample step size. This paper considers approximations based on irregular samples taken at the passage times of the driving process through a series of thresholds. Such approximations can involve less computation than their regular sample counterparts, particularly for real-time applications. The orders of convergence of the Euler and Milshtein approximations are derived and a new approximation is defined which is asymptotically efficient with respect to the irregular samples. Its asymptotic mean-square error is less than half that of efficient approximations based on regular sample     

Convergence in probability of random power series and a related problem in linear topological spaces

A linear topological space is said to have the circle property if every power series with coefficients in it has a circle of convergence. Every complete locally convex or locally bounded space has the circle property, but not a certain class ofF-spaces including the space of all random variables on a non-atomic probability space, endowed with the topology of convergence in probability. Research sponsored by the National Science Foundation under Grant No. GP 6035.     

Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

Uniform Convergence of Variational Methods for Plane Subsonic Flow

Uniform convergence is proved for certain direct variationalmethods, assuming the existence of a solution with certain properties.In particular one important property used is that of "subsonicity".This is then imposed on the approximating functions in orderto establish the uniform convergence. This overcomes a crucialassumption made in previous work for Rayleigh–Ritz approximations.further, previous results for bounded subdomains are extentedto infinity. The analysis applies mroe generally to plane uniformlyelliptic problems when a priori bounds on the first derivativesof the solution are known to exist.     

Affine scaling interior Levenberg–Marquardt method for bound-constrained semismooth equations under local error bound conditions

We develop and analyze a new affine scaling Levenberg–Marquardt method with nonmonotonic interior backtracking line search technique for solving bound-constrained semismooth equations under local error bound conditions. The affine scaling Levenberg–Marquardt equation is based on a minimization of the squared Euclidean norm of linear model adding a quadratic affine scaling matrix to find a solution that belongs to the bounded constraints on variable. The global convergence results are developed in a very general setting of computing trial directions by a semismooth Levenberg–Marquardt method where a backtracking line search technique projects trial steps onto the feasible interior set. We establish that close to the solution set the affine scaling interior Levenberg–Marquardt algorithm is shown to converge locally Q-superlinearly depending on the quality of the semismooth and Levenberg–Marquardt parameter under an error bound assumption that is much weaker than the standard nonsingularity condition, that is, BD-regular condition under nonsmooth case. A nonmonotonic criterion should bring about speed up the convergence progress in the contours of objective function with large curvature.     

On the approximation of square-integrable functions by exponential series

The expansion of a real square-integrable function in a Legendre series is considered. Existence of best approximations from different sets of exponential functions and their mean convergence to the function in question are proved. As an extension of this result existence and mean convergence of some non-linear best approximations that have been developed by Longman are also demonstrated.     

Behavior of Shannon’s Sampling Series for Hardy Spaces

In this paper the convergence behavior of the Shannon sampling series is analyzed for Hardy spaces. It is well known that the Shannon sampling series is locally uniformly convergent. However, for practical applications the global uniform convergence is important. It is shown that there are functions in the Hardy space such that the Shannon sampling series is not uniformly convergent on the whole real axis. In fact, there exists a function in this space such that the peak value of the Shannon sampling series diverges unboundedly. The proof uses Fefferman’s theorem, which states that the dual space of the Hardy space is the space of functions of bounded mean oscillation. This work was partly supported by the German Research Foundation (DFG) under grant BO 1734/9-1.     

Hybrid sampling series associated with orthogonal wavelets and Gibbs phenomenon

When a sampling theorem holds in wavelet subspaces, sampling expansions can be a good approximation to projection expansions. Even when the sampling theorem does not hold, the scaling function series with the usual coefficients replaced by sampled function values may also be a good approximation to the projection. We refer to such series as hybrid sampling series. For this series, we shall investigate the local convergence and analyze Gibbs phenomenon.     

Boundedness of the series of absolute values of blocks of sine series

The series of absolute values of blocks of a sine series whose coefficients satisfy a certain weakened monotonicity condition are considered. It is shown that to ensure the bounded convergence of such a series, one can take the same blocks as for the Fourier series of functions of bounded variation.     

A direct construction of very smooth local Navier-Stokes solutions

We will consider Galerkin approximations to the solution of the Navier-Stokes initial boundary-value problem in three dimensions. Uniform convergence (locally in time) will be proved with respect to the same norm (being stronger than theH ²-norm) in which the solution's initial value is bounded. The result is the best possible if we will avoid a nonlinear, nonlocal compatibility condition for the initial value.Dedicated to Professor Robert Finn on the occasion of his 70th birthday     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

Closed-form expressions for the finite difference approximations of first and higher derivatives based on Taylor series

Numerical differentiation formulas based on interpolating polynomials, operators and lozenge diagrams can be simplified to one of the finite difference approximations based on Taylor series. In this paper, we have presented closed-form expressions of these approximations of arbitrary order for first and higher derivatives. A comparison of the three types of approximations is given with an ideal digital differentiator by comparing their frequency responses. The comparison reveals that the central difference approximations can be used as digital differentiators, because they do not introduce any phase distortion and their amplitude response is closer to that of an ideal differentiator. It is also observed that central difference approximations are in fact the same as maximally flat digital differentiators. In the appendix, a computer program, written in MATHEMATICA is presented, which can give the approximation of any order to the derivative of a function at a certain mesh point.     

Local convergence analysis for partitioned quasi-Newton updates

Summary This paper considers local convergence properties of inexact partitioned quasi-Newton algorithms for the solution of certain non-linear equations and, in particular, the optimization of partially separable objective functions. Using the bounded deterioration principle, one obtains local and linear convergence, which impliesQ-superlinear convergence under the usual conditions on the quasi-Newton updates. For the optimization case, these conditions are shown to be satisfied by any sequence of updates within the convex Broyden class, even if some Hessians are singular at the minimizer. Finally, local andQ-superlinear convergence is established for an inexact partitioned variable metric method under mild assumptions on the initial Hessian approximations.Work supported by a research grant of the Deutsche Forschungsgemeinschaft, Bonn and carried out at the Department of Applied Mathematics and Theoretical Physics Cambridge (United Kingdom)     

Chernoff approximations of Feller semigroups in Riemannian manifolds

Chernoff approximations of Feller semigroups and the associated diffusion processes in Riemannian manifolds are studied. The manifolds are assumed to be of bounded geometry, thus including all compact manifolds and also a wide range of non-compact manifolds. Sufficient conditions are established for a class of second order elliptic operators to generate a Feller semigroup on a (generally non-compact) manifold of bounded geometry. A construction of Chernoff approximations is presented for these Feller semigroups in terms of shift operators. This provides approximations of solutions to initial value problems for parabolic equations with variable coefficients on the manifold. It also yields weak convergence of a sequence of random walks on the manifolds to the diffusion processes associated with the elliptic generator. For parallelizable manifolds this result is applied in particular to the representation of Brownian motion on the manifolds as limits of the corresponding random walks.     

Boundary layer approximate approximations and cubature of potentials in domains

In this article we present a new approach to the computation of volume potentials over bounded domains, which is based on the quasi‐interpolation of the density by almost locally supported basis functions for which the corresponding volume potentials are known. The quasi‐interpolant is a linear combination of the basis function with shifted and scaled arguments and with coefficients explicitly given by the point values of the density. Thus, the approach results in semi‐analytic cubature formulae for volume potentials, which prove to be high order approximations of the integrals. It is based on multi‐resolution schemes for accurate approximations up to the boundary by applying approximate refinement equations of the basis functions and iterative approximations on finer grids. We obtain asymptotic error estimates for the quasi‐interpolation and corresponding cubature formulae and provide some numerical examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

A posteriori error analysis for numerical approximations of Friedrichs systems

The global error of numerical approximations for symmetric positive systems in the sense of Friedrichs is decomposed into a locally created part and a propagating component. Residual-based two-sided local a posteriori error bounds are derived for the locally created part of the global error. These suggest taking the -norm as well as weaker, dual norms of the computable residual as local error indicators. The dual graph norm of the residual is further bounded from above and below in terms of the norm of where h is the local mesh size. The theoretical results are illustrated by a series of numerical experiments. Received January 10, 1997 / Revised version received March 5, 1998     

无约束非光滑优化问题信赖域算法的收敛条件

1 引言 考虑下列无约束非光滑优化问题 minf(x),(1) x∈R~n,其中f为R~n上的局部Lipschitz函数,本文将‖·‖_2简记为‖·‖.记下列信赖域子问题为S∪B(x,△). min m(x,s)=φ(x,s)+1/2s~TBs, 其中φ:R~(2m)→R为f的迭代函数。 对于无约束非光滑优化问题(1),[11],[13],[3]、[4]和[5]分别在特殊的条件下给出了信赖域算法用以求解(1)的收敛性结果。最近,[10]、[2]和[6]在不同的假设条件下分别给出了信赖域算法求解无约束非光滑优化问题的一般模型,并在子问题的目标函数满足局部一致有界性条件时证明了算法模型的整体收敛性。在目标函数满足某种正则性条件时,[11]和[9]给出了当信赖域子问题的目标函数中二次项不满足一致有界性条件时的收敛性结果.本文则在目标函数仅为局部Lipschitz函数时得到了和[8]、[11]、[9]相同的收敛性结果。     

Weighted error estimates for approximation by Cesàro means of Fourier-Jacobi series in spaces of locally continuous functions

We establish sufficient conditions on the parameter θ > 0 of the Cesàro means of Fourier-Jacobi series in spaces of locally continuous functions in order to have bounded weighted norm. For θ ≥ 1, a Stechkin type error estimate for the order of convergence will also be given.