Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

By means of a gradient strategy, the Moreau-Yosida regularization, limited memory BFGS update, and proximal method, we propose a trust-region method for nonsmooth convex minimization. The search direction is the combination of the gradient direction and the trust-region direction. The global convergence of this method is established under suitable conditions. Numerical results show that this method is competitive to other two methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Auslender, A.: Numerical methods for nondifferentiable convex optimization. Math. Program. Stud. 30, 102–126 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bellavia, S., Macconi, M., Morini, B.: An affine scaling trust-region approach to bound-constrained nonlinear systems. Appl. Numer. Math. 44, 257–280 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bihain, A.: Optimization of upper semidifferentiable functions. J. Optim. Theory Appl. 44, 545–568 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Birge, J.R., Qi, L., Wei, Z.: A general approach to convergence properties of some methods for nonsmooth convex optimization. Appl. Math. Optim. 38, 141–158 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. Birge, J.R., Qi, L., Wei, Z.: Convergence analysis of some methods for minimizing a nonsmooth convex function. J. Optim. Theory Appl. 97, 357–383 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: A family of variable metric proximal methods. Math. Program. 68, 15–47 (1995)

    MATH  Google Scholar 

  7. Byrd, R.H., Nocedal, J., Schnabel, R.B.: Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63, 129–156 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Byrd, R.H., Schnabel, R.B., Shultz, G.A.: A trust region algorithm for nonlinearly constrained optimization. SIAM J. Numer. Anal. 24, 1152–1170 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  9. Buchley, A., LeNir, A.: QN-like variable storage conjugate gradients. Math. Program. 27, 577–593 (1983)

    Google Scholar 

  10. Calamai, P.H., Moré, J.J.: Projected gradient methods for linear constrained problems. Math. Program. 39, 93–116 (1987)

    Article  MATH  Google Scholar 

  11. Charalambous, J., Conn, A.R.: An efficient method to solve the minimax problem directly. SIAM J. Numer. Anal. 15, 162–187 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  12. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  13. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. SIAM, Philadelphia (2000)

    Book  MATH  Google Scholar 

  14. Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62, 261–273 (1993)

    Article  MATH  Google Scholar 

  15. de Sampaio, R.J.B., Yuan, J.Y., Sun, W.Y.: Trust region algorithm for nonsmooth optimization. Appl. Math. Comput. 85, 109–116 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  16. Demyanov, V.F., Malozemov, V.N.: Introduction to Minimax. Wiley, New York (1974)

    Google Scholar 

  17. Dennis, J.E. Jr., Li, S.B., Tapia, R.A.: A unified approach to global convergence of trust region methods for nonsmooth optimization. Math. Program. 68, 319–346 (1995)

    MathSciNet  MATH  Google Scholar 

  18. Fan, J.Y.: A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations. J. Comput. Math. 21, 625–636 (2003)

    MathSciNet  MATH  Google Scholar 

  19. Fletcher, R.: An algorithm for solving linearly constrained optimization problems. Math. Program. 2, 133–165 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  20. Fletcher, R.: A model algorithm for composite nondifferentiable optimization problems. Math. Program. Stud. 17, 67–76 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fukushima, M.: A descent algorithm for nonsmooth convex optimization. Math. Program. 30, 163–175 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  22. Fukushima, M., Qi, L.: A globally and superlinearly convergent algorithm for nonsmooth convex minimization. SIAM J. Optim. 6, 1106–1120 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  23. Gabriel, S.A., Pang, J.S.: A trust-region method for constrained nonsmooth equations. In: Hanger, W.W., Hearn, D.W., Pardalos, P.M. (eds.) Large Scale Optimization—State of the Art, pp. 155–181. Kluwer Academic, Dordrecht (1994)

    Chapter  Google Scholar 

  24. Gilbert, J.C., Lemaréchal, C.: Some numerical experiments with variable storage quasi-Newton algorithms. Math. Program. 45, 407–436 (1989)

    Article  MATH  Google Scholar 

  25. Goldfeld, S., Quandt, R., Trotter, H.: Maximization by quadratic hill climbing. Econometrica 34, 541–551 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  26. Gupta, N.: A higher than first order algorithm for nonsmooth constrained optimization. Ph.D. thesis, Department of Philosophy, Washington State University, Pullman, WA (1985)

  27. Hiriart-Urruty, J.B., Lemmaréchal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1983)

    Google Scholar 

  28. Jiang, H., Qi, L., Chen, X., Sun, D.: Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization and Applications, pp. 197–212. Plenum, New York (1996)

    Google Scholar 

  29. Kanzow, C.: An active-set type Newton method for constrained nonlinear equations. In: Ferris, M.C., Mangasarian, O.L., Pang, J.S. (eds.) Complementarity: Applications, Algorithms, and Extensions, pp. 179–200. Kluwer, Dordrecht (2001)

    Google Scholar 

  30. Kiwiel, K.C.: An ellipsoid trust region bundle method for nonsmooth convex minimization. SIAM J. Control Optim. 27, 737–757 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kiwiel, K.C.: Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Math. Program. 69, 89–109 (1995)

    MathSciNet  MATH  Google Scholar 

  32. Levenberg, K.: A method for the solution of certain nonlinear problem in least squares. Q. Appl. Math. 2, 164–166 (1944)

    MathSciNet  MATH  Google Scholar 

  33. Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  34. Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83, 373–391 (1998)

    MATH  Google Scholar 

  35. Martinet, B.: Régularisation d’inéquations variationelles par approximations succcessives. Rev. Fr. Inform. Rech. Oper. 4, 154–159 (1970)

    MathSciNet  MATH  Google Scholar 

  36. Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization. World Scientific, London (1992)

    MATH  Google Scholar 

  37. Ni, Q., Yuan, Y.: A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization. Math. Comput. 66, 1509–1520 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  38. Nocedal, J., Yuan, Y.: Combining trust region and line search techniques. In: Yuan, Y. (ed.) Advances in Nonlinear Programming, pp. 153–175. Kluwer, Dordrecht (1998)

    Chapter  Google Scholar 

  39. Pang, J.S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  40. Powell, M.J.D.: Convergence properties of a class of minimization algorithms. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming, vol. 2. Academic Press, New York (1975)

    Google Scholar 

  41. Powell, M.J.D.: A new algorithm for unconstrained optimization. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming, vol. 2, pp. 1–27. Academic Press, New York (1975)

    Google Scholar 

  42. Powell, M.J.D.: A fast algorithm for nonlinearly constrained optimization calculations. Numer. Anal. 155–157 (1978)

  43. Powell, M.J.D., Yuan, Y.: A trust region algorithm for equality constrained optimization. Math. Program. 49, 189–213 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  44. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–245 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  45. Qi, L.: Regular Pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems. Math. Oper. Res. 24, 440–471 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  46. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  47. Qi, L., Sun, J.: A trust region algorithm for minimization of locally Lipschitzian functions. Math. Program. 66, 25–43 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  48. Qi, L., Tong, X., Li, D.: Active-set projected trust-region algorithm for box-constrained nonsmooth equations. J. Optim. Theory Appl. 120, 601–625 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  49. Qi, H., Qi, L., Sun, D.: Solving KKT system via the trust region and the conjugate gradient method. SIAM J. Optim. 14, 439–463 (2004)

    Article  MathSciNet  Google Scholar 

  50. Rockafellar, R.T.: Monotone operators and proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  51. Rosen, J.B.: The gradient projection method for nonlinear programming, part I. Linear constraints. J. Soc. Ind. Appl. Math. 8, 181–217 (1960)

    Article  MATH  Google Scholar 

  52. Rosen, J.B.: The gradient projection method for nonlinear programming, part II. Nonlinear constraints. J. Soc. Ind. Appl. Math. 4, 514–532 (1961)

    Google Scholar 

  53. Ryrd, R.H., Lu, P.H., Nocedal, J., Zhu, C.Y.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput. 16, 1190–1208 (1995)

    Article  MathSciNet  Google Scholar 

  54. Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis numerical results. SIAM J. Optim. 2, 121–152 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  55. Short, N.Z.: Minimization Methods for Nondifferentiable Functions. Springer, Berlin (1985)

    Book  Google Scholar 

  56. Ulbrich, M.: Nonmonotone trust-region method for bounded constrained semismooth equations with applications to nonlinear mixed complementarity problems. SIAM J. Optim. 11, 889–917 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  57. Vardi, A.: A trust region algorithm for equality constrained minimization: convergence properties and implementation. SIAM J. Numer. Anal. 22, 575–591 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  58. Wei, Z., Qi, L.: Convergence analysis of a proximal Newton method. Numer. Funct. Anal. Optim. 17, 463–472 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  59. Wei, Z., Qi, L., Birge, J.R.: A new methods for nonsmooth convex optimization. Arch. Inequal. Appl. 2, 157–179 (1998)

    MathSciNet  MATH  Google Scholar 

  60. Womersley, J.: Numerical methods for structured problems in nonsmooth optimization. Ph.D. thesis. Mathematics Department, University of Dundee, Dundee, Scotland (1981)

  61. Xiao, Y., Li, D.: An active set limited memory BFGS algorithm for large-scale bound constrained optimization. Math. Methods Oper. Res. 67, 443–454 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  62. Yuan, Y.: On a subproblem of trust region algorithms for constrained optimization. Math. Program. 47, 53–63 (1990)

    Article  MATH  Google Scholar 

  63. Yuan, Y.: Trust region algorithm for nonlinear equations. Information 1, 7–21 (1998)

    MathSciNet  MATH  Google Scholar 

  64. Yuan, G., Lu, X.: An active set limited memory BFGS algorithm for bound constrained optimization. Appl. Math. Model. 35, 3561–3573 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  65. Yuan, Y., Sun, W.: Theory and Methods of Optimization. Science Press of China, Beijing (1999)

    Google Scholar 

  66. Yuan, G., Lu, X., Wei, Z.: BFGS trust-region method for symmetric nonlinear equations. J. Comput. Appl. Math. 230, 44–58 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  67. Yuan, G., Wei, Z., Wu, Y.: Modified limited memory BFGS method with nonmonotone line search for unconstrained optimization. J. Korean Math. Soc. 47, 767–788 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  68. Yuan, G., Wei, Z., Lu, S.: Limited memory BFGS method with backtracking for symmetric nonlinear equations. Math. Comput. Model. 54, 367–377 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  69. Zhang, L.: A new trust region algorithm for nonsmooth convex minimization. Appl. Math. Comput. 193, 135–142 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  70. Zhang, J., Wang, Y.: A new trust region method for nonlinear equations. Math. Methods Oper. Res. 58, 283–298 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  71. Zhang, J., Zhu, D.: Projected quasi-Newton algorithm with trust-region for constrained optimization. J. Optim. Theory Appl. 67, 369–393 (1990)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank two anonymous referees and the editor for catching several typos of the paper, and their useful suggestions and comments which improved the paper greatly. This work is supported by Program for Excellent Talents in Guangxi Higher Education Institutions, China NSF grands 11161003 and 71001015, Guangxi Education research project grands 201012MS013, and Guangxi SF grands 2012GXNSFAA053002.

Author information

Authors and Affiliations

  1. Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, 530004, P.R. China

    Gonglin Yuan, Zengxin Wei & Zhongxing Wang

Authors
  1. Gonglin Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zengxin Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhongxing Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gonglin Yuan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yuan, G., Wei, Z. & Wang, Z. Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization. Comput Optim Appl 54, 45–64 (2013). https://doi.org/10.1007/s10589-012-9485-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9485-8

Keywords

Search

Navigation