Global and local R-linear convergence of a spectral projected gradient method for convex optimization with singular solution

Volume 9, Issue 6, pp 4509--4519 http://dx.doi.org/10.22436/jnsa.009.06.89

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2163 Downloads
• 2362 Views

Authors

Zhensheng Yu - College of Science, University of Shanghai for Science and Technology, Shanghai, 200093, P. R. China. Xinyue Gan - College of Science, University of Shanghai for Science and Technology, Shanghai, 200093, P. R. China.

Abstract

In this paper, we propose a spectral projected gradient method for the convex optimization problem with singular solution. By solving the equivalent equation of the gradient function, this method combines the perturbed spectral gradient direction with the projection direction to generate the next iteration point. Under some mild conditions, we establish the global convergence and the local R-linear convergence rate under the local error bound condition. Preliminary numerical tests are given to show that the proposed method works well.

Share and Cite

Keywords

• Unconstrained optimization
• spectral projected gradient
• local error bound
• R-linear convergence.

MSC

•  65K05
•  90C30

References

• [1] N. Andrei, An Unconstrained Optimization Test Functions Collection, Adv Model Optim., 10 (2008), 147-161.


• [2] J. Barzilai, J. M. Borwein, Two Point Step size Gradient Methods, IMA J. Numer Anal., 8 (1988), 141-148.


• [3] E. G. Birgin, J. M. Martínez, M. Raydan, Nonmonotone Spectral Projected Gradient Methods for Convex Sets, SIAM J. Optim., 10 (2000), 1196-1211.


• [4] E. G. Birgin, J. M. Martínez, M. Raydan , Encyclopedia of Optimization: Spectral Projected Gradient Methods, Springer, 2008 (2008), 3652-3659.


• [5] E. G. Birgin, J. M. Martnez, M. Raydan, Spectral Projected Gradient Methods: Review and Perspectives, J. Stati. Software, 6 (2014), 1-21.


• [6] I. Bongartz, A. R. Conn, N. I. M. Gould, P. L. Toint , CUTE: Constrained and Unconstrained Testing Environments, ACM TOMS, 21 (1995), 123-160.


• [7] Y.-H. Dai, R. Fletcher, Projected Barzilai-Borwein Methods for Large-Scale Box-Constrained Quadratic Programming, Numer. Math., 100 (2005), 21-47.


• [8] Y.-H. Dai, L.-Z. Liao, R-linear Convergence of the Barzilai and Borwein Gradient Method, IMA J. Numer. Anal., 22 (2002), 1-10.


• [9] J. E. Dennis, J. J. More , Quasi-Newton Methods, Motivation and Theory, SIAM Rev., 19 (1977), 46-89.


• [10] J. E. Dennis, R. B. Schnabel, Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, NJ (1983)


• [11] M. A. Diniz-Ehrhardt, M. A. Gomes-Ruggiero, J. M. Martínez, S. A. Santos , Augmented Lagrangian Algorithm Based On the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems , J. Optim. Theory Appl., 123 (2004), 497-517.


• [12] L. Grippo, F. Lampariello, S. Lucidi , A Nonmonotone Line Search Technique for Newton's Methods, SIAM J. Numer. Anal., 23 (1986), 707-716.


• [13] C. Kanzow, N. Yamashita, M. Fukushima, Levenberg-Marquardt Methods for Constrained Nonlinear Equations with Strong Local Convergence Properties, J. Comput. Appl. Math., 172 (2004), 375-397.


• [14] W. La Cruz, J. M. Martínez, M. Raydan , Spectral Residual Method Without Gradient Information for Solving Large-scale Nonlinear Systems of Equations , Math Comput., 75 (2006), 1449-1466.


• [15] W. La Cruz, M. Raydan, Nonmonotone Spectral Methods for Large-scale Nonlinear Systems, Optim Method Soft., 18 (2003), 583-599.


• [16] D.-H. Li, M. Fukushima, L. Qi, N. Yamashita, Regularized Newton Method for Convex Minimization Problems with Singular Solutions, Comput. Optim. Appl., 26 (2004), 131-147.


• [17] Y.-J. Li, D.-H. Li , Truncated Regularized Newton Method for Convex Minimizations, Comput. Optim. Appl., 43 (2009), 119-131.


• [18] W. B. Liu, Y. H. Dai, Minimization Algorithms Based on Supervisor and Searcher Cooperation, J. Optim. Theory. Appl., 111 (2001), 359-379.


• [19] B. Molina, M. Raydan , Preconditioned Barzilai-Borwein Method for the Numerical Solution of A Partial Differential Equation, Numer. Algorithm, 13 (1996), 45-60.


• [20] M. Raydan, On the Barzilai and Borwein Choice of Step Length for the Gradient Method , IMA J. Numer. Anal., 13 (1993), 321-326.


• [21] M. Raydan, The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem, SIAM J. Optim., 7 (1997), 26-33.


• [22] M. V. Solodov, B. F. Svaiter, Descent Methods with Linesearch in the Presence of Perturbations, J. Comput. Appl. Math., 80 (1997), 265-275.


• [23] M. V. Solodov, B. F. Svaiter, A Globally Convergent Inexact Newton Method for Systems of Monotone Equations: in Reformulation: Piecewise Smooth, Semi-smooth and Smoothing Methods, Kluwer Acad. Publ., (1999), 355-369.


• [24] C. Wang, Y. Wang, C. Xu, A Projection Method for A System of Nonlinear Monotone Equations with Convex Constraints, Math. Meth. Oper. Res., 66 (2007), 33-46.


• [25] N. Yamashita, M. Fukushima, On the Rate of Convergence of the Levenberg-Marquardt Method: in Topics in numerical analysis, Comput. Suppl., 15, Springer, Vienna, (2001), 237-249.


• [26] J. L. Zhang, L. Y. Wu, X. S. Zhang, A Trust Region Method for Optimization Problem with Singular Solutions, Appl. Math. Optim., 56 (2007), 379-394.


• [27] L. Zhang, W. J. Zhou, Spectral Gradient Projection Method for Solving Nonlinear Monotone Equations, J. Comput. Appl. Math., 196 (2006), 478-484.


• [28] G. Zhou, K. C. Toh, Superlinear Convergence of a Newton-type Algorithm for Monotone Equations, J. Optim. Theory Appl., 125 (2005), 205-221.