The symmetric rank-one quasi-Newton method is a space-dilation subgradient algorithm
type: Item
instance of: scholarly article
title: The symmetric rank-one quasi-Newton method is a space-dilation subgradient algorithm
zbMATH Open document ID: 0604.90113
DOI: 10.1016/0167-6377(86)90010-6
author: Michael J. Todd
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://hdl.handle.net/1813/8571
review text: It is well-known that a particular choice of the parameters in Shor's subgradient algorithm with space dilation in the direction of the gradient yields the ellipsoid method. We show that another choice of these parameters leads to the quasi-Newton method that uses the symmetric rank-one update and direct prediction. One curious feature is that the sequence of approximate inverse Hessian matrices lags by one in the former description; this necessitates a different starting matrix or an unusual update at the first step. While the similarity between update formulae in space-dilation and quasi-Newton methods has been observed by several researchers, our result seems to be the first showing a precise equivalence. We note that apparently this equivalence cannot be extended to other quasi-Newton methods (for smooth optimization) or space-dilation methods (for non-smooth optimization). Nevertheless, we feel that our result gives insight into the relationship between these two classes of algorithms, and hope that it will suggest new efficient methods for non- smooth problems.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 49M37
zbMATH DE Number: 3976793
zbMATH Keywords: unconstrained optimization
zbMATH Keywords: particular choice of the parameters
zbMATH Keywords: Shor's subgradient algorithm
zbMATH Keywords: space dilation
zbMATH Keywords: quasi-Newton method
MaRDI profile type: Publication
OpenAlex ID: W2031846494
cites work: On the Local and Superlinear Convergence of Quasi-Newton Methods
cites work: Q3702408
cites work: Quasi-newton algorithms generate identical points
cites work: Q5187067
description: scientific article; zbMATH DE number 3976793