A Rank-One Fitting Method with Descent Direction for Solving Symmetric Nonlinear Equations

In this paper, a rank-one updated method for solving symmetric nonlinear equations is proposed. This method possesses some features: 1) The updated matrix is positive definite whatever line search technique is used;2) The search direction is descent for the norm function;3) The global convergence of the given method is established under reasonable conditions. Numerical results show that the presented method is interesting.

Global Convergence of an Extended Descent Algorithm without Line Search for Unconstrained Optimization

In this paper, we extend a descent algorithm without line search for solving unconstrained optimization problems. Under mild conditions, its global convergence is established. Further, we generalize the search direction to more general form, and also obtain the global convergence of corresponding algorithm. The numerical results illustrate that the new algorithm is effective.

Global Convergence of Curve Search Methods for Unconstrained Optimization

In this paper we propose a new family of curve search methods for unconstrained optimization problems, which are based on searching a new iterate along a curve through the current iterate at each iteration, while line search methods are based on finding a new iterate on a line starting from the current iterate at each iteration. The global convergence and linear convergence rate of these curve search methods are investigated under some mild conditions. Numerical results show that some curve search methods are stable and effective in solving some large scale minimization problems.

A Descent Gradient Method and Its Global Convergence

Y Liu and C Storey(1992)proposed the famous LS conjugate gradient method which has good numerical results.However,the LS method has very weak convergence under the Wolfe-type line search.In this paper,we give a new descent gradient method based on the LS method.It can guarantee the sufficient descent property at each iteration and the global convergence under the strong Wolfe line search.Finally,we also present extensive preliminary numerical experiments to show the efficiency of the proposed method by comparing with the famous PRP^+method.

A New Descent Nonlinear Conjugate Gradient Method for Unconstrained Optimization

In this paper, a new nonlinear conjugate gradient method is proposed for large-scale unconstrained optimization. The sufficient descent property holds without any line searches. We use some steplength technique which ensures the Zoutendijk condition to be held, this method is proved to be globally convergent. Finally, we improve it, and do further analysis.

CONVERGENCE RATE OF GRADIENT DESCENT METHOD FOR MULTI-OBJECTIVE OPTIMIZATION

The convergence rate of the gradient descent method is considered for unconstrained multi-objective optimization problems (MOP). Under standard assumptions, we prove that the gradient descent method with constant stepsizes converges sublinearly when the objective functions are convex and the convergence rate can be strengthened to be linear if the objective functions are strongly convex. The results are also extended to the gradient descent method with the Armijo line search. Hence, we see that the gradient descent method for MOP enjoys the same convergence properties as those for scalar optimization.

非凸多分块优化的Bregman ADMM的收敛率研究

Wang等提出了求解带线性约束的多块可分非凸优化问题的带Bregman距离的交替方向乘子法(Bregman ADMM),并证明了其收敛性.该文将进一步研究求解带线性约束的多块可分非凸优化问题的Bregman ADMM的收敛率,以及算法产生的迭代点列有界的充分条件.在效益函数的Kurdyka-Lojasiewicz (KL)性质下,该文建立了值和迭代的收敛速率,证明了与目标函数相关的各种KL指数值可获得Bregman ADMM的三种不同收敛速度.更确切地说,该文证明了如下结果:如果效益函数的KL指数θ=0,那么由Bregman ADMM生成的序列经过有限次迭代后收敛;如果θ∈(0,1/2),那么Bregman ADMM是线性收敛的;如果θ∈(1/2,1),那么Bregman ADMM是次线性收敛的.

A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting:Convergence and Rate Analyses

This work explores a family of two-block nonconvex optimization problems subject to linear constraints.We first introduce a simple but universal Bregman-style improved alternating direction method of multipliers(ADMM)based on the iteration framework of ADMM and the Bregman distance.Then,we utilize the smooth performance of one of the components to develop a linearized version of it.Compared to the traditional ADMM,both proposed methods integrate a convex combination strategy into the multiplier update step.For each proposed method,we demonstrate the convergence of the entire iteration sequence to a unique critical point of the augmented Lagrangian function utilizing the powerful Kurdyka–Łojasiewicz property,and we also derive convergence rates for both the sequence of merit function values and the iteration sequence.Finally,some numerical results show that the proposed methods are effective and encouraging for the Lasso model.

基于非下降线搜索的改进PRP共轭梯度方法及在图像恢复中的应用

PRP方法是最有效的非线性共轭梯度优化方法之一,然而该方法不能保证产生目标函数的下降方向,这给一般函数的全局收敛带来了困难。为了保证PRP方法的全局收敛性,提出了一种改进的PRP共轭梯度方法。文章以非凸优化问题为目标,简要介绍了非下降线搜索技术以及一些适当的假设条件,探讨了改进PRP方法的全局收敛性。基于MATLAB软件工具,验证了新方法在处理无约束优化和图像恢复问题时的有效性和实用性。

A Bregman-style Partially Symmetric Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization

The alternating direction method of multipliers(ADMM)is one of the most successful and powerful methods for separable minimization optimization.Based on the idea of symmetric ADMM in two-block optimization,we add an updating formula for the Lagrange multiplier without restricting its position for multiblock one.Then,combining with the Bregman distance,in this work,a Bregman-style partially symmetric ADMM is presented for nonconvex multi-block optimization with linear constraints,and the Lagrange multiplier is updated twice with different relaxation factors in the iteration scheme.Under the suitable conditions,the global convergence,strong convergence and convergence rate of the presented method are analyzed and obtained.Finally,some preliminary numerical results are reported to support the correctness of the theoretical assertions,and these show that the presented method is numerically effective.

A Symmetric Linearized Alternating Direction Method of Multipliers for a Class of Stochastic Optimization Problems

Alternating direction method of multipliers(ADMM)receives much attention in the recent years due to various demands from machine learning and big data related optimization.In 2013,Ouyang et al.extend the ADMM to the stochastic setting for solving some stochastic optimization problems,inspired by the structural risk minimization principle.In this paper,we consider a stochastic variant of symmetric ADMM,named symmetric stochastic linearized ADMM(SSL-ADMM).In particular,using the framework of variational inequality,we analyze the convergence properties of SSL-ADMM.Moreover,we show that,with high probability,SSL-ADMM has O((ln N)·N^(-1/2))constraint violation bound and objective error bound for convex problems,and has O((ln N)^(2)·N^(-1))constraint violation bound and objective error bound for strongly convex problems,where N is the iteration number.Symmetric ADMM can improve the algorithmic performance compared to classical ADMM,numerical experiments for statistical machine learning show that such an improvement is also present in the stochastic setting.

A Coordinate Gradient Descent Method for Nonsmooth Nonseparable Minimization

This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function.We find a search direction by solving a subproblem obtained by a second-order approximation of the smooth function and adding a separable convex function.Under a local Lipschitzian error bound assumption,we show that the algorithm possesses global and local linear convergence properties.We also give some numerical tests(including image recovery examples) to illustrate the efficiency of the proposed method.

A modified three–term conjugate gradient method with sufficient descent property

A hybridization of the three–term conjugate gradient method proposed by Zhang et al. and the nonlinear conjugate gradient method proposed by Polak and Ribi`ere, and Polyak is suggested. Based on an eigenvalue analysis, it is shown that search directions of the proposed method satisfy the sufficient descent condition, independent of the line search and the objective function convexity. Global convergence of the method is established under an Armijo–type line search condition. Numerical experiments show practical efficiency of the proposed method.

A New Nonlinear Conjugate Gradient Method for Unconstrained Optimization Problems

In this paper,an efficient conjugate gradient method is given to solve the general unconstrained optimization problems,which can guarantee the sufficient descent property and the global convergence with the strong Wolfe line search conditions.Numerical results show that the new method is efficient and stationary by comparing with PRP＋ method,so it can be widely used in scientific computation.

Three New Hybrid Conjugate Gradient Methods for Optimization

In this paper, three new hybrid nonlinear conjugate gradient methods are presented, which produce suf?cient descent search direction at every iteration. This property is independent of any line search or the convexity of the objective function used. Under suitable conditions, we prove that the proposed methods converge globally for general nonconvex functions. The numerical results show that all these three new hybrid methods are efficient for the given test problems.

PRP-Type Direct Search Methods for Unconstrained Optimization

Three PRP-type direct search methods for unconstrained optimization are presented. The methods adopt three kinds of recently developed descent conjugate gradient methods and the idea of frame-based direct search method. Global convergence is shown for continuously differentiable functions. Data profile and performance profile are adopted to analyze the numerical experiments and the results show that the proposed methods are effective.

两个带重启方向的改进HS型共轭梯度法

共轭梯度法是求解大规模无约束优化的有效方法之一.该文首先对Hestenes-Stiefel(HS)共轭参数改进,再通过引入重启条件及重启方向,建立两个带重启方向的改进HS型共轭梯度法.第一个方法在弱Wolfe线搜索下产生下降方向,第二个方法独立于任何线搜索得到充分下降性.常规假设下,分析并获得两个新方法的全局收敛性.最后,数值比对试验结果及性能图显示新方法是有效的.

On the Sublinear Convergence Rate of Multi-block ADMM

The alternating direction method of multipliers(ADMM)is widely used in solving structured convex optimization problems.Despite its success in practice,the convergence of the standard ADMM for minimizing the sum of N(N≥3)convex functions,whose variables are linked by linear constraints,has remained unclear for a very long time.Recently,Chen et al.(Math Program,doi:10.1007/s10107-014-0826-5,2014)provided a counter-example showing that the ADMM for N≥3 may fail to converge without further conditions.Since the ADMM for N≥3 has been very successful when applied to many problems arising from real practice,it is worth further investigating under what kind of sufficient conditions it can be guaranteed to converge.In this paper,we present such sufficient conditions that can guarantee the sublinear convergence rate for the ADMM for N≥3.Specifically,we show that if one of the functions is convex(not necessarily strongly convex)and the other N-1 functions are strongly convex,and the penalty parameter lies in a certain region,the ADMM converges with rate O(1/t)in a certain ergodic sense and o(1/t)in a certain non-ergodic sense,where t denotes the number of iterations.As a by-product,we also provide a simple proof for the O(1/t)convergence rate of two-blockADMMin terms of both objective error and constraint violation,without assuming any condition on the penalty parameter and strong convexity on the functions.

A NEWε-GENERALIZED PROJECTION METHOD OF STRONGLY SUB-FEASIBLE DIRECTIONS FOR INEQUALITY CONSTRAINED OPTIMIZATION

In this paper, the nonlinear optimization problems with inequality constraints are discussed. Combining the ideas of the strongly sub-feasible directions method and the s-generalized projection technique, a new algorithm starting with an arbitrary initial iteration point for the discussed problems is presented. At each iteration, the search direction is generated by a new s-generalized projection explicit formula, and the step length is yielded by a new Armijo line search. Under some necessary assumptions, not only the algorithm possesses global and strong convergence, but also the iterative points always get into the feasible set after finite iterations. Finally, some preliminary numerical results are reported.

共轭下降法的一个改进及收敛性分析

研究了共轭下降法,做出了较为恰当的改进.步长规则采用Wolfe线搜索,在较弱的条件下证明了算法的全局收敛性,并给出了数值实验.结果表明,改进后的算法是有效的.