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.     

On Backward p(x)-Parabolic Equations for Image Enhancement

In this study, we investigate the backward p(x)-parabolic equation as a new methodology to enhance images. We propose a novel iterative regularization procedure for the backward p(x)-parabolic equation based on the nonlinear Landweber method for inverse problems. The proposed scheme can also be extended to the family of iterative regularization methods involving the nonlinear Landweber method. We also investigate the connection between the variable exponent p(x) in the proposed energy functional and the diffusivity function in the corresponding Euler-Lagrange equation. It is well known that the forward problems converges to a constant solution destroying the image. The purpose of the approach of the backward problems is twofold. First, solving the backward problem by a sequence of forward problems, we obtain a smooth image which is denoised. Second, by choosing the initial data properly, we try to reduce the blurriness of the image. The numerical results for denoising appear to give improvement over standard methods as shown by preliminary results.     

A convergence analysis of an inexact Newton-Landweber iteration method for nonlinear problem

In this paper, we study the convergence and the convergence rates of an inexact Newton–Landweber iteration method for solving nonlinear inverse problems in Banach spaces. Opposed to the traditional methods, we analyze an inexact Newton–Landweber iteration depending on the Hölder continuity of the inverse mapping when the data are not contaminated by noise. With the namely Hölder-type stability and the Lipschitz continuity of DF, we prove convergence and monotonicity of the residuals defined by the sequence induced by the iteration. Finally, we discuss the convergence rates.     

A New Gradient Method for Ill-Posed Problems

In this paper, we present a new gradient method for linear and nonlinear ill-posed problems F(x) = y. Combined with the discrepancy principle as stopping rule it is a regularization method that yields convergence to an exact solution if the operator F satisfies a tangential cone condition. If the exact solution satisfies smoothness conditions, then even convergence rates can be proven. Numerical results show that the new method in most cases needs less iteration steps than Landweber iteration, the steepest descent or minimal error method.     

An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

We consider linear inverse problems where the solution is assumed to have a sparse expansion on an arbitrary preassigned orthonormal basis. We prove that replacing the usual quadratic regularizing penalties by weighted ??^p‐penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem. Use of such ??^p‐penalized problems with p < 2 is often advocated when one expects the underlying ideal noiseless solution to have a sparse expansion with respect to the basis under consideration. To compute the corresponding regularized solutions, we analyze an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm. © 2004 Wiley Periodicals, Inc.     

Study of a special nonlinear problem arising in convex semi-infinite programming

We consider convex problems of semi-infinite programming (SIP) using an approach based on the implicit optimality criterion. This criterion allows one to replace optimality conditions for a feasible solution x ⁰ of the convex SIP problem by such conditions for x ⁰ in some nonlinear programming (NLP) problem denoted by NLP(I(x ⁰)). This nonlinear problem, constructed on the base of special characteristics of the original SIP problem, so-called immobile indices and their immobility orders, has a special structure and a diversity of important properties. We study these properties and use them to obtain efficient explicit optimality conditions for the problem NLP(I(x ⁰)). Application of these conditions, together with the implicit optimality criterion, gives new efficient optimality conditions for convex SIP problems. Special attention is paid to SIP problems whose constraints do not satisfy the Slater condition and to problems with analytic constraint functions for which we obtain optimality conditions in the form of a criterion. Comparison with some known optimality conditions for convex SIP is provided.     

On the order optimality of the regularization via inexact Newton iterations

Inexact Newton regularization methods have been proposed by Hanke and Rieder for solving nonlinear ill-posed inverse problems. Every such a method consists of two components: an outer Newton iteration and an inner scheme providing increments by regularizing local linearized equations. The method is terminated by a discrepancy principle. In this paper we consider the inexact Newton regularization methods with the inner scheme defined by Landweber iteration, the implicit iteration, the asymptotic regularization and Tikhonov regularization. Under certain conditions we obtain the order optimal convergence rate result which improves the suboptimal one of Rieder. We in fact obtain a more general order optimality result by considering these inexact Newton methods in Hilbert scales.     

Robust residual‐ and recovery‐based a posteriori error estimators for a multipoint flux mixed finite element discretization of interface problems

We consider a posteriori error estimation for a multipoint flux mixed finite element method for two‐dimensional elliptic interface problems. Within the class of modified quasi‐monotonically distributed coefficients, we derive a residual‐type a posteriori error estimator of the weighted sum of the scalar and flux errors which is robust with respect to the jumps of the coefficients. Moreover, we develop robust implicit and explicit recovery‐type estimators through gradient recovery in an H(curl)‐conforming finite element space. In particular, we apply a modified L² projection in the implicit recovery procedure so as to reduce the computational cost of the recovered gradient. Numerical experiments confirm the theoretical results.     

A Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations

In this paper, we investigate the convergence behavior of a Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations. In order to improve the stability and convergence of the Landweber iteration, a 2-stage Gauss-type Runge–Kutta method is applied to the continuous analogy of the modified Landweber method, to give a new modified Landweber method, called R–K type modified Landweber method. Under some appropriate conditions, we prove the convergence of the proposed method. We conclude with a numerical example confirming the theoretical results, including comparisons to the modified Landweber iteration.     

Runge‐Kutta Type Methods for Ill‐Posed Problems and the Retrieval of Aerosol Size Distributions

The present paper deals with new explicit and implicit Runge‐Kutta type iteration methods as a regularization tool for ill‐posed problems. These methods are a generalization of the well‐known Landweber method. An application to Atmospheric Physics in determining the aerosol size distribution is given.     

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.     

Frozen Landweber Iteration for Nonlinear Ill-Posed Problems

In this paper we propose a modification of the Landweber iteration termed frozen Landweberiteration for nonlinear ill-posed problems.A convergence analysis for this iteration is presented.The numericalperformance of this frozen Landweber iteration for a nonlinear Hammerstein integral equation is compared withthat of the Landweber iteration.We obtain a shorter running time of the frozen Landweber iteration based onthe same convergence accuracy.     

基于埃特金加速的改进Landweber迭代正则化方法

为克服Landweber迭代正则化方法在求解大规模不适定问题时收敛速度慢的不足,将埃特金加速技巧与不动点迭代相结合,构建了能快速收敛的改进Landweber迭代正则化方法.数值实验结果表明:改进的迭代正则化方法在稳定求解不适定问题时,能够快速地收敛至问题的最优解,较Landweber迭代正则化方法大大提高了收敛速度.     

High‐order numerical methods for one‐dimensional parabolic singularly perturbed problems with regular layers

In this work we construct and analyze some finite difference schemes used to solve a class of time‐dependent one‐dimensional convection‐diffusion problems, which present only regular layers in their solution. We use the implicit Euler or the Crank‐Nicolson method to discretize the time variable and a HODIE finite difference scheme, defined on a piecewise uniform Shishkin mesh, to discretize the spatial variable. In both cases we prove that the numerical method is uniformly convergent with respect to the diffusion parameter, having order near two in space and order one or 3/2, depending on the method used, in time. We show some numerical examples which illustrate the theoretical results, in the case of using the Euler implicit method, and give better numerical behaviour than that predicted theoretically, showing order two in time and order N^?2log²N in space, if the Crank‐Nicolson scheme is used to discretize the time variable. Finally, we construct a numerical algorithm by combining a third order A‐stable SDIRK with two stages and a third‐order HODIE difference scheme, showing its uniformly convergent behavior, reaching order three, up to a logarithmic factor. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

求解不适定问题的快速Landweber迭代法

本文从一般迭代法的级数形式出发，将一般迭代法的每一步分解为矩阵计算和求解两步，并对其中的矩阵计算部分进行了修改，在此基础上提出了快速迭代法，最后通过数值实验验证了我们的算法不仅提高了计算速度，同时也大大减少了计算量，是一种效率很高的算法。     

A Tensor product generalized ADI method for the method of planes

We consider solving separable, second order, linear elliptic prtial differential equations in three independent variables. If the partial differential opertor separates into two terms, one depending on x and y, and one depending on z, then we use the method of planes to obtain a discrete problem, which we write in tensor product from as We apply a new interative method, the tensor product generalized alternating direction implicit method, to solve the discrete problem. We study a specific implementation that uses Hermite bicubic collocation in the xy direction and symmetric finite differences in the z direction. We demostrate that this method is a fast and accurate way to solve the large linear systems arising from three-dimensional elliptic problems.     

How Competitive is the ADI for Tensor Structured Equations?

In [1] we presented an extension of the alternating direction implicit (ADI) method for the solution of Lyapunov equations (1) to higher dimensional problems. The vectorized form of the Lyapunov equation is We considered the generalization of this equation of the form (2) The tensor train structure is one possible generalization of the low rank factorization we find in the right hand side of (1). Therefor we assume B to be of tensor train structure. We showed that in analogy to the low rank ADI case the solution X can be generated in tensor train structure, too. Further we provided an algorithm that computes X using a generalization of the ADI method. Here we compare our new tensor ADI method with an density matrix renormalization group (DMRG) solver for tensor train matrix equations and with matrix equation solvers to investigate the competitiveness of our new solver. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Implicit multifunction theorems for the sensitivity analysis of variational conditions

We study implicit multifunctions (set-valued mappings) obtained from inclusions of the form 0∈M(p,x), whereM is a multifunction. Our basic implicit multifunction theorem provides an approximation for a generalized derivative of the implicit multifunction in terms of the derivative of the multifunctionM. Our primary focus is on three special cases of inclusions 0∈M(p,x) which represent different kinds of generalized variational inequalities, called “variational conditions”. Appropriate versions of our basic implicit multifunction theorem yield approximations for generalized derivatives of the solutions to each kind of variational condition. We characterize a well-known generalized Lipschitz property in terms of generalized derivatives, and use our implicit multifunction theorems to state sufficient conditions (and necessary in one case) for solutions of variational conditions to possess this Lipschitz, property. We apply our results to a general parameterized nonlinear programming problem, and derive a new second-order condition which guarantees that the stationary points associated with the Karush-Kuhn-Tucker conditions exhibit generalized Lipschitz continuity with respect to the parameter.     

Stability for parametric implicit vector equilibrium problems

In this paper, we consider a class of parametric implicit vector equilibrium problems in Hausdorff topological vector spaces where a mapping f and a set K are perturbed by parameters and λ, respectively. We establish sufficient conditions for the upper semicontinuity and lower semicontinuity of the solution set mapping S:Λ₁×Λ₂→2^X for such parametric implicit vector equilibrium problems.     

On the solvability of a nonlocal boundary value problem with the equality of fluxes at a part of the boundary and of the adjoint problem

In the present paper, we consider a nonlocal boundary value problem for the Laplace operator in a circular sector with the equality of fluxes on the radii and with zero value of the solution on one of the radii. We also consider the adjoint problem. We prove the uniqueness of the solution of these problems and obtain an explicit form for the solution by the spectral method. When proving the solvability of the problems, we study the completeness and the basis property of systems of root functions for problems of the type of the Samarskii-Ionkin problem in L _p , which can be of interest in itself.