In 1988, Barzilai and Borwein published a pioneering paper which opened the way to inexpensively accelerate first-order. In more detail, in the framework of unconstrained optimization, Barzilai and Borwein developed two strategies to select the step length in gradient descent methods with the aim of encoding some second-order information of the problem without computing and/or employing the Hessian matrix of the objective function. Starting from these ideas, several effcient step length techniques have been suggested in the last decades in order to make gradient descent methods more and also more appealing for problems which handle large-scale data and require real- time solutions. Typically, these new step length selection rules have been tuned in the quadratic unconstrained framework for sweeping the spectrum of the Hessian matrix, and then applied also to nonquadratic constrained problems, without any substantial modification, by showing them to be very effiective anyway. In this paper, we deeply analyze how, in quadratic and nonquadratic mini- mization problems, the presence of a feasible region, expressed by a single linear equality constraint together with lower and upper bounds, inuences the spectral properties of the original Barzilai-Borwein (BB) rules, generalizing recent results provided for box-constrained quadratic problems. This analysis gives rise to modified BB approaches able not only to capture second-order informa- tion but also to exploit the nature of the feasible region. We show the benefits gained by the new step length rules on a set of test problems arising also from machine learning and image processing applications.

Spectral properties of barzilai-borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds / Crisci, S.; Porta, F.; Ruggiero, V.; Zanni, L.. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - 30:2(2020), pp. 1300-1326. [10.1137/19M1268641]

Spectral properties of barzilai-borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds

Crisci S.;Porta F.;Ruggiero V.;Zanni L.
2020

Abstract

In 1988, Barzilai and Borwein published a pioneering paper which opened the way to inexpensively accelerate first-order. In more detail, in the framework of unconstrained optimization, Barzilai and Borwein developed two strategies to select the step length in gradient descent methods with the aim of encoding some second-order information of the problem without computing and/or employing the Hessian matrix of the objective function. Starting from these ideas, several effcient step length techniques have been suggested in the last decades in order to make gradient descent methods more and also more appealing for problems which handle large-scale data and require real- time solutions. Typically, these new step length selection rules have been tuned in the quadratic unconstrained framework for sweeping the spectrum of the Hessian matrix, and then applied also to nonquadratic constrained problems, without any substantial modification, by showing them to be very effiective anyway. In this paper, we deeply analyze how, in quadratic and nonquadratic mini- mization problems, the presence of a feasible region, expressed by a single linear equality constraint together with lower and upper bounds, inuences the spectral properties of the original Barzilai-Borwein (BB) rules, generalizing recent results provided for box-constrained quadratic problems. This analysis gives rise to modified BB approaches able not only to capture second-order informa- tion but also to exploit the nature of the feasible region. We show the benefits gained by the new step length rules on a set of test problems arising also from machine learning and image processing applications.
30
2
1300
1326
Spectral properties of barzilai-borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds / Crisci, S.; Porta, F.; Ruggiero, V.; Zanni, L.. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - 30:2(2020), pp. 1300-1326. [10.1137/19M1268641]
Crisci, S.; Porta, F.; Ruggiero, V.; Zanni, L.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/1203708
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact