Model reduction of semiaffinely parameterized partial differential equations by two-level affine approximation

We propose an improvement to the reduced basis method for parametric partial differential equations. An assumption of affine parameterization leads to an efficient offline–online decomposition when the problem is solved for many different parametric configurations. We consider an advection–diffusion problem, where the diffusive term is non-affinely parameterized and treated with a two-level affine approximation given by the empirical interpolation method. The offline stage and a posteriori error estimation is performed using the coarse-level approximation, while the fine-level approximation is used to perform a correction iteration that reduces the actual error of the reduced basis approximation while keeping the same certified error bounds.     

A filtering method for the interval eigenvalue problem

We consider the general problem of computing intervals that contain the real eigenvalues of interval matrices. Given an outer approximation (superset) of the real eigenvalue set of an interval matrix, we propose a filtering method that iteratively improves the approximation. Even though our method is based on a sufficient regularity condition, it is very efficient in practice and our experimental results suggest that it improves, in general, significantly the initial outer approximation. The proposed method works for general, as well as for symmetric interval matrices.     

Optimal objective function approximation for separable convex quadratic programming

We present an optimal piecewise-linear approximation method for the objective function of separable convex quadratic programs. The method provides guidelines on how many grid points to use and how to position them for a piecewise-linear approximation if the error induced by the approximation is to be bounded a priori.Corresponding author.     

An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form

We present an algorithm to find an approximation for the stationary distribution for the general ergodic spatially-inhomogeneous block-partitioned upper Hessenberg form. Our approximation makes use of an associated upper block-Hessenberg matrix which is spatially homogeneous except for a finite number of blocks. We treat theMAP/G/1 retrial queue and the retrial queue with two types of customer as specific instances and give some numerical examples. The numerical results suggest that our method is superior to the ordinary finite-truncation method.     

Approximation for Navier-Stokes equations around a rotating obstacle

This work presents an approximation method for Navier-Stokes equations around a rotating obstacle. The detail of this method is that the exterior domain is truncated into a bounded domain and a new exterior domain by introducing a large ball. The approximation problem is composed of the nonlinear problem in the bounded domain and the linear problem in the new exterior domain. We derive the approximation error between the solutions of Navier-Stokes equations and the approximation problem.     

Approximation of bone remodeling models

We present convergence results and error estimates concerning the numerical approximation of a class of bone remodeling models, that are elastic adaptive rod models. These are characterized by an elliptic variational equation, representing the equilibrium of the rod under the action of applied loads, coupled with an ordinary differential equation with respect to time, describing the physiological process of bone remodeling. We first consider the semi-discrete approximation, where only the space variables are discretized using the standard Galerkin method, and then, applying the forward Euler method for the time discretization, we focus on the fully discrete approximation.     

On polyhedral and second-order cone decompositions of semidefinite optimization problems

We study a cutting-plane method for semidefinite optimization problems, and supply a proof of the method’s convergence, under a boundedness assumption. By relating the method’s rate of convergence to an initial outer approximation’s diameter, we argue the method performs well when initialized with a second-order cone approximation, instead of a linear approximation. We invoke the method to provide bound gaps of 0.5–6.5% for sparse PCA problems with 1000s of covariates, and solve nuclear norm problems over 500 × 500 matrices.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

Algebraic approximation of attractors of dynamical systems on manifolds

We consider an algebraic approximation of attractors of dynamical systems defined on a Euclidean space, a flat cylinder, and a projective space. We present the Foias-Temam method for the approximation of attractors of systems with continuous time and apply it to the investigation of Lorenz and Rössler systems. A modification of this method for systems with discrete time is also described. We consider elements of the generalization of the method to the case of an arbitrary Riemannian analytic manifold.     

Une méthode particulaire déterministe pour des équations diffusives non linéaires

We study in this Note a deterministic particle method for heat (or Fokker–Planck) equations or for porous media equations. This method is based upon an approximation of these equations by nonlinear transport equations and we prove the convergence of that approximation. Finally, we present some numerical experiments for the heat equation and for an example of porous media equations.     

Near-field and far-field approximations by the Adomian and asymptotic decomposition methods

The Adomian decomposition method and the asymptotic decomposition method give the near-field approximate solution and far-field approximate solution, respectively, for linear and nonlinear differential equations. The Padé approximants give solution continuation of series solutions, but the continuation is usually effective only on some finite domain, and it can not always give the asymptotic behavior as the independent variables approach infinity. We investigate the global approximate solution by matching the near-field approximation derived from the Adomian decomposition method with the far-field approximation derived from the asymptotic decomposition method for linear and nonlinear differential equations. For several examples we find that there exists an overlap between the near-field approximation and the far-field approximation, so we can match them to obtain a global approximate solution. For other nonlinear examples where the series solution from the Adomian decomposition method has a finite convergent domain, we can match the Padé approximant of the near-field approximation with the far-field approximation to obtain a global approximate solution representing the true, entire solution over an infinite domain.     

Computing the Approximation Error for Neural Networks with Weights Varying on Fixed Directions

We obtain a sharp lower bound estimate for the approximation error of a continuous function by single hidden layer neural networks with a continuous activation function and weights varying on two fixed directions. We show that for a certain class of activation functions this lower bound estimate turns into equality. The obtained result provides us with a method for direct computation of the approximation error. As an application, we give a formula, which can be used to compute instantly the approximation error for a class of functions having second order partial derivatives.     

A Globally Convergent Smoothing Newton Method for Nonsmooth Equations and Its Application to Complementarity Problems

The complementarity problem is theoretically and practically useful, and has been used to study and formulate various equilibrium problems arising in economics and engineerings. Recently, for solving complementarity problems, various equivalent equation formulations have been proposed and seem attractive. However, such formulations have the difficulty that the equation arising from complementarity problems is typically nonsmooth. In this paper, we propose a new smoothing Newton method for nonsmooth equations. In our method, we use an approximation function that is smooth when the approximation parameter is positive, and which coincides with original nonsmooth function when the parameter takes zero. Then, we apply Newton's method for the equation that is equivalent to the original nonsmooth equation and that includes an approximation parameter as a variable. The proposed method has the advantage that it has only to deal with a smooth function at any iteration and that it never requires a procedure to decrease an approximation parameter. We show that the sequence generated by the proposed method is globally convergent to a solution, and that, under semismooth assumption, its convergence rate is superlinear. Moreover, we apply the method to nonlinear complementarity problems. Numerical results show that the proposed method is practically efficient.     

An outer approximate subdifferential method for piecewise affine optimization

Piecewise affine functions arise from Lagrangian duals of integer programming problems, and optimizing them provides good bounds for use in a branch and bound method. Methods such as the subgradient method and bundle methods assume only one subgradient is available at each point, but in many situations there is more information available. We present a new method for optimizing such functions, which is related to steepest descent, but uses an outer approximation to the subdifferential to avoid some of the numerical problems with the steepest descent approach. We provide convergence results for a class of outer approximations, and then develop a practical algorithm using such an approximation for the compact dual to the linear programming relaxation of the uncapacitated facility location problem. We make a numerical comparison of our outer approximation method with the projection method of Conn and Cornuéjols, and the bundle method of Schramm and Zowe. Received September 10, 1998 / Revised version received August 1999?Published online December 15, 1999     

On parameters influencing the stability of quadrature methods for singular integral equations with conjugation

In this paper, we study an approximation method for solving singular integral equations with conjugation on an open arc. The stability of the method depends on the invertibility of certain operators which belong to well-known algebras. We investigate properties of these operators and show how to choose the parameters of the approximation method so that the Fredholm indices of the operators mentioned become equal to zero.     

Approximation of solutions to second order nonlinear Picard problems with Carathéodory right-hand side

We present an approximation method for Picard second order boundary value problems with Carathéodory righthand side. The method is based on the idea of replacing a measurable function in the right-hand side of the problem with its Kantorovich polynomial. We will show that this approximation scheme recovers essential solutions to the original BVP. We also consider the corresponding finite dimensional problem. We suggest a suitable mapping of solutions to finite dimensional problems to piecewise constant functions so that the later approximate a solution to the original BVP. That is why the presented idea may be used in numerical computations.     

From solvability and approximation of variational inequalities to solution of nondifferentiable optimization problems in contact mechanics

In this paper, we first gather existence results for linear and for pseudo-monotone variational inequalities in reflexive Banach spaces. We discuss the necessity of the involved coerciveness conditions and their relationship. Then, we combine Mosco convergence of convex closed sets with an approximation of pseudo-monotone bifunctions and provide a convergent approximation procedure for pseudo-monotone variational inequalities in reflexive Banach spaces. Since hemivariational inequalities in linear elasticity are pseudo-monotone, our approximation method applies to nonmonotone contact problems. We sketch how regularization of the involved nonsmooth functionals together with finite element approximation lead to an efficient numerical solution method for these nonconvex nondifferentiable optimization problems. To illustrate our theory, we give a numerical example of a 2D linear elastic block under a given nonmonotone contact law.     

Solving the biobjective zero–one knapsack problem by an efficient LP-based heuristic

In this paper, we propose a simple and useful method, the core of which is an efficient LP-based heuristic, for solving biobjective 0–1 knapsack problems. Extensive computational experiments show that the proposed method is able to generate a good approximation to the nondominated set very efficiently. We also suggest three qualitative criteria to evaluate such an approximation. In addition, the method can be extended to other problems having properties similar to the knapsack problem.     

Call Center Staffing with Simulation and Cutting Plane Methods

We present an iterative cutting plane method for minimizing staffing costs in a service system subject to satisfying acceptable service level requirements over multiple time periods. We assume that the service level cannot be easily computed, and instead is evaluated using simulation. The simulation uses the method of common random numbers, so that the same sequence of random phenomena is observed when evaluating different staffing plans. In other words, we solve a sample average approximation problem. We establish convergence of the cutting plane method on a given sample average approximation. We also establish both convergence, and the rate of convergence, of the solutions to the sample average approximation to solutions of the original problem as the sample size increases. The cutting plane method relies on the service level functions being concave in the number of servers. We show how to verify this requirement as our algorithm proceeds. A numerical example showcases the properties of our method, and sheds light on when the concavity requirement can be expected to hold.     

A recurrence method for a special class of continuous time linear programming problems

This article studies a numerical solution method for a special class of continuous time linear programming problems denoted by (SP). We will present an efficient method for finding numerical solutions of (SP). The presented method is a discrete approximation algorithm, however, the main work of computing a numerical solution in our method is only to solve finite linear programming problems by using recurrence relations. By our constructive manner, we provide a computational procedure which would yield an error bound introduced by the numerical approximation. We also demonstrate that the searched approximate solutions weakly converge to an optimal solution. Some numerical examples are given to illustrate the provided procedure.