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

In 1988, Barzilai and Borwein published a pioneering paper which opened the way to inexpensively accelerate first-order methods. More in detail, in the framework of unconstrained optimization, Barzilai and Borwein developed two strategies to select the steplength 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 efficient steplength techniques have been suggested in the last decades in order to make gradient descent methods more and more appealing also for problems which handle large-scale data and require real-time solutions. Typically, these new steplength selection rules have been tuned in the quadratic unconstrained framework for sweeping the spectrum of the inverse of the Hessian matrix, and then applied also to non-quadratic constrained problems, without any substantial modification, by showing to be very effective anyway. In this paper we deeply analyse how, in quadratic and non-quadratic minimization problems, the presence of a feasible region, expressed by a single linear equality constraint together with lower and upper bounds, influences 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 information but also to exploit the nature of the feasible region. We show the benefits gained by the new steplength rules on a set of test problems arising also from machine learning and image processing applications.

Article

Download

View Spectral properties of Barzilai-Borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds