On Lanczos Based Methods for the Regularization of Discrete Ill-Posed Problems

We study hybrid methods for the solution of linear ill-posed problems. Hybrid methods are based on he Lanczos process, which yields a sequence of small bidiagonal systems approximating the original ill-posed problem. In a second step, some additional regularization, typically the truncated SVD, is used to stabilize the iteration. We investigate two different hybrid methods and interpret these schemes as well-known projection methods, namely least-squares projection and the dual least-squares method. Numerical results are provided to illustrate the potential of these methods. This gives interesting insight in to the behavior of hybrid methods in practice.This revised version was published online in October 2005 with corrections to the Cover Date.     

A truncated projected SVD method for linear discrete ill-posed problems

Truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. However, since the singular value decomposition of the matrix is independent of the right-hand side, there are linear discrete ill-posed problems for which this method fails to yield an accurate approximate solution. This paper describes a new approach to incorporating knowledge about properties of the desired solution into the solution process through an initial projection of the linear discrete ill-posed problem. The projected problem is solved by truncated singular value decomposition. Computed examples illustrate that suitably chosen projections can enhance the accuracy of the computed solution.     

最优投影策略下解病态积分方程的快速迭代算法

基于最优的投影方法,构造了求解病态积分方程的截断快速Tikhonov迭代算法,与传统投影方法相比得到了相同的最优收敛率,但内积的计算个数少于传统投影方法.同时,给出了后验参数选择办法.算例证实了算法的有效性.     

On a Family of Gradient-Type Projection Methods for Nonlinear Ill-Posed Problems

Abstract

We propose and analyze a family of successive projection methods whose step direction is the same as the Landweber method for solving nonlinear ill-posed problems that satisfy the Tangential Cone Condition (TCC). This family encompasses the Landweber method, the minimal error method, and the steepest descent method; thus, providing an unified framework for the analysis of these methods. Moreover, we define new methods in this family, which are convergent for the constant of the TCC in a range twice as large as the one required for the Landweber and other gradient type methods. The TCC is widely used in the analysis of iterative methods for solving nonlinear ill-posed problems. The key idea in this work is to use the TCC in order to construct special convex sets possessing a separation property, and to successively project onto these sets. Numerical experiments are presented for a nonlinear two-dimensional elliptic parameter identification problem, validating the efficiency of our method.     

A minimal error conjugate gradient method for ill-posed problems

For the ill-posed operator equationTx=y in Hilbert space, we introduce a modification of the usual conjugate gradient method which minimizes the error, not the residual, at each step. Moreover, the error is minimized over the same finite-dimensional subspace that is associated with the usual method.This work was completed while the author was on leave at the University of Tennessee, Knoxville, Tennessee. Travel support from the Taft Committee and from the University of Tennessee is gratefully acknowledged.     

A combined penalty function and gradient projection method for nonlinear programming

A new programming algorithm for nonlinear constrained optimization problems is proposed. The method is based on the penalty function approach and thereby circumyents the necessity to maintain feasibility at each iteration, but it also behaves much like the gradient projection method. Although only first-order information is used, the algorithm converges asymptotically at a rate which is independent of the magnitude of the penalty term; hence, unlike the simple gradient method, the asymptotic rate of the proposed method is not affected by the ill-conditioning associated with the introduction of the penalty term. It is shown that the asymptotic rate of convergence of the proposed method is identical with that of the gradient projection method.Dedicated to Professor M. R. HestenesThis research was supported by the National Science Foundation, Grant No. GK-16125.     

V-cycle convergence of some multigrid methods for ill-posed problems

For ill-posed linear operator equations we consider some V-cycle multigrid approaches, that, in the framework of Bramble, Pasciak, Wang, and Xu (1991), we prove to yield level independent contraction factor estimates. Consequently, we can incorporate these multigrid operators in a full multigrid method, that, together with a discrepancy principle, is shown to act as an iterative regularization method for the underlying infinite-dimensional ill-posed problem. Numerical experiments illustrate the theoretical results.

     

Geometrically convergent projection method in matrix games

We propose a method which evaluates the solution of a matrix game. We reduce the problem of the search for the solution to a convex feasibility problem for which we present a method of projection onto an acute cone. The algorithm converges geometrically. At each iteration, we apply a combinatorial algorithm in order to evaluate the projection onto the standard simplex.     

Regularization of ill-posed constrained minimization problems by iteration methods

The ill-posed minimization problems in Hilbert space with quadratic objective function and closed convex constraint set are considered. For the compact set the regularization methods for such problems are well understood [1, 2] The regularizing properties of some Iteration projection methods for noncompact constraint set are the main issues of this paper. We are looking the gradient projection method for the sphere.     

Quasi-Newton projection methods and the discrepancy principle in image restoration

In this work, the problem of the restoration of images corrupted by space invariant blur and noise is considered. This problem is ill-posed and regularization is required. The image restoration problem is formulated as a nonnegatively constrained minimization problem whose objective function depends on the statistical properties of the noise corrupting the observed image. The cases of Gaussian and Poisson noise are both considered. A Newton-like projection method with early stopping of the iterates is proposed as an iterative regularization method in order to determine a nonnegative approximation to the original image. A suitable approximation of the Hessian of the objective function is proposed for a fast solution of the Newton system. The results of the numerical experiments show the effectiveness of the method in computing a good solution in few iterations, when compared with some methods recently proposed as best performing.     

The Optimal Approximations for Solving Linear Ill-Posed Problems

New projection discrete schemes for ill-posed problems are constructed. We show that for equations with self-adjoint operators the use of self-adjoint projection schemes is not optimal in the sense of the amount of discrete information.     

A half-space projection method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method.     

A method for the computation of nonsimple turning points corresponding to cusps

A direct method is described for the approximation of nonsimple turning points, corresponding to cusp points, of nonlinear operator equations depending on two parameters. The procedure is based on the application of a special projection method to the computation of simple turning points of a suitable augmented system. Numerical examples illustrate the features of the proposed algorithm.     

Regularisierung schlecht gestellter Probleme durch Projektionsverfahren

Summary The numerical solution of ill-posed problems by projection methods is considered. Regularization is carried out simply by choosing an optimal discretization parameter. It is shown by asymptotic estimates and by numerical examples that this kind of regularization is as efficient as the method of Tikhonov and Phillips.

     

A convergence analysis of nonlinear implicit iterative method for nonlinear ill-posed problems

Implicit iterative method acquires good effect in solving linear ill-posed problems. We have ever applied the idea of implicit iterative method to solve nonlinear ill-posed problems, under the restriction that α is appropriate large, we proved the monotonicity of iterative error and obtained the convergence and stability of iterative sequence, numerical results show that the implicit iterative method for nonlinear ill-posed problems is efficient. In this paper, we analyze the convergence and stability of the corresponding nonlinear implicit iterative method when α_k are determined by Hanke criterion.     

A Haar wavelets based approximation for nonlinear inverse problems influenced by unknown heat source

In this discussion, a new numerical algorithm focused on the Haar wavelet is used to solve linear and nonlinear inverse problems with unknown heat source. The heat source is dependent on time and space variables. These types of inverse problems are ill-posed and are challenging to solve accurately. The linearization technique converted the nonlinear problem into simple nonhomogeneous partial differential equation. In this Haar wavelet collocation method (HWCM), the time part is discretized by using finite difference approximation, and space variables are handled by Haar series approximation. The main contribution of the proposed method is transforming this ill-posed problem into well-conditioned algebraic equation with the help of Haar functions, and hence, there is no need to implement any sort of regularization technique. The results of numerical method are efficient and stable for this ill-posed problems containing different noisy levels. We have utilized the proposed method on several numerical examples and have valuable efficiency and accuracy.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

An iterative method for ill-posed problems with inequalities

Ill-posed problems for integral and operator equations with nonnegativity and band inequality constraints arise in a wide range of applications. The effect and propagation of data perturbations in mathematical programming problems are highly dramatized in the area of ill-posed problems. In this note an iterative method for solving an ill-posed integral inequality and its moment discretization is described.     

A modified projection method with a new direction for solving variational inequalities

In this paper, we propose a new projection method for solving variational inequality problems, which can be viewed as an improvement of the method of Li et al. [M. Li, L.Z. Liao, X.M. Yuan, A modified projection method for co-coercive variational inequality, European Journal of Operational Research 189 (2008) 310-323], by adopting a new direction. Under the same assumptions as those in Li et al. (2008), we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported, which illustrated that the new method is more efficient than the method of Li et al. (2008).     

Modified self-adaptive projection method for solving pseudomonotone variational inequalities

In this paper, a self-adaptive projection method with a new search direction for solving pseudomonotone variational inequality (VI) problems is proposed, which can be viewed as an extension of the methods in [B.S. He, X.M. Yuan, J.Z. Zhang, Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications 27 (2004) 247-267] and [X.H. Yan, D.R. Han, W.Y. Sun, A self-adaptive projection method with improved step-size for solving variational inequalities, Computers & Mathematics with Applications 55 (2008) 819-832]. The descent property of the new search direction is proved, which is useful to guarantee the convergence. Under the relatively relaxed condition that F is continuous and pseudomonotone, the global convergence of the proposed method is proved. Numerical experiments are provided to illustrate the efficiency of the proposed method.