Local convergence of the steepest descent method in Hilbert spaces

The aim of this paper is to establish the local convergence of the steepest descent method for C¹-functionals defined on an infinite-dimensional Hilbert space H, under a Palais–Smale-type condition. The functionals f under consideration are also assumed to have a locally Lipschitz continuous gradient operator f. Our approach is based on the solutions of the ordinary differential equation .     

A limited memory steepest descent method

The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai–Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage of the availability of a few additional ‘long’ vectors of storage to achieve a significant improvement in performance, both for quadratic and non-quadratic objective functions. It makes use of certain Ritz values related to the Lanczos process (Lanczos in J Res Nat Bur Stand 45:255–282, 1950). Some underlying theory is provided, and numerical evidence is set out showing that the new method provides a competitive and more simple alternative to the state of the art l-BFGS limited memory method.     

A steepest descent method for vector optimization

In this work we propose a Cauchy-like method for solving smooth unconstrained vector optimization problems. When the partial order under consideration is the one induced by the nonnegative orthant, we regain the steepest descent method for multicriteria optimization recently proposed by Fliege and Svaiter. We prove that every accumulation point of the generated sequence satisfies a certain first-order necessary condition for optimality, which extends to the vector case the well known “gradient equal zero” condition for real-valued minimization. Finally, under some reasonable additional hypotheses, we prove (global) convergence to a weak unconstrained minimizer.As a by-product, we show that the problem of finding a weak constrained minimizer can be viewed as a particular case of the so-called Abstract Equilibrium problem.     

A novel hybrid immune algorithm and its convergence based on the steepest descent algorithm

This paper proposes a novel hybrid immune algorithm (HIA) that can overcome the typical drawback of the artificial immune algorithm (AIA), which runs slowly and experiences slow convergence. The HIA combines the adaptive AIA based on the steepest descent algorithm. The HIA fully displays global search ability and the global convergence of the immune algorithm. At the same time, it inserts a quasi-descent operator to strengthen its local search ability. A good convergence of the HIA with the quasi-descent idea is shown as well. Numerical experiment results show that the HIA successfully improves running speed and convergence performance.     

A short note on the global convergence of the unmodified PRP method

To guarantee global convergence of the standard (unmodified) PRP nonlinear conjugate gradient method for unconstrained optimization, the exact line search or some Armijo type line searches which force the PRP method to generate descent directions have been adopted. In this short note, we propose a non-descent PRP method in another way. We prove that the unmodified PRP method converges globally even for nonconvex minimization by the use of an approximate descent inexact line search.     

Strong convergence of a hybrid steepest descent method for the split common fixed point problem

We study the convergence properties of an iterative method for a variational inequality defined on a solution set of the split common fixed point problem. The method involves Landweber-type operators related to the problem as well as their extrapolations in an almost cyclic way. The evaluation of these extrapolations does not require prior knowledge of the matrix norm. We prove the strong convergence under the assumption that the operators employed in the method are approximately shrinking.     

A generalized steepest descent method for continuously subdifferentiable functions

A class of methods for unconstrained minimization of quasidifferentiable, especially subdifferentiable functions is described, which includes well-known algorithms as special cases. Moreover, it is shown that an algorithm previously published fails to converge to an e-inf-stationary point in general. Some preliminary numerical results are reported on.     

A characteristic condition for convergence of steepest descent approximation to accretive operator equations

In the present paper a sufficient and necessary condition for convergence of steepest descent approximation to accretive operator equations is established, and for the sufficiency part a specific error estimation is also given.     

Convergence of the steepest descent method for accretive operators

Let be a uniformly smooth Banach space and let be a bounded demicontinuous mapping, which is also -strongly accretive on . Let and let be an arbitrary initial value in . Then the approximating scheme

converges strongly to the unique solution of the equation , provided that the sequence fulfills suitable conditions.

     

Exact estima tes for the rate of convergence of the s-step method of steepest descent in eigenvalue problems

We obtain exact (unimprovable) estimates for the rate of convergence of the s-step method of steepest descent for finding the least (greatest) eigenvalue of a linear bounded self-adjoint operator in a Hilbert space.     

Convergence of the steepest descent method for minimizing quasiconvex functions

To minimize a continuously differentiable quasiconvex functionf: ⁿ , Armijo's steepest descent method generates a sequencex ^k+1 =x ^k –t _k f(x ^k ), wheret _k >0. We establish strong convergence properties of this classic method: either , s.t. ; or arg minf = , x ^k andf(x ^k ) inff. We also discuss extensions to other line searches.The research of the first author was supported by the Polish Academy of Sciences. The second author acknowledges the support of the Department of Industrial Engineering, Hong Kong University of Science and Technology.We wish to thank two anonymous referees for their valuable comments. In particular, one referee has suggested the use of quasiconvexity instead of convexity off.     

A modified steepest descent method with applications to maximizing likelihood functions

In maximizing a non-linear function G(), it is well known that the steepest descent method has a slow convergence rate. Here we propose a systematic procedure to obtain a 1–1 transformation on the variables , so that in the space of the transformed variables, the steepest descent method produces the solution faster. The final solution in the original space is obtained by taking the inverse transformation. We apply the procedure in maximizing the likelihood functions of some generalized distributions which are widely used in modeling count data. It was shown that for these distributions, the steepest descent method via transformations produced the solutions very fast. It is also observed that the proposed procedure can be used to expedite the convergence rate of the first derivative based algorithms, such as Polak-Ribiere, Fletcher and Reeves conjugate gradient methods as well.     

A convergence analysis of the method of codifferential descent

This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.     

A note on the convergence of the MAOR method

The MAOR method as a generalization of the well-known MSOR method was introduced by Hadjidimos et al. (Appl. Numer. Math. 10 (1992) 115–127) and investigated in Y. Song (J. Comput. Appl. Math. 79 (1997) 299–317) where some convergence results for the case when matrix of the system is strictly diagonally dominant are obtained. In this paper we shall improve these results.     

Long-time asymptotic for the Hirota equation via nonlinear steepest descent method

We present the Riemann–Hilbert problem formalism for the initial value problem for the Hirota equation on the line. We show that the solution of this initial value problem can be obtained from that of associated Riemann–Hilbert problem, which allows us to use nonlinear steepest descent method/Deift–Zhou method to analyze the long-time asymptotic for the Hirota equation.     

A feasible dual affine scaling steepest descent method for the linear semidefinite programming problem

The linear semidefinite programming problem is considered. The dual affine scaling method in which all current iterations belong to the feasible set is proposed for its solution. Moreover, the boundaries of the feasible set may be reached. This method is a generalization of a version of the affine scaling method that was earlier developed for linear programs to the case of semidefinite programming.     

A remedy for the failure of the numerical steepest descent method on a class of oscillatory integrals

In this paper we demonstrate that the numerical method of steepest descent fails when applied in a straight forward fashion to the most commonly occurring highly oscillatory integrals in scattering theory. Through a polar change of variables, however, the integral can be reformulated so that it can be solved efficiently using a combination of oscillatory integration techniques and classical quadrature. The approach is described in detail and demonstrated numerically with some oscillatory integral examples. The numerical examples demonstrate that our approach avoids the failure in some special cases, such as in an acoustic scattering model oscillatory integral with observation point located in the illuminated region. This paves the way for using the framework of numerical steepest descent methods on a wider class of problems, like the 3D high frequency scattering from convex obstacles, up to now only handled in a satisfactory way by methods due to Ganesh and Hawkins (J Comp Phys 230:104–125, 2011).     

半监督度量学习内蕴最速下降算法的收敛性分析

主要研究对称正定矩阵群上的内蕴最速下降算法的收敛性问题.首先针对一个可转化为对称正定矩阵群上无约束优化问题的半监督度量学习模型,提出对称正定矩阵群上一种自适应变步长的内蕴最速下降算法.然后利用李群上的光滑函数在任意一点处带积分余项的泰勒展开式,证明所提算法在对称正定矩阵群上是线性收敛的.最后通过在分类问题中的数值实验说明算法的有效性.