conjugate gradient method

Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm

  • Albert S. Berahas
  • Raghu Bollapragada
  • Wanping Dong
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees … Read more

    A Semismooth Conjugate Gradients Method — Theoretical Analysis

  • Franz Bethke
  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , ,

    In large scale applications, deterministic and stochastic variants of Cauchy’s steepest descent method are widely used for the minimization of objectives that are only piecewise smooth. In this paper we analyse a  deterministic descent method based on the generalization of rescaled conjugate gradients proposed by Philip Wolfe in 1975 for objectives that are convex. Without … Read more

    Regularized Step Directions in Conjugate Gradient Minimization for Machine Learning

  • Cassidy K. Buhler
  • Hande Benson
  • David F. Shanno
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    Conjugate gradient minimization methods (CGM) and their accelerated variants are widely used in machine learning applications. We focus on the use of cubic regularization to improve the CGM direction independent of the steplength (learning rate) computation. Using Shanno’s reformulation of CGM as a memoryless BFGS method, we derive new formulas for the regularized step direction, … Read more

    A new stopping criterion for Krylov solvers applied in Interior Point Methods

  • Jacek Gondzio
  • Filippo Zanetti
    • Categories Convex Optimization Tags , , , ,

    A surprising result is presented in this paper with possible far reaching consequences for any optimization technique which relies on Krylov subspace methods employed to solve the underlying linear equation systems. In this paper the advantages of the new technique are illustrated in the context of Interior Point Methods (IPMs). When an iterative method is … Read more

    Complexity of a Projected Newton-CG Method for Optimization with Bounds

  • Yue Xie
  • Stephen Wright
    • Categories Bound-constrained Optimization Tags , , , ,

    This paper describes a method for solving smooth nonconvex minimization problems subject to bound constraints with good worst-case complexity and practical performance. The method contains elements of two existing methods: the classical gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex optimization. Using a new definition of approximate … Read more

    Riemannian conjugate gradient methods with inverse retraction

  • Hiroyuki Sato
  • Xiaojing Zhu
    • Categories Nonlinear Optimization Tags , , , , ,

    We propose a new class of Riemannian conjugate gradient (CG) methods, in which inverse retraction is used instead of vector transport for search direction construction. In existing methods, differentiated retraction is often used for vector transport to move the previous search direction to the current tangent space. However, a different perspective is adopted here, motivated … Read more

    New subspace minimization conjugate gradient methods based on regularization model for unconstrained optimization

  • Hongwei Liu
  • Zhao Ting
  • Zexian Liu
    • Categories Applications - OR and Management Sciences Tags , , , ,

    In this paper, two new subspace minimization conjugate gradient methods based on p-regularization models are proposed, where a special scaled norm in p-regularization model is analyzed. Diffierent choices for special scaled norm lead to different solutions to the p-regularized subproblem. Based on the analyses of the solutions in a two-dimensional subspace, we derive new directions … Read more

    Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Clément W. Royer
  • Stephen Wright
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from … Read more

    On limited-memory quasi-Newton methods for minimizing a quadratic function

  • David Ek
  • Anders Forsgren
    • Categories Quadratic Programming, Unconstrained Optimization Tags , , , ,

    The main focus in this paper is exact linesearch methods for minimizing a quadratic function whose Hessian is positive definite. We give two classes of limited-memory quasi-Newton Hessian approximations that generate search directions parallel to those of the method of preconditioned conjugate gradients, and hence give finite termination on quadratic optimization problems. The Hessian approximations … Read more

    A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint

  • Maziar Salahi
  • Akram Taati
    • Categories Global Optimization, Quadratic Programming Tags , ,

    In this paper, we consider the nonconvex quadratically constrained quadratic programming (QCQP) with one quadratic constraint. By employing the conjugate gradient method, an efficient algorithm is proposed to solve QCQP that exploits the sparsity of the involved matrices and solves the problem via solving a sequence of positive definite system of linear equations after identifying … Read more