quasi-newton methods

A Self-Correcting Variable-Metric Algorithm Framework for Nonsmooth Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Baoyu Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    An algorithm framework is proposed for minimizing nonsmooth functions. The framework is variable-metric in that, in each iteration, a step is computed using a symmetric positive definite matrix whose value is updated as in a quasi-Newton scheme. However, unlike previously proposed variable-metric algorithms for minimizing nonsmooth functions, the framework exploits self-correcting properties made possible through … Read more

    Block BFGS Methods

  • Wenbo Gao
  • Donald Goldfarb
    • Categories Unconstrained Optimization Tags , , ,

    We introduce a quasi-Newton method with block updates called Block BFGS. We show that this method, performed with inexact Armijo-Wolfe line searches, converges globally and superlinearly under the same convexity assumptions as BFGS. We also show that Block BFGS is globally convergent to a stationary point when applied to non-convex functions with bounded Hessian, and … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Donald Goldfarb
  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle ($\SFO$). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case … Read more

    Improved Damped Quasi-Newton Methods for Unconstrained Optimization

  • Mehiddin Al-Baali
  • Lucio Grandinetti
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Recently, Al-Baali (2014) has extended the damped-technique in the modified BFGS method of Powell (1978) for Lagrange constrained optimization functions to the Broyden family of quasi-Newton methods for unconstrained optimization. Appropriate choices for the damped-parameter, which maintain the global and superlinear con- vergence property of these methods on convex functions and correct the Hessian approximations … Read more

    Generalized Uniformly Optimal Methods for Nonlinear Programming

  • Saeed Ghadimi
  • Guanghui Lan
  • Hongchao Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

    In this paper, we present a generic framework to extend existing uniformly optimal convex programming algorithms to solve more general nonlinear, possibly nonconvex, optimization problems. The basic idea is to incorporate a local search step (gradient descent or Quasi-Newton iteration) into these uniformly optimal convex programming methods, and then enforce a monotone decreasing property of … Read more

    On the equivalence of the method of conjugate gradients and quasi-Newton methods on quadratic problems

  • Anders Forsgren
  • Tove Odland
    • Categories Quadratic Programming, Unconstrained Optimization Tags , ,

    In this paper we state necessary and sufficient conditions for equivalence of the method of conjugate gradients and quasi-Newton methods on a quadratic problem. We show that the set of quasi-Newton schemes that generate parallel search directions to those of the method of conjugate gradients is strictly larger than the one-parameter Broyden family. In addition, … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that only stochastic information of the gradients of the objective function is available via a stochastic first-order oracle (SFO). Firstly, we propose a general framework of stochastic quasi-Newton methods for solving nonconvex stochastic optimization. The proposed framework extends the classic … Read more

    A Quasi-Newton Algorithm for Nonconvex, Nonsmooth Optimization with Global Convergence Guarantees

  • Frank E. Curtis
  • Xiaocun Que
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    A line search algorithm for minimizing nonconvex and/or nonsmooth objective functions is presented. The algorithm is a hybrid between a standard Broyden–Fletcher–Goldfarb–Shanno (BFGS) and an adaptive gradient sampling (GS) method. The BFGS strategy is employed because it typically yields fast convergence to the vicinity of a stationary point, and together with the adaptive GS strategy … Read more

    A Stochastic Quasi-Newton Method for Large-Scale Optimization

  • Richard H. Byrd
  • Samantha Hansen
  • Jorge Nocedal
  • Yoram Singer
    • Categories Data-Mining, Stochastic Programming, Unconstrained Optimization Tags , , ,

    Abstract The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust … Read more

    Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

  • Katya Scheinberg
  • Xiaocheng Tang
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Recently several methods were proposed for sparse optimization which make careful use of second-order information [11, 30, 17, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here … Read more