Steplength selection in gradient projection methods for box-constrained quadratic programs

被引:20
作者
Crisci, Serena [1 ,3 ]
Ruggiero, Valeria [1 ,3 ]
Zanni, Luca [2 ,3 ]
机构
[1] Univ Ferrara, Dept Math & Comp Sci, Via Saragat 1, I-44122 Ferrara, Italy
[2] Univ Modena & Reggio Emilia, Dept Phys Informat & Math, Via Campi 213-B, I-41125 Modena, Italy
[3] INdAM Res Grp GNCS, Milan, Italy
关键词
Box-constrained optimization; Gradient projection methods; Steplength rules; Hessian spectral properties; BARZILAI-BORWEIN METHOD; CONVERGENCE;
D O I
10.1016/j.amc.2019.03.039
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The role of the steplength selection strategies in gradient methods has been widely investigated in the last decades. Starting from the work of Barzilai and Borwein (1988), many efficient steplength rules have been designed, that contributed to make the gradient approaches an effective tool for the large-scale optimization problems arising in important real-world applications. Most of these steplength rules have been thought in unconstrained optimization, with the aim of exploiting some second-order information for achieving a fast annihilation of the gradient of the objective function. However, these rules are successfully used also within gradient projection methods for constrained optimization, though, to our knowledge, a detailed analysis of the effects of the constraints on the steplength selections is still not available. In this work we investigate how the presence of the box constraints affects the spectral properties of the Barzilai-Borwein rules in quadratic programming problems. The proposed analysis suggests the introduction of new steplength selection strategies specifically designed for taking account of the active constraints at each iteration. The results of a set of numerical experiments show the effectiveness of the new rules with respect to other state of the art steplength selections and their potential usefulness also in case of box-constrained non-quadratic optimization problems. (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页码:312 / 327
页数:16
相关论文
共 38 条
[1]   On the Application of the Spectral Projected Gradient Method in Image Segmentation [J].
Antonelli, Laura ;
De Simone, Valentina ;
di Serafino, Daniela .
JOURNAL OF MATHEMATICAL IMAGING AND VISION, 2016, 54 (01) :106-116
[2]   2-POINT STEP SIZE GRADIENT METHODS [J].
BARZILAI, J ;
BORWEIN, JM .
IMA JOURNAL OF NUMERICAL ANALYSIS, 1988, 8 (01) :141-148
[3]   Nonmonotone spectral projected gradient methods on convex sets [J].
Birgin, EG ;
Martínez, JM ;
Raydan, M .
SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (04) :1196-1211
[4]   Inexact spectral projected gradient methods on convex sets [J].
Birgin, EG ;
Martínez, JM ;
Raydan, M .
IMA JOURNAL OF NUMERICAL ANALYSIS, 2003, 23 (04) :539-559
[5]   Spectral Projected Gradient Methods: Review and Perspectives [J].
Birgin, Ernesto G. ;
Martinez, Jose Mario ;
Raydan, Marcos .
JOURNAL OF STATISTICAL SOFTWARE, 2014, 60 (03) :1-21
[6]   New convergence results for the scaled gradient projection method [J].
Bonettini, S. ;
Prato, M. .
INVERSE PROBLEMS, 2015, 31 (09)
[7]   A scaled gradient projection method for constrained image deblurring [J].
Bonettini, S. ;
Zanella, R. ;
Zanni, L. .
INVERSE PROBLEMS, 2009, 25 (01)
[8]   Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming [J].
Dai, YH ;
Fletcher, R .
NUMERISCHE MATHEMATIK, 2005, 100 (01) :21-47
[9]   On the nonmonotone line search [J].
Dai, YH .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2002, 112 (02) :315-330
[10]   R-linear convergence of the Barzilai and Borwein gradient method [J].
Dai, YH ;
Liao, LZ .
IMA JOURNAL OF NUMERICAL ANALYSIS, 2002, 22 (01) :1-10