An approximation problem of noisy data by cubic and bicubic splines

Smoothing of noisy data has always been a topic of interest in many areas where computer simulations have been performed, including natural sciences as well as economics and social sciences. In this paper we present an approximation method of explicit curves or surfaces from exact and noisy data by fairness cubic or bicubic splines. A variational problem of explicit curves or surfaces is obtained by minimizing a quadratic functional in a space of cubic or bicubic splines from noisy data. We show the existence and uniqueness of this problem as long as a convergence result especially for noisy data is carefully established. We analyze some numerical and graphical examples using fictional noisy data in order to prove the validity of our method.     

An inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

Pricing and hedging Asian basket spread options

Asian options, basket options and spread options have been extensively studied in the literature. However, few papers deal with the problem of pricing general Asian basket spread options. This paper aims to fill this gap. In order to obtain prices and Greeks in a short computation time, we develop approximation formulae based on comonotonicity theory and moment matching methods. We compare their relative performances and explain how to choose the best approximation technique as a function of the Asian basket spread characteristics. We also give explicitly the Greeks for our proposed methods. In the last section we extend our results to options denominated in foreign currency.     

Existence of optimal solution for exponential model by least squares

In this paper we prove the existence theorem for the best least squares approximation of the optimal parameters for the exponential model function. We give sufficient conditions which guarantee the existence of such optimal parameters. Using these results and methods, we are able to localize a sufficiently narrow area where one can choose a good initial approximation.     

Adaptive parameter choice for one-sided finite difference schemes and its application in diabetes technology

In this paper we discuss the problem of approximation of the first derivative of a function at the endpoint of its definition interval. This problem is motivated by diabetes therapy management, where it is important to provide estimations of the future blood glucose trend from current and past measurements. A natural way to approach the problem is to use one-sided finite difference schemes for numerical differentiation, but, following this way, one should be aware that the values of the function to be differentiated are noisy and available only at given fixed points. Then (as we argue in the paper) the number of used point values is the only parameter to be employed for regularization of the above mentioned ill-posed problem of numerical differentiation. In this paper we present and theoretically justify an adaptive procedure for choosing such a parameter. We also demonstrate some illustrative tests, as well as the results of numerical experiments with simulated clinical data.     

带约束导数值域的L逼近

1972年J.A.Roulier和G.D.Taylor研究了带约束导数值域的一致逼近,在文章最后,他们提出了一个未解决的问题,就是关于带约束导数值域的L逼近问题.本文研究了这个问题,得到与[1]平行的结果.这个结果同时也推广了 R.A.Lorentz的工作. 第一节给出存在定理,第二节证明若干特征定理,第三节给出一个唯一性定理.     

A combined direction stochastic approximation algorithm

The stochastic approximation problem is to find some root or minimum of a nonlinear function in the presence of noisy measurements. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy negative gradient direction as the iterative direction. In order to accelerate the classical RM algorithm, this paper gives a new combined direction stochastic approximation algorithm which employs a weighted combination of the current noisy negative gradient and some former noisy negative gradient as iterative direction. Both the almost sure convergence and the asymptotic rate of convergence of the new algorithm are established. Numerical experiments show that the new algorithm outperforms the classical RM algorithm.     

Properties and least‐squares problems for row extended matrices

In this paper, we discuss basic properties, a least‐squares problem for row extended matrices and the associated approximation problem. First, we obtain their basic properties by applying their particular structure. Then we derive a general representation of the solutions to the least‐squares problem, and we obtain an expression for the solution to the associated approximation problem. Finally, we provide a perturbation analysis and a perturbation bound for the best approximate solution. The results are illustrated by numerical examples. Copyright © 2009 John Wiley & Sons, Ltd.     

Numerical solution of linear Volterra integral equations of the second kind with sharp gradients

Collocation methods are a well-developed approach for the numerical solution of smooth and weakly singular Volterra integral equations. In this paper, we extend these methods through the use of partitioned quadrature based on the qualocation framework, to allow the efficient numerical solution of linear, scalar Volterra integral equations of the second kind with smooth kernels containing sharp gradients. In this case, the standard collocation methods may lose computational efficiency despite the smoothness of the kernel. We illustrate how the qualocation framework can allow one to focus computational effort where necessary through improved quadrature approximations, while keeping the solution approximation fixed. The computational performance improvement introduced by our new method is examined through several test examples. The final example we consider is the original problem that motivated this work: the problem of calculating the probability density associated with a continuous-time random walk in three dimensions that may be killed at a fixed lattice site. To demonstrate how separating the solution approximation from quadrature approximation may improve computational performance, we also compare our new method to several existing Gregory, Sinc, and global spectral methods, where quadrature approximation and solution approximation are coupled.     

Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes

A stochastic approximation (SA) algorithm with new adaptive step sizes for solving unconstrained minimization problems in noisy environment is proposed. New adaptive step size scheme uses ordered statistics of fixed number of previous noisy function values as a criterion for accepting good and rejecting bad steps. The scheme allows the algorithm to move in bigger steps and avoid steps proportional to $1/k$ when it is expected that larger steps will improve the performance. An algorithm with the new adaptive scheme is defined for a general descent direction. The almost sure convergence is established. The performance of new algorithm is tested on a set of standard test problems and compared with relevant algorithms. Numerical results support theoretical expectations and verify efficiency of the algorithm regardless of chosen search direction and noise level. Numerical results on problems arising in machine learning are also presented. Linear regression problem is considered using real data set. The results suggest that the proposed algorithm shows promise.     

Portfolio optimization via stochastic programming: Methods of output analysis

Solutions of portfolio optimization problems are often influenced by errors or misspecifications due to approximation, estimation and incomplete information. Selected methods for analysis of results obtained by solving stochastic programs are presented and their scope illustrated on generic examples – the Markowitz model, a multiperiod bond portfolio management problem and a general strategic investment problem. The approaches are based on asymptotic and robust statistics, on the moment problem and on results of parametric optimization.     

Model checking for partially linear models with missing responses at random

In this paper, we investigate the model checking problem for a partial linear model while some responses are missing at random. By imputation and marginal inverse probability weighted methods, two completed data sets are constructed. Based on the two completed data sets, we build two empirical process-based tests for examining the adequacy of partial linearity of the model. The asymptotic distributions of the test statistics under the null hypothesis and local alternative hypotheses are obtained respectively. A re-sampling approach is applied to obtain the approximation to the null distributions of the test statistics. Simulation results show that the proposed tests work well and both proposed methods have better finite sample properties compared with the complete case (CC) analysis which discards all the subjects with missing data.     

Estimates of efficiency for two methods of stable numerical summation of smooth functions

We consider a classical ill-posed problem of reconstruction of continuous functions from their noisy Fourier coefficients. We study the case of functions of two variables that has been much less investigated. The smoothness of reconstructed functions is measured in terms of the Sobolev classes as well as the classes of functions with dominated mixed derivatives. We investigate two summation methods, that are based on ideas of the rectangle and the hyperbolic cross, respectively. For both of these methods we establish the estimates of the accuracy on the classes that are considered as well the estimates of computational costs. Moreover, we made the comparison of their efficiency based on obtained estimates. A somehow surprising outcome of our study is that for both types of the considered smoothness classes one should employ hyperbolic cross approximation that is not typical for the functions under consideration.     

Efficient numerical methods for boundary data and right‐hand side reconstructions in elliptic partial differential equations

In this article, we discuss the application of two important numerical methods, Ritz–Galerkin and Method of Fundamental Solutions (MFS), for solving some inverse problems, arising in the context of two‐dimensional elliptic equations. The main incentive for studying the considered problems is their wide applications in engineering fields. In the previous literature, the use of these methods, particularly MFS for right hand side reconstruction has been limited, partly due to stability concerns. We demonstrate that these diculties may be surmounted if the aforementioned methods are combined with techniques such as dual reciprocity method(DRM). Moreover, we incorporate some iterative regularization techniques. This fact is especially veried by taking into account the noisy data with boundary conditions. In addition, parts of this article are dedicated to the problem of boundary data approximation and the issue of numerical stability, ending with a general discussion on the advantages and disadvantages of various methods. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1995–2026, 2015     

New assignment algorithms for the multi-depot vehicle routing problem

This paper considers the design and analysis of algorithms for the multi-depot vehicle routing problem with time windows (MDVRPTW). Given the intrinsic difficulty of this problem class, approximation methods of the type ‘cluster first, route second’ (two-step approaches) seem to offer the most promise for practical size problems. After describing six heuristics for the cluster part (assignment of customers to depots) an initial computational study of their performance is conducted. Finding, as expected, that the heuristics with the best results (in terms of the routing results) are those with the largest computational efforts.     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Approximation by Partial Isometries and Symmetric Approximation of Finite Frames

We solve the problem of best approximation by partial isometries of given rank to an arbitrary rectangular matrix, when the distance is measured in any unitarily invariant norm. In the case where the norm is strictly convex, we parametrize all the solutions. In particular, this allows us to give a simple necessary and sufficient condition for uniqueness. We then apply these results to solve the global problem of approximation by partial isometries, and to extend the notion of symmetric approximation of frames introduced in Frank et al. (Trans Am Math Soc 354: 777–793, 2002). In addition, we characterize symmetric approximations of frames belonging to a prescribed subspace.     

Approximation bounds for sparse principal component analysis

We produce approximation bounds on a semidefinite programming relaxation for sparse principal component analysis. The sparse maximum eigenvalue problem cannot be efficiently approximated up to a constant approximation ratio, so our bounds depend on the optimum value of the semidefinite relaxation: the higher this value, the better the approximation. In particular, these bounds allow us to control approximation ratios for tractable statistics in hypothesis testing problems where data points are sampled from Gaussian models with a single sparse leading component.     

Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery

In this paper, we consider a variant of the many-to-many location-routing problem, where hub facilities have to be located and customers with either pickup or delivery demands have to be combined in vehicle routes. In addition, several commodities and inter-hub transport processes are taken into account. A practical application of the problem can be found in the timber-trade industry, where companies provide their services using hub-and-spoke networks. We present a mixed-integer linear model for the problem and use CPLEX 12.4 to solve small-scale instances. Furthermore, a multi-start procedure based on a fix-and-optimize scheme and a genetic algorithm are introduced that efficiently construct promising solutions for medium- and large-scale instances. A computational performance analysis shows that the presented methods are suitable for practical application.     

Approximation of nonnegative functions by means of exponentiated trigonometric polynomials

We consider the problem of approximating a nonnegative function from the knowledge of its first Fourier coefficients. Here, we analyze a method introduced heuristically in a paper by Borwein and Huang (SIAM J. Opt. 5 (1995) 68–99), where it is shown how to construct cheaply a trigonometric or algebraic polynomial whose exponential is close in some sense to the considered function. In this note, we prove that approximations given by Borwein and Huang's method, in the trigonometric case, can be related to a nonlinear constrained optimization problem, and their convergence can be easily proved under mild hypotheses as a consequence of known results in approximation theory and spectral properties of Toeplitz matrices. Moreover, they allow to obtain an improved convergence theorem for best entropy approximations.