具简单界约束变分不等式的拟牛顿算法的收敛性分析

１．引言 牛顿型方法是解变分不等式的一类重要数值迭代算法．其局部收敛性质的研究也取得了很好的成果（见［５］等）．近几年来,此类算法的全局收敛性研究也得到了许多进展．如阻尼牛顿法的局部超线性乃至二阶收敛性质的研究（见［４,６,９; １１, １２, １４; １６］等）．然而,对于计算上更为实用的拟牛顿法的研究还不多见．文［１８］基于祁力群等在［１４］中给出的逐次逼近牛顿型法,建立了一种解非线性互补问题的拟牛顿法,并得到了类Ｂｒｏｙｄｅｎ算法的全局收敛性．但是,该方法有以下两个缺陷：１．线搜索可能不能实现…     

带有广义Wolfe线搜索的变尺度算法的收敛性

本文提出一类广义Ｗｏｌｆｅ线搜索模型，并且把它与著名的ＢＦＧＳ方法相结合，对于所得到的算法证明了：对于凸函数算法具有全局收敛性和超线性收敛速度，这推广了参考文献［１］中的结果．     

BFGS算法对非凸函数优化问题的收敛性

ＢＦＧＳ算法是无约束最优化中最著名的数值算法之一,对非凸函数ＢＦＧＳ算法是否具有整体收敛性,这是一个ｏｐｅｎ问题,本文考虑Ｗｏｌｆｏ线搜索下目标函数非凸的ＢＦＧＳ算法,我们给出一个使该算法收敛的充分条件。     

基于非单调线搜索非拟牛顿法的全局收敛性

本文就非拟牛顿法在无约束最优化问题上，对采用非单调线搜索的情况下是否具有全局收敛性进行了研究，在目标函数满足一致凸的条件下，证明了非拟牛顿族是全局收敛的．     

关于单调的变分不等式问题的收敛性方法

１引言变分不等式的性质及解法的研究是优化领域的重要课题．所谓变分不等式问题就是：寻找一个点,使得其中Ｘ是Ｒｎ中的非空闲凸集,Ｆ是Ｒｎ中的映射,表示Ｒｎ中的内积．求解问题（１．１）有多种思路［１,４,５］其中之一就是将（１．１）转化为它的某种等价问题,再进行求解．在山中ＭａｓａｏＦｕｋｕｓｈｉｍａ给出了（１．１）的如下的等价问题Ｇ是对称正定矩阵．山提出了求解（１．２）的带精确搜索和Ａｒｍｉｊｏ搜索的两种收敛性算法．本文建立了“ｄ－ｆｕｎｃｔｉｏｎ”的概念,利用“Ｄ－ｆｕｎｃｔｉｎ”给出了（１．１）…     

一般无约束优化问题的广义拟牛顿法

对一般目标函数极小化问题的拟牛顿法及其全局收敛性的研究,已经成为拟牛顿法理论中最基本的开问题之一．本文对这个问题做了进一步的研究,对无约束优化问题提出一类新的广义拟牛顿算法,并结合Goldstein线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性．     

一族超线性收敛的投影拟牛顿算法

本文将梯度投影与拟牛顿法相结合，给出了求解一般线性约束非线性规划问题含两组参数的算法族．在一定的条件下证明了算法族的全局收敛性与它的子族的超线性收敛速度，并给出了投影Ｄ．Ｆ．Ｐ方法、投影ＢＦＧＳ方法等一些特例．     

无约束最优化线搜索一般模型及BFGS方法的整体收敛性

本文给出了无约束最优化的算法中线性搜索的可接受的步长选择律的一种一般形式，它概括了大多数已有的步长律为其特例，并且研究了它基本性质，最后证明了此线性搜索一般模拟相结合的无约束优化的ＢＦＧＳ算法的整体收敛性。     

非凸无约束优化问题的广义拟牛顿法的全局收敛性

本文对无约束优化问题提出一类新的广义拟牛顿法,并采用一类非精确线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性.     

一类超线性收敛的广义拟Newton算法

１引言考虑无约束最优化问题其中目标函数ｆ（ｘ）二阶连续可微,记ｆｋ＝ｆ（ｘ）,当充分小时,有如下近似关系：它们对二次函数皆严格成立．考虑选代其中Ｂ（Ｇ的近似）已知,为某种线搜索确定的步长．对Ｂ修正产生Ｂ,即Ｕ为待定ｎ阶矩阵．若要求Ｂ＋满足关系即Ｂ满足拟Ｎｅｗｔｏｎ方程,由它可导出许多著名的拟Ｎｅｗｔｏｎ算法［１－［４］）．若要求Ｂ满足关系则可导出伪Ｎｅｗｔｏｎ－δ族校正公式,它不再是Ｈｕａｎｇ族成员［６］．从信息资源的利用看,（１．６）仅利用了与信息,（１．７）仅利用了与信息．一般而言,较多的信…     

带一类非精确搜索的Broyden族的全局收敛性

带一类非精确搜索的Ｂｒｏｙｄｅｎ族的全局收敛性刘光辉，韩继业（中国科学院应用数学研究所）ＧＬＯＢＡＬＣＯＮＶＥＲＧＥＮＣＥＯＦＴＨＥＢＲＯＹＤＥＮ＇ＳＦＡＭＩＬＹＷＩＴＨＡＣＬＡＳＳＯＦＩＮＥＸＡＣＴＬＩＮＥＳＥＡＲＣＨＥＳ￥ＬｉｕＧｕａｎｇ－ｈｕｉ...     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

Inexact proximal stochastic gradient method for convex composite optimization

We study an inexact proximal stochastic gradient (IPSG) method for convex composite optimization, whose objective function is a summation of an average of a large number of smooth convex functions and a convex, but possibly nonsmooth, function. Variance reduction techniques are incorporated in the method to reduce the stochastic gradient variance. The main feature of this IPSG algorithm is to allow solving the proximal subproblems inexactly while still keeping the global convergence with desirable complexity bounds. Different subproblem stopping criteria are proposed. Global convergence and the component gradient complexity bounds are derived for the both cases when the objective function is strongly convex or just generally convex. Preliminary numerical experiment shows the overall efficiency of the IPSG algorithm.     

一类改进BFGS算法及其收敛性分析

本文针对无约束最优化问题,基于目标函数的局部二次模型近似,提出一类改进的BFGS算法,称为 MBFGS算法。其修正 B_k的公式中含有一个参数θ∈[0,l],当 θ= 1时即得经典的BFGS公式;当θ∈[0、l）时,所得公式已不属于拟Newton类。在目标函数一致凸假设下,证明了所给算法的全局收敛性及局部超线性收敛性。     

A Study of the Dennis-Wolkowicz Method on Convex Functions

In this paper, we analyze the global convergence of the least-change secant method proposed by Dennis and Wolkowicz, when applied to convex objective functions. One of the most distinguished features of this method is that the Dennis-Wolkowicz update doesn't necessarily belong to the Broyden convex family and can be close to the DFP update, but it still has the self-correcting property. We prove that, for convex objective functions, this method with the commonly used Wolfe line search is globally convergent. We also provide some numerical results.     

Convergence analysis of a proximal newton method 1

Recently Fukushima and Qi proposed a proximal Newton method for minimizating a nonsmooth convex function. An alternative global convergence proof for that method is presented in this paper. Global convergence was established without any additional assumption on the objective function. We also show that the infimum of a convex function is always equal to the infimun of its Moreau—Yosida regularization     

Quadratic and Superlinear Convergence of the Huschens Method for Nonlinear Least Squares Problems

This paper is concerned with quadratic and superlinear convergence of structured quasi-Newton methods for solving nonlinear least squares problems. These methods make use of a special structure of the Hessian matrix of the objective function. Recently, Huschens proposed a new kind of structured quasi-Newton methods and dealt with the convex class of the structured Broyden family, and showed its quadratic and superlinear convergence properties for zero and nonzero residual problems, respectively. In this paper, we extend the results by Huschens to a wider class of the structured Broyden family. We prove local convergence properties of the method in a way different from the proof by Huschens.     

Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.