Error bounds for numerical solutions of ordinary differential equations

Summary An a posteriori error bound, for an approximate solution of a system of ordinary differential equations, is derived as the solution of a Riccati equation. The coefficients of the Riccati equation depend on an eigenvalue of a matrix related to a Jacobian matrix, on a Lipschitz constant for the Jacobian matrix, and on the approximation defect. An upper bound is computable as the formal solution of a sequence of Riccati equations with constant coefficients. This upper bound may sometimes be used to control step length in a numerical method.     

Polynomials with bounds and numerical approximation

We discuss the generation of polynomials with two bounds —an upper bound and a lower bound— on compact sets \(\mathcal C=[0,1]^{d}\subset \mathbb {R}^{d}\) in view on numerical approximation and scientific computing. The presentation is restricted to d = 1,2. We show that a composition formula based on a weighted 4-squares Euler identity generates all such polynomials in dimension d=1. It yields a new algebraic or compositional approach to the classical problem related to polynomials with minimal uniform norm. The theoretical generalization to the multivariate case is discussed in dimension d=2 by means of the 8-squares Degen identity and the connection with quaternions algebras is made explicit. Numerical results in dimension d=1 illustrate the potentialities of this approach and some implementation details are provided.     

Improved error bounds for quantization based numerical schemes for BSDE and nonlinear filtering

We take advantage of recent (see Graf et al., 2008; Pages and Wilbertz, 2012) and new results on optimal quantization theory to improve the quadratic optimal quantization error bounds for backward stochastic differential equations (BSDE) and nonlinear filtering problems. For both problems, a first improvement relies on a Pythagoras like Theorem for quantized conditional expectation. While allowing for some locally Lipschitz continuous conditional densities in nonlinear filtering, the analysis of the error brings into play a new robustness result about optimal quantizers, the so-called distortion mismatch property: the $L^s$-mean quantization error induced by $L^r$-optimal quantizers of size $N$ converges at the same rate $N^{?\frac{1}{d}}$ for every $s\in (0,r+d)$.     

Column generation for IMRT cancer therapy optimization with implementable segments

A radiation beam passes through normal tissue to reach tumor. The latest devices for the radiotherapy of cancer provide intensity modulated radiation treatment, or IMRT. This method refines cancer treatment by varying the intensity profile across the face of a radiation beam. Intensity modulation is usually accomplished by partitioning each beam, distinguished by its angle of entry, into an array of smaller sized units, called beamlets, assigned different intensities. Planning treatment calls for an optimization over beamlet intensities to maximize the dose delivered to the targeted tumor while keeping the distribution of dose throughout the various organs within physician prescribed bounds. The choice of beam angles can be entered into the optimization as well. A common method to produce an intensity pattern is to block out different parts of the beam for different amounts of time. This can be done sliding narrow blocks (leafs) of unit width into the beam from either of two opposing sides to create different beam shapes called segments. A sequence of segments with their exposure times is superimposed to yield the dose distribution actually received in the patient. Current two stage treatment is derived in separate steps: optimization over independently considered beamlet intensities, and generation of a sequence of segments to approximate the planned intensity map. The approximation degrades the solution, and the separate search for segments adds to planning time. We present a mixed integer programming alternative employing column generation to optimize dose over segments themselves. Only segments that can be realized with delivery devices are generated, and adjustments made for the effects of block edges, so that the optimized plans are directly implementable. Preliminary testing demonstrates gains in both planning efficiency and quality of the plans produced. A portion of the work of Dr. Langer, Mr. Thai and Dr. Preciado-Walters was supported by National Science Foundation grant ECS-0120145 and National Cancer Institute 1R41CA91688-01.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

Cover-based bounds on the numerical rank of Gaussian kernels

A popular approach for analyzing high-dimensional datasets is to perform dimensionality reduction by applying non-parametric affinity kernels. Usually, it is assumed that the represented affinities are related to an underlying low-dimensional manifold from which the data is sampled. This approach works under the assumption that, due to the low-dimensionality of the underlying manifold, the kernel has a low numerical rank. Essentially, this means that the kernel can be represented by a small set of numerically-significant eigenvalues and their corresponding eigenvectors.We present an upper bound for the numerical rank of Gaussian convolution operators, which are commonly used as kernels by spectral manifold-learning methods. The achieved bound is based on the underlying geometry that is provided by the manifold from which the dataset is assumed to be sampled. The bound can be used to determine the number of significant eigenvalues/eigenvectors that are needed for spectral analysis purposes. Furthermore, the results in this paper provide a relation between the underlying geometry of the manifold (or dataset) and the numerical rank of its Gaussian affinities.The term cover-based bound is used because the computations of this bound are done by using a finite set of small constant-volume boxes that cover the underlying manifold (or the dataset). We present bounds for finite Gaussian kernel matrices as well as for the continuous Gaussian convolution operator. We explore and demonstrate the relations between the bounds that are achieved for finite and continuous cases. The cover-oriented methodology is also used to provide a relation between the geodesic length of a curve and the numerical rank of Gaussian kernel of datasets that are sampled from it.     

Column generation in the integral simplex method

The integral simplex method for set partitioning problems allows only pivots-on-one to be made, which results in a primal all-integer method. In this technical note we outline how to tailor the column generation principle to this method. Because of the restriction to pivots-on-one, only local optimality can be guaranteed, and to ensure global optimality we consider the use of implicit enumeration.     

Some exponentially decreasing error bounds for a numerical inversion of the Laplace transform

Convergence properties of a class of least-squares methods for finding approximate inverses of the Laplace transform are obtained by using reproducing kernel Hilbert space techniques (or, alternatively, related minimization techniques) and some classical interpolation results.     

Column generation based heuristic for tactical planning in multi-period vehicle routing

The periodic vehicle routing problem (PVRP) consists in establishing a planning of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. The tactical planning model considered here restricts its attention to scheduling visits and assigning them to vehicles while leaving sequencing decisions for an underlying operational model. The objective is twofold: to optimize regional compactness of the routes in a desire to specialize routes to restricted geographical area and to balance the workload evenly between vehicles. Approximate solutions are constructed using a truncated column generation procedure followed by a rounding heuristic. This mathematical programming based procedure can deal with problems with 50–80 customers over five working days which is the range of size of most PVRP instances treated in the literature with meta-heuristics. The paper highlights the importance of alternative optimization criteria not accounted for in standard operational models and provides insights on the implementation of a column generation based rounding heuristic.     

On grid generation for numerical models of geophysical fluid dynamics

A simple geometric condition that defines the class of classical (stereographic, conic and cylindrical) conformal mappings from a sphere onto a plane is derived. The problem of optimization of computational grid for spherical domains is solved in an entire class of conformal mappings on spherical (geodesic) disk. The characteristics of computational grids of classical mappings are compared for different spherical radii of geodesic disk. For a rectangular computational domain, the optimization problem is solved in the class of classical mappings and respective area of the spherical domain is evaluated.     

Computable numerical bounds for lagrange multipliers of stationary points of non-convex differentiable non-linear programs

It is shown that the satisfaction of a standard constraint qualification of mathematical programming [5] at a stationary point of a non-convex differentiable non-linear program provides explicit numerical bounds for the set of all Lagrange multipliers associated with the stationary point. Solution of a single linear program gives a sharper bound together with an achievable bound on the 1-norm of the multipliers associated with the inequality constraints. The simplicity of obtaining these bounds contrasts sharply with the intractable NP-complete problem of computing an achievable upper bound on the p-norm of the multipliers associated with the equality constraints for integer $\text{p ≧ 1}$.     

Exponential moment bounds and strong convergence rates for tamed-truncated numerical approximations of stochastic convolutions

Numerical Algorithms - In this article we establish exponential moment bounds, moment bounds in fractional order smoothness spaces, a uniform Hölder continuity in time, and strong convergence...     

Column generation heuristics for multiple machine, multiple orders per job scheduling problems

Front opening unified pods (FOUPs) are used to store and transport silicon wafers in 300-mm semiconductor wafer fabs. To achieve production efficiencies, wafers are grouped together in FOUPs without regard to the originating customer placing the order. In the resulting multiple orders per job (moj) scheduling problem, scheduling is performed at the FOUP (i.e., aggregated order) level, while scheduling performance is assessed per individual customer order. Column generation heuristics are presented for single and parallel machine moj scheduling problems to minimize total weighted order completion time. The proposed heuristics obtain near-optimal solutions very quickly, outperforming competing approaches in the literature.