On exact linesearch quasi-Newton methods for minimizing a quadratic function

DOI10.1007/S10589-017-9940-7zbMATH Open1411.90248arXiv1503.01892OpenAlexW3098015857MaRDI QIDQ683343FDOQ683343

Authors: Anders Forsgren, Tove Odland 

Publication date: 6 February 2018

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: This paper concerns exact linesearch quasi-Newton methods for minimizing a quadratic function whose Hessian is positive definite. We show that by interpreting the method of conjugate gradients as a particular exact linesearch quasi-Newton method, necessary and sufficient conditions can be given for an exact linesearch quasi-Newton method to generate a search direction which is parallel to that of the method of conjugate gradients. We also analyze update matrices and give a complete description of the rank-one update matrices that give search direction parallel to those of the method of conjugate gradients. In particular, we characterize the family of such symmetric rank-one update matrices that preserve positive definiteness of the quasi-Newton matrix. This is in contrast to the classical symmetric-rank-one update where there is no freedom in choosing the matrix, and positive definiteness cannot be preserved. The analysis is extended to search directions that are parallel to those of the preconditioned method of conjugate gradients in a straightforward manner.

Full work available at URL: https://arxiv.org/abs/1503.01892

Recommendations

• Exact linesearch limited-memory quasi-Newton methods for minimizing a quadratic function
• Minimization of extended quadratic functions with inexact line searches
• A quadratic approximation method for minimizing a class of quasidifferentiable functions
• Quasi-Newton approaches to interior point methods for quadratic problems
• scientific article; zbMATH DE number 2166157
• scientific article; zbMATH DE number 3865005
• Quasi-Newton methods for solving nonlinear programming problems
• On the construction of minimization methods of quasi-Newton type
• An algorithm for global minimization of linearly constrained quadratic functions
• Convergence of quasi-Newton method with new inexact line search

zbMATH Keywords

quasi-Newton methodexact line search methodmethod of conjugate gradientsunconstrained quadratic program

Mathematics Subject Classification ID

Quadratic programming (90C20) Methods of quasi-Newton type (90C53)

Cites Work

• Variable Metric Method for Minimization
• A Rapidly Convergent Descent Method for Minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Function minimization by conjugate gradients
• Methods of conjugate gradients for solving linear systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Limited Memory Conjugate Gradient Method
• A Relationship between the BFGS and Conjugate Gradient Algorithms and Its Implications for New Algorithms
• Unified approach to quadratically convergent algorithms for function minimization
• BFGS with Update Skipping and Varying Memory
• On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems

Cited In (8)

• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Exact linesearch limited-memory quasi-Newton methods for minimizing a quadratic function
• Inexact Newton Method for Minimization of Convex Piecewise Quadratic Functions
• On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems
• Quasi-Newton minimization for the \(p(x)\)-Laplacian problem
• An LP empirical quadrature procedure for parametrized functions
• On the Derivation of Quasi-Newton Formulas for Optimization in Function Spaces
• The linear algebra of block quasi-Newton algorithms

This page was built for publication: On exact linesearch quasi-Newton methods for minimizing a quadratic function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683343)