Skip to main content
SpringerLink
Log in

A hybrid ODE-based method for unconstrained optimization problems

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

Abstract

This paper presents a hybrid ODE-based method for unconstrained optimization problems, which combines the idea of IMPBOT with the subspace technique and a fixed step-length. The main characteristic of this method is that at each iteration, a lower dimensional system of linear equations is solved only once to obtain a trial step. Another is that when a trial step is not accepted, this proposed method uses minimization of a convex overestimation, thus avoiding performing a line search to compute a step-length. Under some reasonable assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computations, especially for solving small scale unconstrained optimization problems.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Yuan, Y.X., Sun, W.Y.: Optimization Theory and Methods. Science Press, Beijing (1997) (in Chinese)

    Google Scholar 

  2. Brown, A.A., Biggs, M.C.: Some effective methods for unconstrained optimization based on the solution of system of ordinary differentiable equations. J. Optim. Theory Appl. 62, 211–224 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  3. Han, L.X.: On the convergence properties of an ODE algorithm for unconstrained optimization. Math. Numer. Sin. 15, 449–455 (1993)

    MATH  Google Scholar 

  4. Higham, D.J.: Trust region algorithms and timestep selection. SIAM J. Numer. Anal. 37, 194–210 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Brown, A.A., Biggs, M.C.: ODE versus SQP methods. J. Optim. Theory Appl. 62, 371–386 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  6. Andrei, N.: Gradient flow algorithm for unconstrained optimization. ICI Technical Report (March 4, 2004). http://csmo.ici.ro/neculai/anman.htm

  7. Luo, X.L., Kelley, C.T., Liao, L.Z., Tam, H.W.: Combining trust-region techniques and Rosenbrock methods to compute stationary points. J. Optim. Theory Appl. 140, 265–286 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Ortega, J.M., Rheinboldt, W.C.: Interative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)

    Google Scholar 

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

    Chapter  Google Scholar 

  10. Gertz, E.M.: A quasi-Newton trust region method. Math. Program., Ser. A 100, 447–470 (2004)

    MathSciNet  MATH  Google Scholar 

  11. Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–188 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  12. Raydan, M.: The Barzilai and Borwein method for the large-scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  13. Sun, J., Zhang, J.P.: Global convergence of convergence of conjugate gradient methods without line search. Ann. Oper. Res. 103, 161–173 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  14. Mo, J.T., Zhang, K.C., Wei, Z.X.: A nonmonotone trust region method for unconstrained optimization. Appl. Math. Comput. 171, 371–384 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ou, Y.G., Zhou, Q., Lin, H.C.: An ODE-based trust region method for unconstrained optimization problems. J. Comput. Appl. Math. 232, 318–326 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Wang, Z.H., Yuan, Y.X.: A subspace implementation of quasi-Newton trust region methods for unconstrained optimization. Numer. Math. 104, 241–269 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Shi, Z.J., Xu, Z.W.: The convergence of subspace trust region methods. J. Comput. Appl. Math. 231, 365–377 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Yuan, Y.X.: Subspace methods for large scale nonlinear equations and nonlinear least squares. Optim. Eng. 10, 207–218 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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 

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

    Article  MathSciNet  MATH  Google Scholar 

  22. More, J., Garbow, B., Hillstrom, K.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  23. Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10(1), 147–161 (2008)

    MathSciNet  MATH  Google Scholar 

  24. Dolan, E.D., More, J.: Benchmarking optimization software with performance profiles. Math. Program., Ser. A 91, 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are very grateful to the editor and the anonymous referees for their valuable comments and suggestions that greatly improved this paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, Hainan University, Haikou, 570228, China

    Yi-gui Ou & Guan-shu Wang

Authors
  1. Yi-gui Ou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guan-shu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yi-gui Ou.

Additional information

Partially supported by NNSF of China (No. 11161016) and NSF of Hainan Province (No. 111001).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ou, Yg., Wang, Gs. A hybrid ODE-based method for unconstrained optimization problems. Comput Optim Appl 53, 249–270 (2012). https://doi.org/10.1007/s10589-012-9455-1

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9455-1

Keywords

Search

Navigation