Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Non-monotone inexact restoration method for nonlinear programming

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

Abstract

This paper deals with a new variant of the inexact restoration method of Fischer and Friedlander (Comput Optim Appl 46:333–346, 2010) for nonlinear programming. We propose an algorithm that replaces the monotone line search performed in the tangent phase by a non-monotone one, using the sharp Lagrangian as merit function. Convergence to feasible points satisfying the convex approximate gradient projection condition is proved under mild assumptions. Numerical results on representative test problems show that the proposed approach outperforms the monotone version when a suitable non-monotone parameter is chosen and is also competitive against other globalization strategies for inexact restoration.

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

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

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

References

  1. Andreani, R., Castro, S.L.C., Chela, J.L., Friedlander, A., Santos, S.A.: An inexact-restoration method for nonlinear bilevel programming problems. Comput. Optim. Appl. 43(3), 307–328 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization 60(5), 627–641 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Andreani, R., Martínez, J.M., Ramos, A., Silva, P.J.S.: A cone-continuity constraint qualification and algorithmic consequences. SIAM J. Optim. 26(1), 96–110 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  4. Andreani, R., Martínez, J.M., Ramos, A., Silva, P.J.S.: Strict constraint qualifications and sequential optimality conditions for constrained optimization. Math. Oper. Res. 43(3), 693–717 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  5. Arouxét, B., Echebest, N.E., Pilotta, E.A.: Inexact restoration method for nonlinear optimization without derivatives. J. Comput. Appl. Math. 290(15), 26–43 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  6. Birgin, E.G., Bueno, L.F., Martínez, J.M.: Assessing the reability of general-purpose inexact restoration methods. J. Comput. Appl. Math. 282, 1–16 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  7. Birgin, E.G., Krejić, N., Martínez, J.M.: On the employment of inexact restoration for the minimization of functions whose evaluation is subject to errors. Math. Comput 87, 1307–1326 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  8. Birgin, E.G., Krejić, N., Martínez, J.M.: Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact. Math. Comput., to appear (2019) (https://doi.org/10.1090/mcom/3445)

  9. Birgin, E.G., Martínez, J.M.: Local convergence of an inexact-restoration method and numerical experiments. J. Optim. Theory Appl. 127, 229–247 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Birgin, E.G., Martínez, J.M.: Practical augmented Lagrangian methods for constrained optimization. Fundamental of algorithms. SIAM, Philadelphia (2014)

    Book  MATH  Google Scholar 

  11. Bueno, L.F., Friedlander, A., Martínez, J.M., Sobral, F.N.C.: Inexact restoration method for derivative-free optimization with smooth constraints. SIAM J. Optim. 23(2), 1189–1213 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bueno, L.F., Haeser, G., Martínez, J.M.: A flexible inexact restoration method for constrained optimization. J. Optim. Theory. Appl. 165, 188–208 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bueno, L.F., Haeser, G., Martínez, J.M.: An inexact restoration approach to optimization problems with multiobjective constraints under weighted-sum scalarization. Optim Lett. 10(6), 1315–1325 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory. Appl. 112(2), 315–330 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fischer, A., Friedlander, A.: A new line search inexact restoration approach for nonlinear programming. Comput. Optim. Appl. 46, 333–346 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Francisco, J.B., Gonçalves, D.S., Viloche-Bazán, F.S., Paredes, L.L.T.: A non-monotone inexact restoration approach for minimization with orthogonality constraints (2018). http://www.optimization-online.org/DB_FILE/2018/10/6860.pdf

  18. Francisco, J.B., Martínez, J.M., Martínez, L., Pisnitchenko, F.I.: Inexact restoration methods for minimization problems that arise in electronic structure calculations. Comput. Optim. Appl. 50, 555–590 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  19. Francisco, J.B., Viloche-Bazán, F.S.: Nonmonotone algorithm for minimization on closed sets with application to minimization on stiefel manifolds. J. Comput. Appl. Math. 236(10), 2717–2727 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Francisco, J.B., Viloche-Bazán, F.S., Weber-Mendonça, M.: Non-monotone algorithm for minimization on arbitrary domains with applications to large-scale orthogonal procrustes problem. Appl. Numer. Math. 112, 51–64 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  21. Friedlander, A., Gomes, F.A.M.: Solution of a truss topology bilevel programming problem by means of an inexact restoration method. Comput. Appl. Math. 30(1), 109–125 (2011)

    MathSciNet  MATH  Google Scholar 

  22. Fu, J., Sun, W.: Nonmonotone adaptive trust-region method for unconstrained optimization problems. Appl. Math. Comput. 163, 489–504 (2005)

    MathSciNet  MATH  Google Scholar 

  23. Golub, G.A., van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, London (1996)

    MATH  Google Scholar 

  24. Gonzaga, C.C., Karas, E.W., Vanti, M.: A globally convergent filter method for nonlinear programming. SIAM J. Optim. 14(3), 646–669 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  25. Jiang, B., Dai, Y.H.: A framework of constraint preserving update schemes for optimization on Stiefel manifold. Math. Program. 153(2), 535–575 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  26. Karas, E.W., Pilotta, E., Ribeiro, A.: Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems. Comput. Optim. Appl. 44, 427–441 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kaya, C.Y.: Inexact restoration for Runge–Kutta discretization of optimal control problems. SIAM J. Numer. Anal. 48(4), 1492–1517 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kohn, W.: Nobel lecture: electronic structure of matter-wave functions and density functionals. Rev. Mod. Phys. 71(5), 1253–1266 (1999)

    Article  Google Scholar 

  29. Krejić, N., Martínez, J.M.: Inexact restoration approach for minimization with inexact evaluation of the objective function. Math. Comput. 85, 1775–1791 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  30. Lasdon, L.S., Fox, R.L., Ratner, M.W.: Nonlinear optimization using the generalized reduced gradient method. R.A.I.R.O. Oper. Res. 8(3), 73–103 (1974)

    MathSciNet  MATH  Google Scholar 

  31. Martínez, J.M.: Inexact restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming. J. Optim. Theory. Appl. 111, 39–58 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  32. Martínez, J.M., Pilotta, E.A.: Inexact restoration algorithms for constrained optimization. J. Optim. Theory. Appl. 104, 135–163 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  33. Miele, A., Huang, H.Y., Heideman, J.C.: Sequential gradient-restoration algorithm for the minimization of constrained functions — ordinary and conjugate gradient versions. J. Optim. Theory. Appl. 4(4), 213–243 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  34. Mittal, S., Meer, P.: Conjugate gradient on Grassmann manifolds for robust subspace estimation. Image. Vis. Comput. 30(2), 417–427 (2012)

    Article  Google Scholar 

  35. Ngo, T., Saad, Y.: Scaled gradients on Grassmann manifolds for matrix completion. Adv. Neural. Inf. Process. Syst. 25, 1412–1420 (2012)

    Google Scholar 

  36. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, New York (1999)

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  38. Toint, P.L.: An assessment of non-monotone linesearch techniques for unconstrained optimization. SIAM J. Sci. Comput. 17, 725–739 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  39. Toint, P.L.: Non-monotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77, 69–94 (1997)

    MathSciNet  MATH  Google Scholar 

  40. Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142(1), 397–434 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  41. Zhang, H., Hager, W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14(4), 1043–1056 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

J.B.F., D.S.G and F.S.V.B are grateful to CNPq by the financial support (Grant Nos. 421386/2016-9 and 308523/2017-2). L.L.T.P would like to thank to CAPES by the scholarship during her Ph.D at Universidade Federal de Santa Catarina. This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior — Brasil (CAPES) — Finance Code 001. D.S.G also thanks CAPES/Print Process 88881.310538/2018-01 which allows him to present part of this work at ICCOPT 2019. We appreciate so much the dedication of the referees whose comments meaningfully improved the quality of this work.

Author information

Authors and Affiliations

  1. Universidade Federal de Santa Catarina, Florianópolis, Brazil

    Juliano B. Francisco, Douglas S. Gonçalves & Fermín S. V. Bazán

  2. Universidad Nacional Mayor de San Marcos, Lima, Peru

    Lila L. T. Paredes

Authors
  1. Juliano B. Francisco
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Douglas S. Gonçalves
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fermín S. V. Bazán
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lila L. T. Paredes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Douglas S. Gonçalves.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Francisco, J.B., Gonçalves, D.S., Bazán, F.S.V. et al. Non-monotone inexact restoration method for nonlinear programming. Comput Optim Appl 76, 867–888 (2020). https://doi.org/10.1007/s10589-019-00129-2

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-019-00129-2

Keywords

Mathematics Subject Classification

Search

Navigation