Elliptic control problems with gradient constraints—variational discrete versus piecewise constant controls

We consider an elliptic optimal control problem with pointwise bounds on the gradient of the state. To guarantee the required regularity of the state we include the L ^r -norm of the control in our cost functional with r>d (d=2,3). We investigate variational discretization of the control problem (Hinze in Comput. Optim. Appl. 30:45–63, 2005) as well as piecewise constant approximations of the control. In both cases we use standard piecewise linear and continuous finite elements for the discretization of the state. Pointwise bounds on the gradient of the discrete state are enforced element-wise. Error bounds for control and state are obtained in two and three space dimensions depending on the value of r.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002     

A priori error estimates for optimal control problems with pointwise constraints on the gradient of the state

We analyze a finite element approximation of an elliptic optimal control problem with pointwise bounds on the gradient of the state variable. We derive convergence rates if the control space is discretized implicitly by the state equation. In contrast to prior work we obtain these results directly from classical results for the W ^1,∞-error of the finite element projection, without using adjoint information. If the control space is discretized directly, we first prove a regularity result for the optimal control to control the approximation error, based on which we then obtain analogous convergence rates.     

Ricci Curvature and Bochner Formulas for Martingales

We generalize the classical Bochner formula for the heat flow on M to martingales on the path space PM and develop a formalism to compute evolution equations for martingales on path space. We see that our Bochner formula on PM is related to two‐sided bounds on Ricci curvature in much the same manner that the classical Bochner formula on M is related to lower bounds on Ricci curvature. Using this formalism, we obtain new characterizations of bounded Ricci curvature, new gradient estimates for martingales on path space, new Hessian estimates for martingales on path space, and streamlined proofs of the previous characterizations of bounded Ricci curvature.© 2018 Wiley Periodicals, Inc.     

A posteriori error estimates for H 1-Galerkin mixed finite-element method for parabolic problems

The purpose of this article is to derive a posteriori error estimates for the H ¹-Galerkin mixed finite element method for parabolic problems. We study both semidiscrete and fully discrete a posteriori error analyses using standard energy argument. A fully discrete a posteriori error analysis based on the backward Euler method is analysed and upper bounds for the errors are derived. The estimators yield upper bounds for the errors which are global in space and time. Our analysis is based on residual approach and the estimators are free from edge residuals.     

Deviation inequalities and the law of iterated logarithm on the path space over a loop group

A law of iterated logarithm (LIL) in small time and an asymptotic estimate of modulus of continuity are proved for Brownian motion on the loop group ?(G) over a compact connected Lie group G. Upper bounds are obtained via infinite-dimensional deviation inequalities for functionals on the path space ?(?(G)) on ?(G), such as the supremum of Brownian motion on ?(G), which are proved from the Clark–Ocone formula on ?(?(G)). The lower bounds rely on analog finite-dimensional results that are proved separately on Riemannian path space.     

On the Smolyak cubature error for analytic functions

We consider Smolyak's construction for the numerical integration over the d‐dimensional unit cube. The underlying class of integrands is a tensor product space consisting of functions that are analytic in the Cartesian product of ellipses. The Kronrod–Patterson quadrature formulae are proposed as the corresponding basic sequence and this choice is compared with Clenshaw–Curtis quadrature formulae. First, error bounds are derived for the one‐dimensional case, which lead by a recursion formula to error bounds for higher dimensional integration. The applicability of these bounds is shown by examples from frequently used test packages. Finally, numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

An approximate method for solving the convex programming problem

We consider an iterative process for maximization of a convex nondifferentiable functional in a real Hilbert space. Two-sided bounds on the optimal functional value are derived. Stability of the approximate solutions is considered. Convergence of the proposed iterative process is proved.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 59, pp. 122–129, 1986     

G-frames and g-frame sequences in Hilbert spaces

In this paper, we first determine the relations among the best bounds A and B of the g-frame, the g-frame operator S and the pre-frame operator Q and give a necessary and sufficient condition for a g-frame with bounds A and B in a complex Hilbert space. We also introduce the definition of a g-frame sequence and obtain a necessary and sufficient condition for a g-frame sequence with bounds A and B in a complex Hilbert space. Lastly, we consider the stability of a g-frame sequence for a complex Hilbert space under perturbation.     

Variational approximations in energy space for the regulator problem with time delay

We consider a variational procedure for approximating the solution of the state regulator problem with time delay. Motivated by a dual formulation of the problem, we introduce a positive-definite functionalF over a certain energy space of Mikhlin and obtain approximating solutions by the Ritz-Trefftz idea of minimizing it over finite-dimensional subspaces. The resulting approximating solutions, in turn, furnish suboptimal solutions which converge to the optimal solution of the regulator problem with time delay. A priori error bounds in terms of splines are given. A posteriori error bounds are also obtained.     

Upper bounds of a stabilizer order for linear finite-dimensional systems

The problem of stabilizing linear dynamic systems by a stabilizer (a dynamic system) is considered. The upper bounds of a stabilizer order obtained using two Hidenori Kimura results are studied. The bound k ₀ is shown to be better than the bounds k ₁ and k ₂ only in one case. In addition, all possible relations between three bounds k ₀, k ₁, and k ₂ are proven to be realized in the space of parameters of observability and controllability indices, i.e., there is a dynamic system with the respective observability and controllability indices.     

Regularization in Sobolev Spaces with Fractional Order

We study the minimization of a quadratic functional where the Tichonov regularization term is an H ^s -norm with a fractional s > 0. Moreover, pointwise bounds for the unknown solution are given. A multilevel approach as an equivalent norm concept is introduced. We show higher regularity of the solution of the variational inequality. This regularity is used to show the existence of regular Lagrange multipliers in function space. The theory is illustrated by two applications: a Dirichlet boundary control problem and a parameter identification problem.     

Finite element approximation of elliptic control problems with constraints on the gradient

We consider an elliptic optimal control problem with control constraints and pointwise bounds on the gradient of the state. We present a tailored finite element approximation to this optimal control problem, where the cost functional is approximated by a sequence of functionals which are obtained by discretizing the state equation with the help of the lowest order Raviart–Thomas mixed finite element. Pointwise bounds on the gradient variable are enforced in the elements of the triangulation. Controls are not discretized. Error bounds for control and state are obtained in two and three space dimensions. A numerical example confirms our analytical findings.     

Additive Schwarz method for the p-version of the boundary element method for the single layer potential operator on a plane screen

Summary. We analyze an additive Schwarz preconditioner for the p-version of the boundary element method for the single layer potential operator on a plane screen in the three-dimensional Euclidean space. We decompose the ansatz space, which consists of piecewise polynomials of degree p on a mesh of size h, by introducing a coarse mesh of size . After subtraction of the coarse subspace of piecewise constant functions on the coarse mesh this results in local subspaces of piecewise polynomials living only on elements of size H. This decomposition yields a preconditioner which bounds the spectral condition number of the stiffness matrix by . Numerical results supporting the theory are presented. Received August 15, 1998 / Revised version received November 11, 1999 / Published online December 19, 2000     

Time Frequency Representations of Almost Periodic Functions

In this paper, we characterize the space of almost periodic (AP) functions in one variable using either a Weyl–Heisenberg (WH) system or an affine system. Our observation is that the sought-for characterization of the AP space is valid if and only if the given WH (respectively, affine) system is an L ₂(ℝ)-frame. Moreover, the frame bounds of the system are also the sharpest bounds in our characterization. This draws an intriguing and quite unexpected connection between L ₂(ℝ) representations and AP-representations.      

A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems

We show that the position of an input point in the Euclideand-dimensional space with respect to a given set of hyperplanes can be determined efficiently by linear decision trees. As an application, we prove that many concrete problems whose recognition versions are NP-complete, like the traveling salesman problem, many other shortest path problems, and integer programming, have polynomial-time upper bounds in the linear decision tree model of computation.     

Transience and capacity of minimal submanifolds

We prove explicit lower bounds for the capacity of annular domains of minimal submanifolds P ^m in ambient Riemannian spaces N ⁿ with sectional curvatures bounded from above. We characterize the situations in which the lower bounds for the capacity are actually attained. Furthermore we apply these bounds to prove that Brownian motion defined on a complete minimal submanifold is transient when the ambient space is a negatively curved Hadamard-Cartan manifold. The proof stems directly from the capacity bounds and also covers the case of minimal submanifolds of dimension m > 2 in Euclidean spaces.     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.