Volume 3,Issue 8
A New Projected Gradient Method for Unconstrained Problems
In this paper, we propose a new gradient projection method for problems without constraints. Based on the steepest descent method, there is a projection matrix P constructed from the descending direction and the iterative direction [1–4]. We gave a general proof of the convergence for the new projected gradient method in this paper. In numerical experiments using the CUTEr test problem library, the new projected gradient method performs better than the classic fastest descent method.
[1] Barzilai J, Borwein M, 1988, Two Point Step Gradient Methods. IMA,J.Numer.Anal, 8: 141–148.
[2] Fridlander A, Martinez MJ, Molina B, et al., 1999, Gradient Method with Retards and Generalizations. SIAM J.Numer.Anal., 36: 275–289.
[3] Raydan M, Svaiter BF, 2002, Relaxed Steepest Descent and Cauchy-Barzilai-Borwein Method. Compute Optimal Appl., 5: 167.
[4] Dai YH, Yuan Y, 2003, Alternate Minimization Gradient Method. IMA J.Anal. 23: 377–393.
[5] Dai YH, 2006, The cyclic Barzilai-Borwein Method for Unconstrained Optimization. IMA Journal of Numerical Analysis, 26: 504–627.
[6] Raydan M, 1993, On the Barzilai and Borwein Choice of Steplength for the Gradient Method. IMA J.Numer.Anal., 13: 321–326.
[7] Raydan M, 1997, The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem, SIAM J. Optim., 7(1): 26–33.
[8] Birgin EG, Chambouleyron I, Martinez JM, 1999, Estimation of the Optical Constants and the Thickness of Thin Films Using Unconstrained Optimization, J. Comput.Phys, 151: 862–880.
[9] Birgin EG, Evtushenko YG, 1998, Automatic Differentiation and Spectral Projected Gradient Methods for Optimal Control Problems. Optim Methods Shoftw, 10, 125–146.
[10] Birgin EG, Martinez JM, Mirada, 2000, Nonmonotone Spectral Projected Gradient Methods for Convex Sets. SIAM Journal on Optimization, 10(4): 1196–1211.
[11] Dai YH, Liao LZ, n.d., R-Linear Convergence of the Barzilai and Borwein Gradient Method. Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences Research.
[12] Fletcher R, 1999, Low Storage Methods for Unconstrained Optimization. Lectures in Applied Mathematics (AMS), 26: 165–179.
[13] Friedlander A, Martinez JM, Molina B, et al., 1999, Gradient Method with Retards and Generalization. J. Numer. Anal., 36, 275–289.
[14] Raydan M, n.d., On the Barzilai and Borwein Choice of Step Length for the Gradient Method. J Anal., 13199: 321–326.
[15] Yuan Y, 1991, A Modified BFGS Algorithm for Unconstrained Optimization. IMA J.Numer Anal, 11: 325–332.
[16] Yuan Y, 1993, Numerical Methods for Nonlinear Programming, Shanghai Scientific and Technical Publishers.
[17] Wang W, 2002, Conjugate Hierarchy Algorithm and Its Convergence for Linear Constrained Optimization Problems. Journal of Natural Science of Northeast Normal University, 34(2): 12–15.
[18] Ye L, 2005, A Memory Gradient Rosen Projection Algorithm Combining Conjugate Gradient Parameters for Linear or Nonlinear Constrained Optimization Problems. Journal of Sichuan University, 42(2): 652–660.
[19] Liang Y, Jian J, 2003, A Conjugate Gradient Method for Linear Constrained Optimization. Operations Research and Management, 12(2): 31–35.
[20] Calamai PH, More JJ, 1987, Projected Gradient Methods for Linearly Constrained Problems. Mathematical Programming, 39: 93–116.
[21] Zhang XS, 1985, On the Convergence of Rosen’s Gradient Projection Method: Three-Dimensional, Case, Acta Mathematicae Applicate Sinica, 8: 125–128.
[22] Du DZ, Remarks on the Convergence of Rosen’s Gradient Projection Method. MSRI Technique Report, 01718–86.
[23] He G, 1987, Proof of Convergence of the Rosen’s Gradient Projection Method. Journal of Chengdu University of Science and Technology, 1(1987): 55–68.
[24] Polak E, 1969, On the Convergence of Optimization Algorithms. Revue Francaised matique Infor et de Recherche Operrationelle, 3(16): 17–34.
[25] Wang C, 1982, A Feasible Direction Method for Nonlinear Programming. Acta Mathematica Sinica, 25: 15–19.
[26] Bazaraa MS, Sherry CM, 1979, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, Inc.
[27] Grippo L, Ampariello FL, 1986, Lucidi A Nonmonotone Line Search Technique For Newton’s Method. Journal on Numerical SIAM Analysis, 23: 707–716.
[28] Shi ZJ, 1996, A Class of Globally Convergent Conjugate Projection Gradient Method and Its Superlinear Convergence. Computational Mathematics, 11(4): 411–421.
[29] Zhu Z, 2004, A New Conjugate Projection Gradient Algorithm and Its Superlinear Convergence, Chinese Journal of Applied Mathematics, 27(1): 149–161.
[30] Liu WB, Dai YH, 1999, Minimization Algorithms Based on Supervisor and Searcher Co-Operation.I:--Faster and Robust Gradient Algorithms for Minimization Problems with Stronger Noises. Academy of Mathematic and Systems Sciences, Chinese Academy of Sciences.
[31] Hestenes MR, Stiefel EL, 1952, Methods of Conjugate Gradients for Solving Linear Systems. JRes Nat Bur Standards Sect. 5(49): 409–436.
[32] Fletcher R, Reeves C, 1964, Function Minimization by Conjugate Gradients. Comput, 7: 149–154.
[33] Toint PL, 1981, Towards an Efficient Sparsity Exploiting Newton Method for Minimization. Sparse Matrices and Their Uses, Academic Press London, England, 57–88.
[34] Steihaug T, 1983, The Conjugate Gradient Method and Trust Region in Large Scale Optimization. SIAM Journal on Numerical Analysis, 20(1983): 626–637.
[35] Dimitri P, Bertsekas DP, n.d., Projected Newton Methods For Optimization Problems With Simple Constraints SIAM J.Control and Optimization, 20(2): 2198.
[36] Hestenes MR, Stiefel EL, 1952, Methods of Conjugate Gradients for Solving Linear. JRes Nat Standards Sect, 49(5): 409–436.
[37] Fletcher R, Reeves C, 1964, Function Minimization by Conjugate Gradients. Compute, 7: 149–154.
[38] Bertsekas DP, 1976, On the Goldstein-Levitin-Polyak Gradient Projection Method. IEEE Transactions on Automatic Control, 21: 174–184.
[39] Dai YH, Zhang HC, 2001, Adaptive Two-Point Stepsize Gradient Algorithm. Numerical Algorithms, 27: 377–385.
[40] Zhang HC, Hager WW, 2004, A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization. SIAM Journal on Optimization, 14: 63–85.