The Shanno-Toint Procedure for Updating Sparse Symmetric Matrices

Two recent methods (Shanno, 1978; Toint, 1980) for revisingestimates of sparse second derivative matrices in quasi-Newtonoptimization algorithms reduce to variable metric formulae whenthere are no sparsity conditions. It is proved that these methodsare equivalent. Further, some examples are given to show thatthe procedure may make the second derivative approximationsworse when the objective function is quadratic. Therefore theconvergence properties of the procedure are sometimes less goodthan the convergence properties of other published methods forrevising sparse second derivative approximations.     

Convergence rate estimates for Tikhonov’s scheme as applied to ill-posed nonconvex optimization problems

We examine the convergence rate of approximations generated by Tikhonov’s scheme as applied to ill-posed constrained optimization problems with general smooth functionals on a convex closed subset of a Hilbert space. Assuming that the solution satisfies a source condition involving the second derivative of the cost functional and depending on the form of constraints, we establish the convergence rate of the Tikhonov approximations in the cases of exact and approximately specified functionals.     

一类新的信赖域算法的全局收敛性

本文对于无约束最优化问题提出了一类非单调的信赖域算法，它是通常的单调信赖域算法的推广。当目标函数是有下界的连续可微函数，而且它的二阶导数的近似的模是线性地依赖于迭代次数时，我们证明了新算法的整体收敛性。     

Constrained interpolation and smoothing

Numerical and theoretical questions related to constrained interpolation and smoothing are treated. The prototype problem is that of finding the smoothest convex interpolant to given univariate data. Recent results have shown that this convex programming problem with infinite constraints can be recast as a finite parametric nonlinear system whose solution is closely related to the second derivative of the desired interpolating function. This paper focuses on the analysis of numerical techniques for solving the nonlinear system and on the theoretical issues that arise when certain extensions of the problem are considered. In particular, we show that two standard iteration techniques, the Jacobi and Gauss-Seidel methods, are globally convergent when applied to this problem. In addition we use the problem structure to develop an efficient implementation of Newton's method and observe consistent quadratic convergence. We also develop a theory for the existence, uniqueness, and representation of solutions to the convex interpolation problem with nonzero lower bounds on the second derivative (strict convexity). Finally, a smoothing spline analogue to the convex interpolation problem is studied with reference to the computation of convex approximations to noisy data.     

Numerical solution of systems of partial integral differential equations with application to pricing options

We introduce and analyze a strongly stable numerical method designed to yield good performance under challenging conditions of irregular or mismatched initial data for solving systems of coupled partial integral differential equations (PIDEs). Spatial derivatives are approximated using second order central difference approximations by treating the mixed derivative terms in a special way. The integral operators are approximated using one and two–dimensional trapezoidal rule on an equidistant grid. Computational complexity of the method for solving large systems of PIDEs is discussed. A detailed treatment for the consistency, stability, and convergence of the proposed method is provided. Two asset American option under regime–switching with jump–diffusion model when solved using a penalty term, leads to a system of two dimensional PIDEs with mixed derivatives. This model involves double probability density function which brings more challenges to the numerical solution in already a complicated partial integral differential equation. The complexity of the dense jump probability generator, the nonlinear penalty term and the regime–switching terms are treated efficiently, while maintaining the stability and convergence of the method. The impact of the jump intensity and other parameters is shown in the graphs. Numerical experiments are performed to demonstrated efficiency, accuracy, and reliability of the proposed approach.     

Limited-memory BFGS with displacement aggregation

A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximations are stored and employed, such as a local superlinear rate of convergence under assumptions that are common for attaining such guarantees. To the best of our knowledge, this is the first work in which a local superlinear convergence rate guarantee is offered by a quasi-Newton scheme that does not either store all curvature pairs throughout the entire run of the optimization algorithm or store an explicit (inverse) Hessian approximation. Numerical results are presented to show that displacement aggregation within an adaptive L-BFGS scheme can lead to better performance than standard L-BFGS.

     

On Double Stratonovich Fractional Integrals and Some Strong and Weak Approximations

Abstract

Double Stratonovich integrals with respect to the odd part and even part of the fractional Brownian motion are constructed. The first and the second moments of such integrals are explicitly identified. As application of double Stratonovich integrals a strong law of large numbers for efBm and ofBm is derived.

Riemann–Stieltjes integral approximations to double Stratonovich fractional integrals are also considered. The strong convergence (almost surely and mean square) is obtained for approximations based on explicit series expansions of the fractional Brownian processes. The weak convergence is derived for approximations by processes with absolutely continuous paths which converge weakly to the considered fractional Brownian processes. The above-mentioned convergences are obtained for deterministic integrands which are given by bimeasures.     

抛物型积分-微分方程有限元近似的超收敛性质

1　引　　言有限元超收敛性质在有限元方法的研究中占有重要的地位 .利用超收敛性不仅可提高有限元实际计算的精度 ,而且还可得到后验误差估计 .对于椭圆问题有限元超收敛性质的研究目前已有了较丰富的结果 [1 - 3] ,而对于近年来引起广泛关注的发展型积分 -微分方程[4- 6] ,这方面的研究尚不成熟 .本文将研究一维抛物型积分 -微分方程半离散有限元近似的超收敛性质 ,证明了剖分单元上的 Lobatto点、Gauss点和拟 Lobatto点分别是函数、一阶和二阶导数逼近的超收敛点 ;并且在一定条件下证明了强超收敛二择一定理 ;在每个单元上 ,单元中点或…     

On the numerical approximation of unstable minimal surfaces with polygonal boundaries

Summary. This work is concerned with the approximation and the numerical computation of polygonal minimal surfaces in . Polygonal minimal surfaces correspond to the critical points of Shiffman's function . Since this function is analytic, polygonal minimal surfaces can be characterized by means of the second derivative of . We present a finite element approximation of quasiminimal surfaces together with an error estimate. In this way we obtain discrete approximations of and of . In particular we prove that the discrete functions converge uniformly on certain compact subsets. This will be the main tool for proving existence and convergence of discrete minimal surfaces in neighbourhoods of non-degenerate minimal surfaces. In the numerical part of this paper we compute numerical approximations of polygonal minimal surfaces by use of Newton's method applied to . Received October 27, 1994     

带补偿的随机二次规划的近似Lagrange-Newton方法

In this paper, two-stage stochastic quadratic programming problems with equality constraints are considered. By Monte Carlo simulation-based approximations of the objective function and its first (second)derivative,an inexact Lagrange-Newton type method is proposed.It is showed that this method is globally convergent with probability one. In particular, the convergence is local superlinear under an integral approximation error bound condition.Moreover, this method can be easily extended to solve stochastic quadratic programming problems with inequality constraints.     

Construction of approximations for a stationary solution of a system of singular ordinary differential equations

We propose a procedure for the construction of successive approximations of a stationary solution of a system of nonlinear ordinary differential equations with a small parameter with the derivative. We present sufficient conditions for the convergence of constructed approximations to the required stationary solution.     

Tree wavelet approximations with applications

We construct a tree wavelet approximation by using a constructive greedy scheme (CGS). We define a function class which contains the functions whose piecewise polynomial approximations generated by the CGS have a prescribed global convergence rate and establish embedding properties of this class. We provide sufficient conditions on a tree index set and on bi-orthogonal wavelet bases which ensure optimal order of convergence for the wavelet approximations encoded on the tree index set using the bi-orthogonal wavelet bases. We then show that if we use the tree index set associated with the partition generated by the CGS to encode a wavelet approximation, it gives optimal order of convergence.     

How bad are the BFGS and DFP methods when the objective function is quadratic?

We study the use of the BFGS and DFP algorithms with step-lengths of one for minimizing quadratic functions of only two variables. The updating formulae in this case imply nonlinear three term recurrence relations between the eigenvalues of consecutive second derivative approximations, which are analysed in order to explain some gross inefficiencies that can occur. Specifically, the BFGS algorithm may require more than 10 iterations to achieve the first decimal place of accuracy, while the performance of the DFP method is far worse. The results help to explain why the DFP method is often less suitable than the BFGS algorithm for general unconstrained optimization calculations, and they show that quadratic functions provide much information about efficiency when the current vector of variables is too far from the solution for an asymptotic convergence analysis.     

On the convergence on nonrectangular grids

The convergence properties of a full discrete approximations to the convection-diffusion equation is the subject of this paper. The full discrete scheme considered is of Lagrangian type: Euler Implicit on time and centered finite difference on space, and is defined using nonrectangular grids. We analyse this scheme under smoothness conditions on nonrectangular space-time grid. The main result establish the convergence of the approximations and we prove that the assumptions on the discrete spatial nodes movement are achieved if we consider the equidistribution principle.     

New zero-finders for trust-region computations

Trust-region methods are among the most popular schemes for determining a local minimum of a nonlinear function in several variables. These methods approximate the nonlinear function by a quadratic polynomial, and a trust-region radius determines the size of the sphere in which the quadratic approximation of the nonlinear function is deemed to be accurate. The trust-region radius has to be computed repeatedly during the minimization process. Each trust-region radius is computed by determining a zero of a nonlinear function ψ(x). This is often done with Newton’s method or a variation thereof. These methods give quadratic convergence of the computed approximations of the trust-region radius. This paper describes a cubically convergent zero-finder that is based on the observation that the second derivative \(\psi ^{\prime \prime }(x)\) can be evaluated inexpensively when the first derivative \(\psi ^{\prime }(x)\) is known. Computed examples illustrate the performance of the zero-finder proposed.     

Stability and Convergence of an Implicit Difference Approximation for the Space Riesz Fractional Reaction-Dispersion Equation

In this paper,we consider a Riesz space-fractional reaction-dispersion equation (RSFRDE).The RSFRDE is obtained from the classical reaction-dispersion equation by replacing the second-order space derivative with a Riesz derivative of orderβ∈(1,2]. We propose an implicit finite difference approximation for RSFRDE.The stability and convergence of the finite difference approximations are analyzed.Numerical results are found in good agreement with the theoretical analysis.     

The Newton Method for Operators with Hölder Continuous First Derivative

We analyze the convergence of the Newton method when the first Fréchet derivative of the operator involved is Hölder continuous. We calculate also the R-order of convergence and provide some a priori error bounds. Based on this study, we give some results on the existence and uniqueness of the solution for a nonlinear Hammerstein integral equation of the second kind.     

Positive Sampling in Wavelet Subspaces

This paper is devoted to the discussion of a “hybrid” sampling series, a series of translates of a nonnegative summability function used in place of an orthogonal scaling function. The coefficients in the series are taken to be sampled values of the function to be approximated. This enables one to avoid the integration which arises in the other series. The approximations based on this hybrid series have certain desirable convergence properties: they are locally uniformly convergent for locally continuous functions, they have quadratic uniform convergence rate for functions in certain Sobolev spaces, they are locally bounded when the function is locally bounded and therefore, in particular, Gibbs' phenomenon is avoided. Numerical experiments are given to illustrate the theoretical results and to compare these approximations with the scaling function approximations.     

Continuous selections and convergence of best Lp –approximations in subspaces of spline functions

The chief purpose of this paper is to study the problem of existence of continuous selections for the metric projection and of convergence of best L_p–approximations in subspaces of polynomial spline functions defined on a real compact interval I. Nürnberger-Sommer [8] have shown that there exists a continuous selection s if and only if the numberof knots k is less than or equal to the order m of the splines. Using their construction of s the author [12] has proved that the sequence of best L_p–approximations of f converges to s(f) as ρ→∞ for every continuous function f. The main results of this paper say that also in the case when k>m there exists always a continuous selection s (it is even pointwise-Lipschitz-continuous and quasi-linear) provided that the approximation problem is restricted to certain subsets I_epsilon; of I. In addition it is shown that anologously as for k≤m the sequence of best L_papproximations of f converges to s(f) for every continuous function f on Iε     

非线性模型误差方差估计的Bootstrap逼近和分布的收敛速度

本文对非线性模型误差方差的估计基于Jackknife虚拟值的Bootstrap方法建立了Bootstrap逼近,证明了逼近的相合性定理,得到了逼近的速度是o(n~(-1/2))。进一步,本文证明了误差方差估计的分布以理想的最佳速度o(n~(-1/2))收敛于正态分布的结论。