A Riemannian variant of the Fletcher–Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata

In this paper, we focus on the stochastic inverse eigenvalue problem with partial eigendata of constructing a stochastic matrix from the prescribed partial eigendata. A Riemannian variant of the Fletcher–Reeves conjugate gradient method is proposed for solving a general unconstrained minimization problem on a Riemannian manifold, and the corresponding global convergence is established under some assumptions. Then, we reformulate the inverse problem as a nonlinear least squares problem over a matrix oblique manifold, and the application of the proposed geometric method to the nonlinear least squares problem is investigated. The proposed geometric method is also applied to the case of prescribed entries and the case of column stochastic matrix. Finally, some numerical tests are reported to illustrate that the proposed geometric method is effective for solving the inverse problem.     

Recovery of an interface from boundary measurement in an elliptic differential equation

We study the inverse problem of recovering an interior interface from a boundary measurement in an elliptic boundary value problem arising from a semiconductor transistor model. We set up a nonlinear least-squares formulation for solving the inverse problem, and establish the necessary derivatives with respect to the interface. We then propose both the Gauss–Newton iterative method and the conjugate gradient method for the least-squares problem, and present implementation of these methods using integral equations.     

求解热传导反问题的一种正则化Newton型迭代法

讨论热传导方程求解系数的一个反问题．把问题归结为一个非线性不适定的算子方程后,考虑该方程的Newton型迭代方法．对线性化后的Newton方程用隐式迭代法求解,关键的一步是引入了一种新的更合理的确定(内)迭代步数的后验准则．对新方法及对照的Tikhonov方法和Bakushiskii方法进行了数值实验,结果显示了新方法具有明显的优越性．     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.     

二维椭圆型方程反问题中优化算法的比较

近年来，决定椭圆型方程系数反问题在地磁、地球物理、冶金和生物等实际问题上有着广泛的应用．本文讨论了二维的决定椭圆型方程系数反问题的数值求解方法．由误差平方和最小原则，这个反问题可化为一个变分问题，并进一步离散化为一个最优化问题，其目标函数依赖于要决定的方程系数．本文着重考察非线性共轭梯度法在此最优化问题数值计算中的表现，并与拟牛顿法作为对比．为了提高算法的效率我们适当选择加快收敛速度的预处理矩阵．同时还考察了线搜索方法的不同对优化算法的影响．数值实验的结果表明，非线性共轭梯度法在这类大规模优化问题中相对于拟牛顿法更有效．     

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper.The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces,and we also proposed an adaptive rule for choosing different searching directions at each iteration.We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition.With the used nonmonotone line search,we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions.Numerical experiments show that the proposed algorithm is promising for the given test problem set.     

无约束优化问题的修正PRP共轭梯度法

本文通过结合牛顿法与PRP共轭梯度法提出一修正PRP方法,新方法中包含了二阶导数信息,在适当的假设下算法全局收敛,数值算例表明了算法的有效性.     

On decomposition-based block preconditioned iterative methods for half-quadratic image restoration

Image restoration is a fundamental problem in image processing. Except for many different filters applied to obtain a restored image in image restoration, a degraded image can often be recovered efficiently by minimizing a cost function which consists of a data-fidelity term and a regularization term. In specific, half-quadratic regularization can effectively preserve image edges in the recovered images and a fixed-point iteration method is usually employed to solve the minimization problem. In this paper, the Newton method is applied to solve the half-quadratic regularization image restoration problem. And at each step of the Newton method, a structured linear system of a symmetric positive definite coefficient matrix arises. We design two different decomposition-based block preconditioning matrices by considering the special structure of the coefficient matrix and apply the preconditioned conjugate gradient method to solve this linear system. Theoretical analysis shows the eigenvector properties and the spectral bounds for the preconditioned matrices. The method used to analyze the spectral distribution of the preconditioned matrix and the correspondingly obtained spectral bounds are different from those in the literature. The experimental results also demonstrate that the decomposition-based block preconditioned conjugate gradient method is efficient for solving the half-quadratic regularization image restoration in terms of the numerical performance and image recovering quality.     

A Smoothing Newton Method for Semi-Infinite Programming

This paper is concerned with numerical methods for solving a semi-infinite programming problem. We reformulate the equations and nonlinear complementarity conditions of the first order optimality condition of the problem into a system of semismooth equations. By using a perturbed Fischer–Burmeister function, we develop a smoothing Newton method for solving this system of semismooth equations. An advantage of the proposed method is that at each iteration, only a system of linear equations is solved. We prove that under standard assumptions, the iterate sequence generated by the smoothing Newton method converges superlinearly/quadratically.     

多孔介质中可压缩可混溶驱动问题的共轭梯度迭代法的L2模误差估计

2006年3月 高等学校计算数学学报 1数学模型 多孔介质中可压缩可混溶驱动问题的模型是两个非线性抛物型方程:压力方程和饱 和度方程.Douglass和Roberts曾提出其数学模型并研究了半离散化方法[“一”}.袁益让对 此模型研究了特征一有限元方法[s]和差分法10]. 本人对可压缩可混溶驱动问题的模型曾研究了共扼梯度迭代解与原问题真解的最优 阶H‘模误差估计阁.其中饱和度方程的弥散项为一甲·(D(劝甲c)，而本文讨论的是D(司 情况下的尸模误差估计.就护模而言，对此模型目前尚未有人讨论过.从本文可看到， 由于饱和度方程中含有拭c)鬓这一项，…     

The Levenberg-Marquardt method applied to a parameter estimation problem arising from electrical resistivity tomography

An efficient and robust electrical resistivity tomographic inversion algorithm based on the Levenberg-Marquardt method is considered to obtain quantities like grain size, spatial scale and particle size distribution of mineralized rocks. The corresponding model in two dimensions is based on the Maxwell equations and leads to a partial differential equation with mixed Dirichlet-Neumann boundary conditions. The forward problem is solved numerically with the finite-difference method. However, the inverse problem at hand is a classical nonlinear and ill-posed parameter estimation problem. Linearizing and applying the Tikhonov regularization method yields an iterative scheme, the Levenberg-Marquardt method. Several large systems of equations have to be solved efficiently in each iteration step which is accomplished by the conjugate gradient method without setting up the corresponding matrix. Instead fast matrix-vector multiplications are performed directly. Therefore, the derivative and its adjoint for the parameter-to-solution map are needed. Numerical results demonstrate the performance of our method as well as the possibility to reconstruct some of the desired parameters.     

Convergence of a generalized Newton and an inexact generalized Newton algorithms for solving nonlinear equations with nondifferentiable terms

In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of equation. Some numerical results indicate that both algorithms works quite well in practice.      

An efficient nonlinear iteration scheme for nonlinear parabolic–hyperbolic system

A nonlinear iteration method named the Picard–Newton iteration is studied for a two-dimensional nonlinear coupled parabolic–hyperbolic system. It serves as an efficient method to solve a nonlinear discrete scheme with second spatial and temporal accuracy. The nonlinear iteration scheme is constructed with a linearization–discretization approach through discretizing the linearized systems of the original nonlinear partial differential equations. It can be viewed as an improved Picard iteration, and can accelerate convergence over the standard Picard iteration. Moreover, the discretization with second-order accuracy in both spatial and temporal variants is introduced to get the Picard–Newton iteration scheme. By using the energy estimate and inductive hypothesis reasoning, the difficulties arising from the nonlinearity and the coupling of different equation types are overcome. It follows that the rigorous theoretical analysis on the approximation of the solution of the Picard–Newton iteration scheme to the solution of the original continuous problem is obtained, which is different from the traditional error estimate that usually estimates the error between the solution of the nonlinear discrete scheme and the solution of the original problem. Moreover, such approximation is independent of the iteration number. Numerical experiments verify the theoretical result, and show that the Picard–Newton iteration scheme with second-order spatial and temporal accuracy is more accurate and efficient than that of first-order temporal accuracy.     

Consistent Numerical Schemes for Solving Nonlinear Inverse Source Problems with Gradient-Type Algorithms and Newton–Kantorovich Methods

In this paper, algorithms of solving an inverse source problem for systems of production–destruction equations are considered. Numerical schemes that are consistent to satisfy Lagrange’s identity for solving direct and adjoint problems are constructed. With the help of adjoint equations, a sensitivity operator with a discrete analog is constructed. It links perturbations of the measured values with those of the sought-for model parameters. This operator transforms the inverse problem to a quasilinear system of equations and allows applying Newton–Kantorovich methods to it. A numerical comparison of gradient algorithms based on consistent and inconsistent numerical schemes and a Newton–Kantorovich algorithm applied to solving an inverse source problem for a nonlinear Lorenz model is done.     

Enriched Methods for Large-Scale Unconstrained Optimization

This paper describes a class of optimization methods that interlace iterations of the limited memory BFGS method (L-BFGS) and a Hessian-free Newton method (HFN) in such a way that the information collected by one type of iteration improves the performance of the other. Curvature information about the objective function is stored in the form of a limited memory matrix, and plays the dual role of preconditioning the inner conjugate gradient iteration in the HFN method and of providing an initial matrix for L-BFGS iterations. The lengths of the L-BFGS and HFN cycles are adjusted dynamically during the course of the optimization. Numerical experiments indicate that the new algorithms are both effective and not sensitive to the choice of parameters.     

A REVISED CONJUGATE GRADIENT PROJECTION ALGORITHM FOR INEQUALITY CONSTRAINED OPTIMIZATIONS

A revised conjugate gradient projection method for nonlinear inequality constrained optimization problems is proposed in the paper, since the search direction is the combination of the conjugate projection gradient and the quasi-Newton direction. It has two merits. The one is that the amount of computation is lower because the gradient matrix only needs to be computed one time at each iteration. The other is that the algorithm is of global convergence and locally superlinear convergence without strict complementary condition under some mild assumptions. In addition the search direction is explicit.     

Limited memory quasi-newton method for large-scale linearly equality-constrained minimization

1. IntroductionConsider the following linearly constrained nonlinear programming problemwhere x e R", A E Rmxn and f E C2. We are interested in the case when n and m arelarge and when the Hessian matrix of f is difficult to compute or is dense. It is ajssumed thatA is a matrix of full row rank and that the level set S(xo) = {x: f(x) 5 f(xo), Ax ~ b} isnonempty and compact.In the past few years j there were two kinds of methods for solving the large-scaleproblem (1.1). FOr the one kind, pr…     

两类下降的非线性共轭梯度法的全局收敛性

本文在文献[1]中提出了一类新共轭梯度法的基础上,给出求解无约束优化问题的两类新的非线性下降共轭梯度法,此两类方法在无任何线搜索下,能够保证在每次迭代中产生下降方向.对一般非凸函数,我们在Wolfe线搜索条件下证明了两类新方法的全局收敛性.     

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.     

一类非线性方程组的Newton-PSS迭代法

正定反Hermite分裂(PSS)方法是求解大型稀疏非Hermite正定线性代数方程组的一类无条件收敛的迭代算法.将其作为不精确Newton方法的内迭代求解器,我们构造了一类用于求解大型稀疏且具有非Hermite正定Jacobi矩阵的非线性方程组的不精确Newton-PSS方法,并对方法的局部收敛性和半局部收敛性进行了详细的分析.数值结果验证了该方法的可行性与有效性.