The basic feasible functionals in computable analysis

We give a correspondence between two notions of complexity for real functions: poly-time computability according to Ko and a notion that arises naturally when one considers the application of Mehlhorn's class of the basic feasible functionals to computable analysis. We show that both notions define the same set of polynomial-time computable real functions.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

A posteriori error estimation for variational problems with uniformly convex functionals

The objective of this paper is to introduce a general scheme for deriving a posteriori error estimates by using duality theory of the calculus of variations. We consider variational problems of the form

where is a convex lower semicontinuous functional, is a uniformly convex functional, and are reflexive Banach spaces, and is a bounded linear operator. We show that the main classes of a posteriori error estimates known in the literature follow from the duality error estimate obtained and, thus, can be justified via the duality theory.

     

Extrema of matrix functionals

The problem of determining conditional extrema of functionals with matrix arguments is considered. We derive the necessary and sufficient mathematical conditions for the existence of extrema of functionals satisfying constraints of the form of matrix equalities on the arguments. The construction of extrema is based on functions and matrices of indeterminate Lagrange multipliers. As applications we consider an example of determining the optimal strength coefficient matrix in a dynamical system with an adaptive Carleman filter and an example, from the theory of statistical decisions, of minimizing the volume of the dispersion error ellipsoid. Our approach has wide applications not only in optimization problems from automatic control theory but also in mathematical statistics and the theory of material strength and plasticity.Translated from Dinamicheskie Sistemy, No. 5, pp. 103–106, 1986.     

Adaptation under probabilistic error for estimating linear functionals

The problem of estimating linear functionals based on Gaussian observations is considered. Probabilistic error is used as a measure of accuracy and attention is focused on the construction of adaptive estimators which are simultaneously near optimal under probabilistic error over a collection of convex parameter spaces. In contrast to mean squared error it is shown that fully rate optimal adaptive estimators can be constructed for probabilistic error. A general construction of such estimators is provided and examples are given to illustrate the general theory.     

Guaranteed and locally computable a posteriori error estimate

^** Email: vejchod{at}math.cas.cz A new approach, based on the combination of the equilibratedresidual method and the method of hypercircle, is proposed fora posteriori error estimation. Computer implementation of theequilibrated residual method is fast, but it does not produceguaranteed estimates. On the other hand, the method of hypercircledelivers guaranteed estimates, but it is not fast because itinvolves solving a global linear algebraic system. The combinationof these two methods leads to guaranteed and locally computablea posteriori error estimator. This combined method is appliedto linear elliptic problem in two dimensions with mixed boundaryconditions and non-negative absolute terms.     

A distance bound for pseudospectra of matrix polynomials

In this note, we obtain a lower bound for the distance between the pseudospectrum of a matrix polynomial and a given point that lies out of it, generalizing a known result on pseudospectra of matrices.     

Efficient computable error bounds for discontinuous Galerkin approximations of elliptic problems

We present guaranteed and computable both sided error bounds for the discontinuous Galerkin (DG) approximations of elliptic problems. These estimates are derived in the full DG-norm on purely functional grounds by the analysis of the respective differential problem, and thus, are applicable to any qualified DG approximation. Based on the triangle inequality, the underlying approach has the following steps for a given DG approximation: (1) computing a conforming approximation in the energy space using the Oswald interpolation operator, and (2) application of the existing functional a posteriori error estimates to the conforming approximation. Various numerical examples with varying difficulty in computing the error bounds, from simple problems of polynomial-type analytic solution to problems with analytic solution having sharp peaks, or problems with jumps in the coefficients of the partial differential equation operator, are presented which confirm the efficiency and the robustness of the estimates.     

凸集值映射的整体误差界

考虑了凸集值映射的整体误差界，推广Li和Singer(1998)的主要定理到无界情形并肯定地回答了该文的猜想．作为应用，给出了线性Hoffman误差界定理一个简单的新证明．     

An error bound for fixed-point iterations

We derive an error bound for fixed-point iterationsx _n+1=f(x _n ) by using monotonicity in the sense of [2]. The new bound is preferable to the classical one which bounds the error in terms of the Lipschitz constant off.     

A global error bound for quadratic perturbation of linear programs

We prove a global error bound result on the quadratic perturbation of linear programs. The error bound is stated in terms of function values.     

Global error bound for convex inclusion problems

The existence of global error bound for convex inclusion problems is discussed in this paper, including pointwise global error bound and uniform global error bound. The existence of uniform global error bound has been carefully studied in Burke and Tseng (SIAM J. Optim. 6(2), 265–282, 1996) which unifies and extends many existing results. Our results on the uniform global error bound (see Theorem 3.2) generalize Theorem 9 in Burke and Tseng (1996) by weakening the constraint qualification and by widening the varying range of the parameter. As an application, the existence of global error bound for convex multifunctions is also discussed.     

Rate of convergence bound for approximating sequences in minimization problems for functionals

A general approximation scheme for minimization of functionals in a Banach space is considered. Inequalities are proved which supply bounds on the rate of convergence of the approximate solutions to the exact solution. These bounds are applied to an optimal control problem for an abstract operator equation in a Hilbert space with control in the right-hand side.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 59, pp. 117–121, 1986.     

Estimation error for occupation time functionals of stationary Markov processes

The approximation of integral functionals with respect to a stationary Markov process by a Riemann sum estimator is studied. Stationarity and the functional calculus of the infinitesimal generator of the process are used to explicitly calculate the estimation error and to prove a general finite sample error bound. The presented approach admits general integrands and gives a unifying explanation for different rates obtained in the literature. Several examples demonstrate how the general bound can be related to well-known function spaces.     

A posteriori error bound methods for the inclusion of polynomial zeros

Using Carstensen's results from 1991 we state a theorem concerning the localization of polynomial zeros and derive two a posteriori error bound methods with the convergence order 3 and 4. These methods possess useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. We establish computationally verifiable initial conditions that guarantee the convergence of these methods. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples. A comparison of a posteriori error bound methods with the corresponding circular interval methods, regarding the computational costs and sizes of produced inclusion disks, were given.     

A Lipschitzian error bound for monotone symmetric cone linear complementarity problem

We first discuss some properties of the solution set of a monotone symmetric cone linear complementarity problem (SCLCP), and then consider the limiting behaviour of a sequence of strictly feasible solutions within a wide neighbourhood of central trajectory for the monotone SCLCP. Under assumptions of strict complementarity and Slater’s condition, we provide four different characterizations of a Lipschitzian error bound for the monotone SCLCP in general Euclidean Jordan algebras. Thanks to the observation that a pair of primal-dual convex quadratic symmetric cone programming (CQSCP) problems can be exactly formulated as the monotone SCLCP, thus we obtain the same error bound results for CQSCP as a by-product.     

A posteriori error estimates for approximate solutions to variational problems with strongly convex functionals

A method of obtaining a posteriori estimates for the difference between an exact solution and an approximate solution is suggested. The method is based on the duality theory of variational calculus. The general form of such an estimate is derived for a broad class of variational problems. The estimate converges to zero as the approximate solution converges to the exact one. The general estimates are considered in detail for some classes of variational problems. Bibliography: 25 titles. Translated fromProblemy Matematicheskogo Analiza, No. 17, 1997, pp. 227–237.     

Guaranteed and computable bounds of the limit load for variational problems with linear growth energy functionals

The paper is concerned with guaranteed and computable bounds of the limit (or safety) load, which is one of the most important quantitative characteristics of mathematical models associated with linear growth functionals. We suggest a new method for getting such bounds and illustrate its performance. First, the main ideas are demonstrated with the paradigm of a simple variational problem with a linear growth functional defined on a set of scalar valued functions. Then, the method is extended to classical plasticity models governed by vonMises and Drucker-Prager yield laws. The efficiency of the proposed approach is confirmed by several numerical experiments.     

Risk-averse stochastic optimal control: An efficiently computable statistical upper bound

In this paper, we discuss an application of the Stochastic Dual Dynamic Programming (SDDP) type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of research. The bound holds for a large class of convex and monotone conditional risk mappings. Finally, we show the validity of the statistical upper bound to solve a real-life stochastic hydro-thermal planning problem.     

A bound for the condition of a hyperbolic eigenvector matrix

The hyperbolic eigenvector matrix is a matrix X which simultaneously diagonalizes the pair (H,J), where H is Hermitian positive definite and J = diag(±1) such that X*HX = Δ and X*JX = J. We prove that the spectral condition of X, κ(X), is bounded byK(X)√minK(D^*HD), where the minimum is taken over all non-singular matrices D which commute with J. This bound is attainable and it can be simply computed. Similar results hold for other signature matrices J, like in the discretized Klein—Gordon equation.