An approximation procedure for solutions to Mayer problems with cost functional not of classC

We consider here control problems in the Mayer form, with a cost functional which is continuous, but not necessarily of classC ¹. The usual necessary conditions for such problems cannot be applied, since they require that the cost functional beC ¹. We describe a convergence procedure, based upon approximations to the cost functional, that will yield an optimal trajectory to such control systems. Criteria are given which justify that this approximation procedure will yield a trajectory and control, satisfying certain prescribed conditions, which minimize the above cost functional within a specified class of such pairs. Examples are presented.     

Approximation algorithms for art gallery problems in polygons

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n⁴) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n⁵).     

Error estimates and superconvergence of semidiscrete mixed methods for optimal control problems governed by hyperbolic equations

In this paper, we investigate the L ^??(L ₂)-error estimates and superconvergence of the semidiscrete mixed finite elementmethods for quadratic optimal control problems governed by linear hyperbolic equations. The state and the co-state are discretized by the order k Raviart-Thomas mixed finite element spaces and the control is approximated by piecewise polynomials of order k(k ?? 0). We derive error estimates for approximation of both state and control. Moreover, we present the superconvergence analysis for mixed finite element approximation of the optimal control problems.     

New efficient numerical procedures for solving stochastic variational problems with a priori maximum pointwise error estimates

In a previous paper we gave a new formulation and derived the Euler equations and other necessary conditions to solve strong, pathwise, stochastic variational problems with trajectories driven by Brownian motion. Thus, unlike current methods which minimize the control over deterministic functionals (the expected value), we find the control which gives the critical point solution of random functionals of a Brownian path and then, if we choose, find the expected value.This increase in information is balanced by the fact that our methods are anticipative while current methods are not. However, our methods are more directly connected to the theory and meaningful examples of deterministic variational theory and provide better means of solution for free and constrained problems. In addition, examples indicate that there are methods to obtain nonanticipative solutions from our equations although the anticipative optimal cost function has smaller expected value.In this paper we give new, efficient numerical methods to find the solution of these problems in the quadratic case. Of interest is that our numerical solution has a maximal, a priori, pointwise error of O(h3/2) where h is the node size. We believe our results are unique for any theory of stochastic control and that our methods of proof involve new and sophisticated ideas for strong solutions which extend previous deterministic results by the first author where the error was O(h²).We note that, although our solutions are given in terms of stochastic differential equations, we are not using the now standard numerical methods for stochastic differential equations. Instead we find an approximation to the critical point solution of the variational problem using relations derived from setting to zero the directional derivative of the cost functional in the direction of simple test functions.Our results are even more significant than they first appear because we can reformulate stochastic control problems or constrained calculus of variations problems in the unconstrained, stochastic calculus of variations formulation of this paper. This will allow us to find efficient and accurate numerical solutions for general constrained, stochastic optimization problems. This is not yet being done, even in the deterministic case, except by the first author.     

Optimal approximation of convex curves by functions which are piecewise linear

In this paper an efficient method is presented for solving the problem of approximation of convex curves by functions that are piecewise linear, in such a manner that the maximum absolute value of the approximation error is minimized. The method requires the curves to be convex on the approximation interval only. The boundary values of the approximation function can be either free or specified. The method is based on the property of the optimal solution to be such that each linear segment approximates the curve on its interval optimally while the optimal error is uniformly distributed among the linear segments of the approximation function. Using this method the optimal solution can be determined analytically to the full extent in certain cases, as it was done for functions x² and $\text{x}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. In general, the optimal solution has to be computed numerically following the procedure suggested in the paper. Using this procedure, optimal solutions were computed for functions sin x, tg x, and arc tg x. Optimal solutions to these functions were used in practical applications.     

A PDE approach to regularity of solutions to finite horizon optimal switching problems

We study optimal 2-switching and n-switching problems and the corresponding system of variational inequalities. We obtain results on the existence of viscosity solutions for the 2-switching problem for various setups when the cost of switching is non-deterministic. For the n-switching problem we obtain regularity results for the solutions of the variational inequalities. The solutions are C^1,1-regular away for the free boundaries of the action sets.     

An optimal sequential algorithm for the uniform approximation of convex functions on [0,1]2

In this paper an algorithm is given for the sequential selection ofN nodes (i.e., measurement points) for the uniform approximation (recovery) of convex functions over [0, 1]², which has almost optimal order global error, (≦c ₁ N ^?1 lgN), over a naturally defined class of convex functions. This shows the essential superiority of sequential algorithms for this class of approximation problems because any simultaneous choice ofN nodes leads to a global error >c ₀ N ^?1/2. New construction and estimation methods are presented, with possible (e.g., multidimensional) generalizations.     

L ∞-error estimates of triangular mixed finite element methods for optimal control problems governed by semilinear elliptic equations

We look at L ^∞-error estimates for convex quadratic optimal control problems governed by nonlinear elliptic partial differential equations. In so doing, use is made of mixed finite element methods. The state and costate are approximated by the lowest order Raviart-Thomas mixed finite element spaces, and the control, by piecewise constant functions. L ^∞-error estimates of optimal order are derived for a mixed finite element approximation of a semilinear elliptic optimal control problem. Finally, numerical tests are presented which confirm our theoretical results.     

New a posteriori L∞(L2) and L2(L2)-error estimates of mixed finite element methods for general nonlinear parabolic optimal control problems

We study new a posteriori error estimates of the mixed finite element methods for general optimal control problems governed by nonlinear parabolic equations. The state and the co-state are discretized by the high order Raviart-Thomas mixed finite element spaces and the control is approximated by piecewise constant functions. We derive a posteriori error estimates in L^∞(J; L²Ω)-norm and L²(J; L²Ω)-norm for both the state, the co-state and the control approximation. Such estimates, which seem to be new, are an important step towards developing a reliable adaptive mixed finite element approximation for optimal control problems. Finally, the performance of the posteriori error estimators is assessed by two numerical examples.     

A new coupled approach high accuracy numerical method for the solution of 3D non-linear biharmonic equations

In this paper, we derive a new fourth order finite difference approximation based on arithmetic average discretization for the solution of three-dimensional non-linear biharmonic partial differential equations on a 19-point compact stencil using coupled approach. The numerical solutions of unknown variable u(x,y,z) and its Laplacian ∇²u are obtained at each internal grid point. The resulting stencil algorithm is presented which can be used to solve many physical problems. The proposed method allows us to use the Dirichlet boundary conditions directly and there is no need to discretize the derivative boundary conditions near the boundary. We also show that special treatment is required to handle the boundary conditions. The new method is tested on three problems and the results are compared with the corresponding second order approximation, which we also discuss using coupled approach.     

Milstein Approximation for Advection-Diffusion Equations Driven by Multiplicative Noncontinuous Martingale Noises

In this paper, the strong approximation of a stochastic partial differential equation, whose differential operator is of advection-diffusion type and which is driven by a multiplicative, infinite dimensional, càdlàg, square integrable martingale, is presented. A finite dimensional projection of the infinite dimensional equation, for example a Galerkin projection, with nonequidistant time stepping is used. Error estimates for the discretized equation are derived in?L ² and almost sure senses. Besides space and time discretizations, noise approximations are also provided, where the Milstein double stochastic integral is approximated in such a way that the overall complexity is not increased compared to an Euler?CMaruyama approximation. Finally, simulations complete the paper.     

C 1 Quadratic and C 2 Quartic Macro-Elements on a Modified Morgan-Scott Triangulation

In this paper, we construct a quadratic composite finite element of class C ¹ and quartic composite finite element of class C ² on a new triangulation τ ₁₀ which is obtained by splitting each triangle of a given triangulation τ into ten smaller subtriangles. These new elements can be used for constructing spline spaces with local basis that can be applied for solving some Hermite interpolation problems with optimal approximation order.     

A posteriori error estimates for hp finite element solutions of convex optimal control problems

In this paper, we present a posteriori error analysis for hp finite element approximation of convex optimal control problems. We derive a new quasi-interpolation operator of Clément type and a new quasi-interpolation operator of Scott-Zhang type that preserves homogeneous boundary condition. The Scott-Zhang type quasi-interpolation is suitable for an application in bounding the errors in L²-norm. Then hp a posteriori error estimators are obtained for the coupled state and control approximations. Such estimators can be used to construct reliable adaptive finite elements for the control problems.     

Soft due window assignment and scheduling of unit-time jobs on parallel machines

We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n ⁵/m ²) and O(n ^4.5log^0.5 n/m ²) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.     

Parallel domain decomposition procedures of improved D-D type for parabolic problems

Two parallel domain decomposition procedures for solving initial-boundary value problems of parabolic partial differential equations are proposed. One is the extended D-D type algorithm, which extends the explicit/implicit conservative Galerkin domain decomposition procedures, given in [5], from a rectangle domain and its decomposition that consisted of a stripe of sub-rectangles into a general domain and its general decomposition with a net-like structure. An almost optimal error estimate, without the factor H^−1/2 given in Dawson-Dupont’s error estimate, is proved. Another is the parallel domain decomposition algorithm of improved D-D type, in which an additional term is introduced to produce an approximation of an optimal error accuracy in L²-norm.     

Using piecewise linear functions in the numerical approximation of semilinear elliptic control problems

We study the numerical approximation of distributed optimal control problems governed by semilinear elliptic partial differential equations with pointwise constraints on the control. Piecewise linear finite elements are used to approximate the control as well as the state. We prove that the L ²-error estimates are of order o(h), which is optimal according with the $C^{0,1}(\overline{\Omega})$ -regularity of the optimal control.     

Complexity of differential and integral equations

We are interested in the intrinsic difficulty (or complexity) of computing an approximate solution of the linear operator equation Lu = f. Practical examples of such problems include the cases where L is a known partial differential or integral operator. Problems of the form Lu = f are typically solved under the constraint that only partial information about f is available, such as the values of a finite number of inner products, or the values of f at a finite number of points. It is of interest to determine when algorithms which are in wide use are optimal algorithms, i.e., algorithms which produce an approximation with minimal cost. We are especially interested in determining conditions which are necessary and sufficient for the finite element method (FEM) to be optimal. For the cases of elliptic partial differential equations and of Fredholm integral equations of the second kind, we describe such a condition, in the form of an inequality involving the order of the problem and the degree of the finite element subspace. Suppose this inequality is violated; is the nonoptimality of the FEM inherent in the information used by the FEM, or is it because the FEM uses this information in a nonoptimal manner? The latter is the case; there always exists an algorithm using this information which is optimal. We also discuss the situation in which the information used by the finite element method (which consists of inner products) is not available. Suppose that the only admissible information about f consists of evaluations of f. In the case of the Fredholm problem of the second kind, this information is optimal; moreover, a finite element method in which the inner products are approximated by quadrature rules is an optimal algorithm. However there exist elliptic problems of positive order for which this new information is nonoptimal.     

A discontinuous mixed covolume method for elliptic problems

We develop a discontinuous mixed covolume method for elliptic problems on triangular meshes. An optimal error estimate for the approximation of velocity is obtained in a mesh-dependent norm. First-order L²-error estimates are derived for the approximations of both velocity and pressure.     

An optimal replacement policy for a multistate degenerative simple system

In this paper, a degenerative simple system (i.e. a degenerative one-component system with one repairman) with k + 1 states, including k failure states and one working state, is studied. Assume that the system after repair is not “as good as new”, and the degeneration of the system is stochastic. Under these assumptions, we consider a new replacement policy T based on the system age. Our problem is to determine an optimal replacement policy T^∗ such that the average cost rate (i.e. the long-run average cost per unit time) of the system is minimized. The explicit expression of the average cost rate is derived, the corresponding optimal replacement policy can be determined, the explicit expression of the minimum of the average cost rate can be found and under some mild conditions the existence and uniqueness of the optimal policy T^∗ can be proved, too. Further, we can show that the repair model for the multistate system in this paper forms a general monotone process repair model which includes the geometric process repair model as a special case. We can also show that the repair model in the paper is equivalent to a geometric process repair model for a two-state degenerative simple system in the sense that they have the same average cost rate and the same optimal policy. Finally, a numerical example is given to illustrate the theoretical results of this model.     

Error estimate of fully discrete discontinuous Galerkin approximation for the viscoelasticity type equation

In this paper we develop fully discrete discontinuous Galerkin approximation using symmetric interior penalty method. We construct finite element spaces which consist of piecewise continuous polynomials. We introduce an appropriate elliptic-type projection of u and prove its optimal convergence. We develop fully discrete discontinuous Galerkin approximations and prove the optimal convergence in ? ^∞(L ²) normed space.