谱HS投影算法求解非线性单调方程组

借助谱梯度法和HS共轭梯度法的结构, 建立一种求解非线性单调方程组问题的谱HS投影算法. 该算法继承了谱梯度法和共轭梯度法储存量小和计算简单的特征, 且不需要任何导数信息, 因此它适应于求解大规模非光滑的非线性单调方程组问题. 在适当的条件下, 证明了该算法的收敛性, 并通过数值实验表明了该算法的有效性.     

解凸约束非线性单调方程组的无导数谱PRP投影算法

本文在著名PRP共轭梯度算法的基础上研究了一种无导数谱PRP投影算法,并证明了算法在求解带有凸约束条件的非线性单调方程组问题的全局收敛性.由于无导数和储存量小的特性,它更适应于求解大规模非光滑的非线性单调方程组问题.数值试验表明,新算法对给定的测试问题是有效的和稳定的.     

凸约束非光滑方程组一个新的谱梯度投影算法

基于寻找分离超平面的三种经典线搜索技术,本文提出了一种自适应线搜索技术.结合谱梯度投影法,提出了凸约束非光滑单调方程组的一个谱梯度投影算法.该算法不需要计算和存储任何矩阵,因而适合求解大规模非光滑的非线性单调方程组.在较弱的条件下,证明了方法的全局收敛性,并分析了算法的收敛率.数值试验结果表明算法是有效的和鲁棒的.     

A derivative-free three-term projection algorithm involving spectral quotient for solving nonlinear monotone equations

ABSTRACT

In this paper, we develop a three-term conjugate gradient method involving spectral quotient, which always satisfies the famous Dai-Liao conjugacy condition and quasi-Newton secant equation, independently of any line search. This new three-term conjugate gradient method can be regarded as a variant of the memoryless Broyden-Fletcher-Goldfarb-Shanno quasi-Newton method with regard to spectral quotient. By combining this method with the projection technique proposed by Solodov and Svaiter in 1998, we establish a derivative-free three-term projection algorithm for dealing with large-scale nonlinear monotone system of equations. We prove the global convergence of the algorithm and obtain the R-linear convergence rate under some mild conditions. Numerical results show that our projection algorithm is effective and robust, and is more competitive with the TTDFP algorithm proposed Liu and Li [A three-term derivative-free projection method for nonlinear monotone system of equations. Calcolo. 2016;53:427–450].     

凸约束伪单调方程组的无导数投影算法

基于HS共轭梯度法的结构,本文在弱假设条件下建立了一种求解凸约束伪单调方程组问题的迭代投影算法.该算法不需要利用方程组的任何梯度或Jacobian矩阵信息,因此它适合求解大规模问题.算法在每一次迭代中都能产生充分下降方向,且不依赖于任何线搜索条件.特别是,我们在不需要假设方程组满足Lipschitz条件下建立了算法的全局收敛性和R-线收敛速度.数值结果表明,该算法对于给定的大规模方程组问题是稳定和有效的.     

求解非线性单调方程组的一种无导数投影算法

推广了一种修正的CG_DESCENT共轭梯度方法,并建立了一种有效求解非线性单调方程组问题的无导数投影算法.在适当的线搜索条件下,证明了算法的全局收敛性.由于新算法不需要借助任何导数信息,故它适应于求解大规模非光滑的非线性单调方程组问题.大量的数值试验表明,新算法对给定的测试问题是有效的.     

A gradient projection method for the sparse signal reconstruction in compressive sensing

Many problems arising from machine learning, compressive sensing, linear inverse problem, and statistical inference involve finding sparse solutions to under-determined or ill-conditioned equations. In this paper, a gradient projection method is proposed to recover sparse signal in compressive sensing by solving the nonlinear convex constrained equations. The global convergence is established with the backtracking line search. Preliminary numerical experiments coping with the sparse signal reconstruction in compressive sensing are performed, which show that the proposed method is very effective and stable.     

A modified quasi‐Newton diagonal update algorithm for total variation denoising problems and nonlinear monotone equations with applications in compressive sensing

In this paper, we present a new algorithm to accelerate the Chambolle gradient projection method for total variation image restoration. The new proposed method considers an approximation of the Hessian based on the secant equation. Combined with the quasi‐Cauchy equations and diagonal updating, we can obtain a positive definite diagonal matrix. In the proposed minimization method model, we use the positive definite diagonal matrix instead of the constant time stepsize in Chambolle's method. The global convergence of the proposed scheme is proved. Some numerical results illustrate the efficiency of this method. Moreover, we also extend the quasi‐Newton diagonal updating method to solve nonlinear systems of monotone equations. Performance comparisons show that the proposed method is efficient. A practical application of the monotone equations is shown and tested on sparse signal reconstruction in compressed sensing. Copyright © 2015 John Wiley & Sons, Ltd.     

Spectral gradient projection method for solving nonlinear monotone equations

An algorithm for solving nonlinear monotone equations is proposed, which combines a modified spectral gradient method and projection method. This method is shown to be globally convergent to a solution of the system if the nonlinear equations to be solved is monotone and Lipschitz continuous. An attractive property of the proposed method is that it can be applied to solving nonsmooth equations. We also give some preliminary numerical results to show the efficiency of the proposed method.     

A modified spectral conjugate gradient projection algorithm for total variation image restoration

In this study, a modified spectral conjugate gradient projection method is presented to solve total variation image restoration, which is transferred into the nonlinear constrained optimization with the closed constrained set. The global convergence of the proposed scheme is analyzed. In the end, some numerical results illustrate the efficiency of this method.     

Three adaptive hybrid derivative-free projection methods for constrained monotone nonlinear equations and their applications

In this work, by considering the hyperplane projection and hybrid techniques, three scaled three-term conjugate gradient methods are extended to solve the system of constrained monotone nonlinear equations, and the developed methods have the advantages of low storage and only using function values. The new methods satisfy the sufficient descent condition independent of any line search criterion. It has been proved that three new methods converge globally under some mild conditions. The numerical experiments for constrained monotone nonlinear equations and image de-blurring problems illustrate that the proposed methods are numerically effective and efficient.     

A class of conjugate gradient methods for convex constrained monotone equations

The recent designed non-linear conjugate gradient method of Dai and Kou [SIAM J Optim. 2013;23:296–320] is very efficient currently in solving large-scale unconstrained minimization problems due to its simpler iterative form, lower storage requirement and its closeness to the scaled memoryless BFGS method. Just because of these attractive properties, this method was extended successfully to solve higher dimensional symmetric non-linear equations in recent years. Nevertheless, its numerical performance in solving convex constrained monotone equations has never been explored. In this paper, combining with the projection method of Solodov and Svaiter, we develop a family of non-linear conjugate gradient methods for convex constrained monotone equations. The proposed methods do not require the Jacobian information of equations, and even they do not store any matrix in each iteration. They are potential to solve non-smooth problems with higher dimensions. We prove the global convergence of the class of the proposed methods and establish its R-linear convergence rate under some reasonable conditions. Finally, we also do some numerical experiments to show that the proposed methods are efficient and promising.     

An Liu-Storey-Type Method for Solving Large-Scale Nonlinear Monotone Equations

An algorithm for solving nonlinear monotone equations is proposed, which combines a modified Liu-Storey conjugate gradient method with hyperplane projection method. Under mild conditions, the global convergence of the proposed method is established with a suitable line search method. The method can be applied to solve large-scale problems for its lower storage requirement. Numerical results indicate that our method is efficient.     

Preconditioned Spectral Gradient Method

The spectral gradient method is a nonmonotone gradient method for large-scale unconstrained minimization. We strengthen the algorithm by modifications which globalize the method and present strategies to apply preconditioning techniques. The modified algorithm replaces a condition of uniform positive definitness of the preconditioning matrices, with mild conditions on the search directions. The result is a robust algorithm which is effective on very large problems. Encouraging numerical experiments are presented for a variety of standard test problems, for solving nonlinear Poisson-type equations, an also for finding molecular conformations by distance geometry.     

The Gauss-Newton Methods via Conjugate Gradient Path without Line Search Technique for Solving Nonlinear Systems

In this article, we propose the Gauss-Newton methods via conjugate gradient path for solving nonlinear systems. By constructing and solving a linearized model of the nonlinear systems, we obtain the iterative direction by employing the conjugate gradient path. In successive iterations, the approximate Jacobian of the nonlinear systems is updated by a Broyden formula to construct the conjugate path. The global convergence and local superlinear convergence rate of the proposed algorithms are established under some reasonable conditions. Finally, the numerical results are reported to show the effectiveness of the proposed algorithms.     

A new derivative-free SCG-type projection method for nonlinear monotone equations with convex constraints

Based on a modified line search scheme, this paper presents a new derivative-free projection method for solving nonlinear monotone equations with convex constraints, which can be regarded as an extension of the scaled conjugate gradient method and the projection method. Under appropriate conditions, the global convergence and linear convergence rate of the proposed method is proven. Preliminary numerical results are also reported to show that this method is promising.     

一种修正的谱CD共轭梯度算法的全局收敛性

In this paper,we present a new nonlinear modified spectral CD conjugate gradient method for solving large scale unconstrained optimization problems.The direction generated by the method is a descent direction for the objective function,and this property depends neither on the line search rule,nor on the convexity of the objective function.Moreover,the modified method reduces to the standard CD method if line search is exact.Under some mild conditions,we prove that the modified method with line search is globally convergent even if the objective function is nonconvex.Preliminary numerical results show that the proposed method is very promising.     

Stokes方程的投影／方向分裂谱方法

我们提出和分析了一种求解Stokes方程的数值方法．新方法基于空间上的Legendre谱离散,时间上则采用投影／方向分裂格式．更确切地说,时间离散的出发点是旋度形式的压力校正投影法,在此基础上进一步应用方向分裂法,把速度和压力方程分裂为一系列一维的椭圆型子问题．然后生成的这些一维子问题用Legendre谱方法进行空间离散．另外,我们证明了全离散格式的稳定性．一些数值实验验证了收敛性和方法的有效性．     

A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used. In this paper, we propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

     

A Probe Method of Gradient Projection Type

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＷｅｃｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ：（Ｐ）　　ｍｉｎｘ∈Ｘｆ（ｘ）（１）ｗｈｅｒｅＸ＝｛ｘ｜ｘ∈Ｅｎ,ｇｊ（ｘ）≤０,ｊ＝１,２,…,ｍ;ｇｊ（ｘ）＝０,ｊ＝ｍ＋１,…,ｍ＋ｌ｝,ｌｅｔＩ＝｛１,２,…,ｍ｝,Ｌ＝｛ｍ＋１,…,ｍ＋ｌ｝．Ｆｏｒｔｈｅｐｒｏｂｌｅｍ（Ｐ）ｗｉｔｈＬ＝,ｍａｎｙｅｆｆｉｃｉｅｎｔｐｒｏｊｅｃｔｉｏｎｔｙｐｅａｌｇｏｒｉｔｈｍｓ［１－１１］ｈａｖｅｂｅｅｎｐｒｏｐｏｓｅｄ．Ｉｎ［１２］,…