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. 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 efficient 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 effective anyway. In this paper, we deeply analyze how, in quadratic and nonquadratic 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 step length rules on a set of test problems arising also from machine learning and image processing applications.