An optimal parameter choice for regularized ill-posed problems

Schock has given a nearly optimal a posteriori parameter choice strategy for Tikhonov regularization. We show that a modification of his argument leads, in fact, to an optimal convergence rate.     

Lavrentiev's regularization method for nonlinear ill-posed equations in Banach spaces

In this paper, we deal with nonlinear ill-posed problems involving m-accretive mappings in Banach spaces. We consider a derivative and inverse free method for the implementation of Lavrentiev regularization method. Using general H¨older type source condition we obtain an optimal order error estimate. Also we consider the adaptive parameter choice strategy proposed by Pereverzev and Schock(2005) for choosing the regularization parameter.     

Parameter choice by discrepancy principles for ill-posed problems leading to optimal convergence rates

Schock (Ref. 1) considered a general a posteriori parameter choice strategy for the Tikhonov regularization of the ill-posed operator equationTx=y which provides nearly the optimal rate of convergence if the minimal-norm least-squares solution belongs to the range of the operator (T ^* T) ^v , o<v1. Recently, Nair (Ref. 2) improved the result of Schock and also provided the optimal rate ifv=1. In this note, we further improve the result and show in particular that the optimal rate can be achieved for 1/2v1.The final version of this work was written while M. T. Nair was a Visiting Fellow at the Centre for Mathematics and Its Applications, Australian National University, Canberra, Australia. The work of S. George was supported by a Senior Research Fellowship from CSIR, India.     

The selection of the optimal parameter in the modulus-based matrix splitting algorithm for linear complementarity problems

The modulus-based matrix splitting (MMS) algorithm is effective to solve linear complementarity problems (Bai in Numer Linear Algebra Appl 17: 917–933, 2010). This algorithm is parameter dependent, and previous studies mainly focus on giving the convergence interval of the iteration parameter. Yet the specific selection approach of the optimal parameter has not been systematically studied due to the nonlinearity of the algorithm. In this work, we first propose a novel and simple strategy for obtaining the optimal parameter of the MMS algorithm by merely solving two quadratic equations in each iteration. Further, we figure out the interval of optimal parameter which is iteration independent and give a practical choice of optimal parameter to avoid iteration-based computations. Compared with the experimental optimal parameter, the numerical results from three problems, including the Signorini problem of the Laplacian, show the feasibility, effectiveness and efficiency of the proposed strategy.

     

Exponential Tikhonov Regularization Method for Solving an Inverse Source Problem of Time Fractional Diffusion Equation

In this paper, we mainly study an inverse source problem of time fractional diffusion equation in a bounded domain with an over-specified terminal condition at a fixed time. A novel regularization method, which we call the exponential Tikhonov regularization method with a parameter $\gamma$, is proposed to solve the inverse source problem, and the corresponding convergence analysis is given under a-priori and a-posteriori regularization parameter choice rules. When $\gamma$ is less than or equal to zero, the optimal convergence rate can be achieved and it is independent of the value of $\gamma$. However, when $\gamma$ is greater than zero, the optimal convergence rate depends on the value of $\gamma$ which is related to the regularity of the unknown source. Finally, numerical experiments are conducted for showing the effectiveness of the proposed exponential regularization method.     

关于迭代Tikhonov正则化的最优正则参数选取

本文讨论了算子和右端都近似给定的第一类算子方程的迭代Ｔｉｋｈｏｎｏｖ正则化，给出了不依赖于准确解的任何信息但能得到最优收敛阶的正则参数选取法。     

Adaptive Choice of the Regularization Parameter in Numerical Differentiation

We investigate a novel adaptive choice rule of the Tikhonov regularization parameter in numerical differentiation which is a classic ill-posed problem. By assuming a general unknown Hölder type error estimate derived for numerical differentiation, we choose a regularization parameter in a geometric set providing a nearly optimal convergence rate with very limited a-priori information. Numerical simulation in image edge detection verifies reliability and efficiency of the new adaptive approach.     

Solving generalized semi-infinite programs by reduction to simpler problems

The article intends to give a unifying treatment of different approaches to solve generalized semi-infinite programs by transformation to simpler problems. In particular dual-, penalty-, discretization-, reduction-, and Karush-Kuhn-Tucker (KKT)-methods are applied to obtain equivalent problems or relaxations of a simpler structure. The relaxations are viewed as a perturbation P _τ of the original problem P, depending on a perturbation parameter τ > 0, and are analyzed by using parametric programming techniques. We give convergence results and results on the rate of convergence for the minimal values and the optimal solutions of P _τ when τ tends toward 0. We review earlier studies and present new ones.     

Accelerated Gauss-Newton algorithms for nonlinear least squares problems

Recent theoretical and practical investigations have shown that the Gauss-Newton algorithm is the method of choice for the numerical solution of nonlinear least squares parameter estimation problems. It is shown that when line searches are included, the Gauss-Newton algorithm behaves asymptotically like steepest descent, for a special choice of parameterization. Based on this a conjugate gradient acceleration is developed. It converges fast also for those large residual problems, where the original Gauss-Newton algorithm has a slow rate of convergence. Several numerical test examples are reported, verifying the applicability of the theory.     

一类求解鞍点问题的广义不精确Uzawa方法

本文提出了一类求解大型稀疏鞍点问题的新的广义不精确Uzawa算法.该方法不仅可以包含 前人的方法, 而且可以拓展出很多新方法. 理论分析给出该方法收敛的条件, 并详细的分析了其收敛性质和参数矩阵的选取方法. 通过对有限元离散的Stokes问题的数值实验表明, 新方法是行之有效的, 其收敛速度明显优于原来的算法.     

Necessary and sufficient conditions for power convergence rate of approximations in Tikhonov’s scheme for solving ill-posed optimization problems

We investigate a rate of convergence of estimates for approximations generated by Tikhonov’s scheme for solving ill-posed optimization problems with smooth functionals under a structural nonlinearity condition in a Hilbert space, in the cases of exact and noisy input data. In the noise-free case, we prove that the power source representation of the desired solution is close to a necessary and sufficient condition for the power convergence estimate having the same exponent with respect to the regularization parameter. In the presence of a noise, we give a parameter choice rule that leads for Tikhonov’s scheme to a power accuracy estimate with respect to the noise level.     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

Approximation of conformal mappings of annular regions

Summary. In this paper we examine the convergence rates in an adaptive version of an orthonormalization method for approximating the conformal mapping of an annular region onto a circular annulus. In particular, we consider the case where has an analytic extension in compl() and, for this case, we determine optimal ray sequences of approximants that give the best possible geometric rate of uniform convergence. We also estimate the rate of uniform convergence in the case where the annular region has piecewise analytic boundary without cusps. In both cases we also give the corresponding rates for the approximations to the conformal module of . Received February 2, 1996     

半正定算子方程正则解的收敛率和参数选取法

1 引言 关于第一类线性算子方程 Ax=y (1)已有很多文献和专著作过研究。由于方程(1)一般是不适定的.须用正则化方法求解.最著名的方法是Tikhonov正则化方法.关于其正则解的收敛性、收敛率及参数选取法,专著[2,3]已作了深入系统的研究.当A为半正定自共轭的有界线性算子时,可应用 Lavrent’ev正则化方法或称为简化正则化方法,由于其在计算上所具有的优越性,已引起不少学者的关注.本文将用简化正则化方法研究当A为半正定线性有界算子的情形.实际上,此时的A是一个单调算子,而对单调算子方程,已有很多研究结果,只不过主要是关于正则解的收敛性及有限维逼近的讨论,而未涉及正则解的收敛率问题。我们将在第2节中讨论正则解的收敛率.并给出一种后验的参数选取法,这种参数选取法比先验的参数选取法的优越之处在于它不依赖于解的“光滑性”条件”“,但当满足某种“光滑性”条件时,所得到的收敛率是最优的.第3节中我们讨论了当算子方程的右端数据及算子本身都为近似已知的情形,这种情形更接近于实际的数学模型。文献[13,14]曾作过研究.     

Optimal Rates for the Regularized Least-Squares Algorithm

We develop a theoretical analysis of the performance of the regularized least-square algorithm on a reproducing kernel Hilbert space in the supervised learning setting. The presented results hold in the general framework of vector-valued functions; therefore they can be applied to multitask problems. In particular, we observe that the concept of effective dimension plays a central role in the definition of a criterion for the choice of the regularization parameter as a function of the number of samples. Moreover, a complete minimax analysis of the problem is described, showing that the convergence rates obtained by regularized least-squares estimators are indeed optimal over a suitable class of priors defined by the considered kernel. Finally, we give an improved lower rate result describing worst asymptotic behavior on individual probability measures rather than over classes of priors.     

Two-layer muti-parameterized Schwarz Alternating Method

The convergence rate of a numerical procedure based on Schwarz Alternating Method (SAM) for solving elliptic boundary value problems (BVP’s) depends on the selection of the interface conditions applied on the interior boundaries of the overlapping subdomains. It has been observed that theRobin condition(mixed interface condition), controlled by a parameter, can optimize SAM’s convergence rate. Since the convergence rate is very sensitive to the parameter, Tang[17] suggested another interface condition calledover- determined interface condition. Based on the over-determined interface condition, we formulate thetwo-layer multi-parameterized SAM. For the SAM and the one-dimensional elliptic model BVP’s, we determine analytically the optimal values of the parameters. For the two-dimensional elliptic BVP’s, we also formulate the two-layer multiparameterized SAM and suggest a choice of multi-parameter to produce good convergence rate.     

An a posteriori parameter choice for simplified regularization of ill-posed problems

An a posteriori parameter choice strategy is proposed for the simplified regularization of ill-posed problems where no information about the smoothness of the unknown solution is required. If the smoothness of the solution is known then, as a particular case, the optimal rate is achieved. Our result also includes a recent result of Guacanme (1990).     

On the convergence of the Bermúdez-Moreno algorithm with constant parameters

Summary. Bermúdez-Moreno [5] presents a duality numerical algorithm for solving variational inequalities of the second kind. The performance of this algorithm strongly depends on the choice of two constant parameters. Assuming a further hypothesis of the inf-sup type, we present here a convergence theorem that improves on the one presented in [5]: we prove that the convergence is linear, and we give the expression of the asymptotic error constant and the explicit form of the optimal parameters, as a function of some constants related to the variational inequality. Finally, we present some numerical examples that confirm the theoretical results. Received June 28, 1999 / Revised version received February 19, 2001 / Published online October 17, 2001     

SOME RESULTS ON ESTIMATION OF THE TAIL INDEX OF A DISTRIBUTION

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＳｕｐｐｏｓｅｔｈａｔＦｉｓａｄｉｓｔｒｉｂｕｔｉｏｎｆｕｎｃｔｉｏｎｓｕｃｈｔｈａｔ,ｆｏｒａｎｙｘ＞０,ｌｉｍｔ→∞１－Ｆ（ｔｘ）１－Ｆ（ｔ）＝ｘ－１γ,γ＞０．（１．１）ＷｅｃａｌγｔｈｅｔａｉｌｉｎｄｅｘｏｆＦ．...     

On simplified Tikhonov regularization

Approximations to the minimal norm, least-square solution of a linear equation with positive semidefinite operator are defined in such a way that fewer computations are needed than in Tikhonov's approach. We establish necessary and sufficient conditions for convergence, and we provide a choice for the regularization parameter that brings the optimal rate of convergence.The author expresses his gratitude to C. W. Groetsch for his guidance and the recent visit to the University of Puerto Rico.