One Approach to the Comparison of Error Bounds at a Point and on a Set in the Solution of Ill-Posed Problems

The approximate solution of ill-posed problems by the regularization method always involves the issue of estimating the error. It is a common practice to use uniform bounds on the whole class of well-posedness in terms of the modulus of continuity of the inverse operator on this class. Local error bounds, which are also called error bounds at a point, have been studied much less. Since the solution of a real-life ill-posed problem is unique, an error bound obtained on the whole class of well-posedness roughens to a great extent the true error bound. In the present paper, we study the difference between error bounds on the class of well-posedness and error bounds at a point for a special class of ill-posed problems. Assuming that the exact solution is a piecewise smooth function, we prove that an error bound at a point is infinitely smaller than the exact bound on the class of well-posedness.     

Two Error Bounds for Constrained Optimization Problems and Their Applications

This paper presents a global error bound for the projected gradient and a local error bound for the distance from a feasible solution to the optimal solution set of a nonlinear programming problem by using some characteristic quantities such as value function, trust region radius etc., which are appeared in the trust region method. As applications of these error bounds, we obtain sufficient conditions under which a sequence of feasible solutions converges to a stationary point or to an optimal solution, respectively, and a necessary and sufficient condition under which a sequence of feasible solutions converges to a Kuhn–Tucker point. Other applications involve finite termination of a sequence of feasible solutions. For general optimization problems, when the optimal solution set is generalized non-degenerate or gives generalized weak sharp minima, we give a necessary and sufficient condition for a sequence of feasible solutions to terminate finitely at a Kuhn–Tucker point, and a  sufficient condition which guarantees that a sequence of feasible solutions terminates finitely at a stationary point. This research was supported by the National Natural Science Foundation of China (10571106) and CityU Strategic Research Grant.     

Conjugate residual methods for almost symmetric linear systems

This paper concerns the use of conjugate residual methods for the solution of nonsymmetric linear systems arising in applications to differential equations. We focus on an application derived from a seismic inverse problem. The linear system is a small perturbation to a symmetric positive-definite system, the nonsymmetries arising from discretization errors in the solution of certain boundary-value problems. We state and prove a new error bound for a class of generalized conjugate residual methods; we show that, in some cases, the perturbed symmetric problem can be solved with an error bound similar to the one for the conjugate residual method applied to the symmetric problem. We also discuss several applications for special distributions of eigenvalues.This work was supported in part by the National Science Foundation, Grants DMS-84-03148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

BVPs on infinite intervals: A test problem,a nonstandard finite difference scheme and a posteriori error estimator

As far as the numerical solution of boundary value problems defined on an infinite interval is concerned, in this paper, we present a test problem for which the exact solution is known. Then we study an a posteriori estimator for the global error of a nonstandard finite difference scheme previously introduced by the authors. In particular, we show how Richardson extrapolation can be used to improve the numerical solution using the order of accuracy and numerical solutions from 2 nested quasi‐uniform grids. We observe that if the grids are sufficiently fine, the Richardson error estimate gives an upper bound of the global error.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

An approximate solution for linear boundary-value problems with slowly varying coefficients

In this paper, an approximate closed-form solution for linear boundary-value problems with slowly varying coefficient matrices is obtained. The derivation of the approximate solution is based on the freezing technique, which is commonly used in analyzing the stability of slowly varying initial-value problems as well as solving them. The error between the approximate and the exact solutions is given, and an upper bound on the norm of the error is obtained. This upper bound is proportional to the rate of change of the coefficient matrix of the boundary-value problem. The proposed approximate solution is obtained for a two-point boundary-value problem and is compared to its solution obtained numerically. Good agreement is observed between the approximate and the numerical solutions, when the rate of change of the coefficient matrix is small.     

A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems

We prove a new local upper Lipschitz stability result and the associated local error bound for solutions of parametric Karush–Kuhn–Tucker systems corresponding to variational problems with Lipschitzian base mappings and constraints possessing Lipschitzian derivatives, and without any constraint qualifications. This property is equivalent to the appropriately extended to this nonsmooth setting notion of noncriticality of the Lagrange multiplier associated to the primal solution, which is weaker than second-order sufficiency. All this extends several results previously known only for optimization problems with twice differentiable data, or assuming some constraint qualifications. In addition, our results are obtained in the more general variational setting.     

Error estimate for the modified Newton method with applications to the solution of nonlinear,two-point boundary-value problems

The solution of nonlinear, two-point boundary value problems by Newton's method requires the formation and factorization of a Jacobian matrix at every iteration. For problems in which the cost of performing these operations is a significant part of the cost of the total calculation, it is natural to consider using the modified Newton method. In this paper, we derive an error estimate which enables us to determine an upper bound for the size of the sequence of modified Newton iterates, assuming that the Kantorovich hypotheses are satisfied. As a result, we can efficiently determine when to form a new Jacobian and when to continue the modified Newton algorithm. We apply the result to the solution of several nonlinear, two-point boundary value problems occurring in combustion.     

Noniterative solution of inverse problems by the linear least square method

In this paper, a noniterative linear least-squares error method developed by Yang and Chen for solving the inverse problems is re-examined. For the method, condition for the existence of a unique solution and the error bound of the resulting inverse solution considering the measurement errors are derived. Though the method was shown to be able to give the unique inverse solution at only one iteration in the literature, however, it is pointed out with two examples that for some inverse problems the method is practically not applicable, once the unavoidable measurement errors are included. The reason behind this is that the so-called reverse matrix for these inverse problems has a huge number of 1-norm, thus, magnifying a small measurement error to an extent that is unacceptable for the resulting inverse solution in a practical sense. In other words, the method fails to yield a reasonable solution whenever applied to an ill-conditioned inverse problem. In such a case, two approaches are recommended for decreasing the very high condition number: (i) by increasing the number of measurements or taking measurements as close as possible to the location at which the to-be-estimated unknown condition is applied, and (ii) by using the singular value decomposition (SVD).     

Elliptic systems and numerical transformations

Properties of a transformation method which has been developed for solving fluid dynamic problems on general two-dimensional regions are discussed. These include the error in the construction of the transformation and applications to mesh generation. An error and stability analysis for the numerical solution of a model parabolic problem is also presented.     

Backward perturbation analysis for scaled total least‐squares problems

The scaled total least‐squares (STLS) method unifies the ordinary least‐squares (OLS), the total least‐squares (TLS), and the data least‐squares (DLS) methods. In this paper we perform a backward perturbation analysis of the STLS problem. This also unifies the backward perturbation analyses of the OLS, TLS and DLS problems. We derive an expression for an extended minimal backward error of the STLS problem. This is an asymptotically tight lower bound on the true minimal backward error. If the given approximate solution is close enough to the true STLS solution (as is the goal in practice), then the extended minimal backward error is in fact the minimal backward error. Since the extended minimal backward error is expensive to compute directly, we present a lower bound on it as well as an asymptotic estimate for it, both of which can be computed or estimated more efficiently. Our numerical examples suggest that the lower bound gives good order of magnitude approximations, while the asymptotic estimate is an excellent estimate. We show how to use our results to easily obtain the corresponding results for the OLS and DLS problems in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

Global Error Bound for the Generalized Linear Complementarity Problem over a Polyhedral Cone

In this paper, the global error bound estimation for the generalized linear complementarity problem over a polyhedral cone (GLCP) is considered. To obtain a global error bound for the GLCP, we first develop some equivalent reformulations of the problem under milder conditions and then characterize the solution set of the GLCP. Based on this, an easily computable global error bound for the GLCP is established. The results obtained in this paper can be taken as an extension of the existing global error bound for the classical linear complementarity problems. This work was supported by the Research Grant Council of Hong Kong, a Chair Professor Fund of The Hong Kong Polytechnic University, the Natural Science Foundation of China (Grant No. 10771120) and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Galerkin-wavelet methods for two-point boundary value problems

Summary Anti-derivatives of wavelets are used for the numerical solution of differential equations. Optimal error estimates are obtained in the applications to two-point boundary value problems of second order. The orthogonal property of the wavelets is used to construct efficient iterative methods for the solution of the resultant linear algebraic systems. Numerical examples are given.This work was supported by National Science Foundation     

Error bounds for finite element solutions of mildly nonlinear elliptic boundary value problems

Summary The equivalence in a Hilbert space of variational and weak formulations of linear elliptic boundary value problems is well known. This same equivalence is proved here for mildly nonlinear problems where the right hand side of the differential equation involves the solution function. A finite element approximation to the solution of the weak problem ina finite dimensional subspace of the original Hilbert space is defined. An inequality bounding the error in this approximation over all functions of the space is derived, and in particular this holds for an interpolant to the weak solution. Thus this inequality, together with previously known, interpolation error bounds, produces a bound on the finite element solution to this nonlinear problem. An example of a mildly nonlinear Poisson problem is given.     

On penalty method for equilibrium problems in lexicographic order

In this paper, we consider lexicographic vector equilibrium problems. We propose a penalty function method for solving such problems. We show that every penalty trajectory of the penalized lexicographic equilibrium problem tends to the solution of the original problem. Using the regularized gap function to obtain an error bound result for such penalized problems is given.     

A multigrid method for grid generation with line-spacing control

A multigrid method for grid generation on two-dimensional regions and its applications to test problems are presented. The multigrid algorithm deals with the solution of elliptic differential problems which occur in the computation of boundary-fitted grids. The solution of elliptic systems of partial differential equations, which correspond to transformed Poisson systems, is carried out by a full approximation storage (FAS) algorithm. The components of the method, such as the relaxation for error smoothing and the coarsening strategy, are evaluated on problems in which sources of attractions are considered, and the generated grids are shown by figures.     

Computable Error Bounds for Semidefinite Programming

We study computability and applicability of error bounds for a given semidefinite pro-gramming problem under the assumption that the recession function associated with the constraint system satisfies the Slater condition. Specifically, we give computable error bounds for the distances between feasible sets, optimal objective values, and optimal solution sets in terms of an upper bound for the condition number of a constraint system, a Lipschitz constant of the objective function, and the size of perturbation. Moreover, we are able to obtain an exact penalty function for semidefinite programming along with a lower bound for penalty parameters. We also apply the results to a class of statistical problems.     

Error bounds for the approximative solution of restricted planar location problems

Facility location problems in the plane play an important role in mathematical programming. When looking for new locations in modeling real-world problems, we are often confronted with forbidden regions, that are not feasible for the placement of new locations. Furthermore these forbidden regions may have complicated shapes, even if we require them to be convex. It may be more useful or even necessary to use approximations of such forbidden regions when trying to solve location problems. In this paper, we develop error bounds for the approximative solution of restricted planar location problems using the so called sandwich algorithm. The number of approximation steps required to achieve a specified error bound is analyzed. As examples of these approximation schemes, we discuss round norms and polyhedral norms. Computational tests are also included.     

Error bound results for generalized D-gap functions of nonsmooth variational inequality problems

Solving a variational inequality problem can be equivalently reformulated into solving a unconstraint optimization problem where the corresponding objective function is called a merit function. An important class of merit function is the generalized D-gap function introduced in [N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92 (1997) 439-456] and Yamashita and Fukushima (1997) [17]. In this paper, we present new fractional local/global error bound results for the generalized D-gap functions of nonsmooth variational inequality problems, which gives an effective estimate on the distance between a specific point to the solution set, in terms of the corresponding function value of the generalized D-gap function. Numerical examples and a simple application to the free boundary problem are also presented to illustrate the significance of our error bound results.     

An extrapolated TSVD method for linear discrete ill-posed problems with Kronecker structure

This paper describes a new numerical method for the solution of large linear discrete ill-posed problems, whose matrix is a Kronecker product. Problems of this kind arise, for instance, from the discretization of Fredholm integral equations of the first kind in two space-dimensions with a separable kernel. The available data (right-hand side) of many linear discrete ill-posed problems that arise in applications is contaminated by measurement errors. Straightforward solution of these problems generally is not meaningful because of severe error propagation. We discuss how to combine the truncated singular value decomposition (TSVD) with reduced rank vector extrapolation to determine computed approximate solutions that are fairly insensitive to the error in the data. Exploitation of the structure of the problem keeps the computational effort quite small.