Skip to main content
SpringerLink
Log in

Incorporating minimum Frobenius norm models in direct search

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

Abstract

The goal of this paper is to show that the use of minimum Frobenius norm quadratic models can improve the performance of direct-search methods. The approach taken here is to maintain the structure of directional direct-search methods, organized around a search and a poll step, and to use the set of previously evaluated points generated during a direct-search run to build the models. The minimization of the models within a trust region provides an enhanced search step. Our numerical results show that such a procedure can lead to a significant improvement of direct search for smooth, piecewise smooth, and noisy 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

Similar content being viewed by others

References

  1. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2009)

    MATH  Google Scholar 

  2. Custódio, A.L., Vicente, L.N.: Using sampling and simplex derivatives in pattern search methods. SIAM J. Optim. 18, 537–555 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  3. Custódio, A.L., Dennis, J.E. Jr., Vicente, L.N.: Using simplex gradients of nonsmooth functions in direct search methods. IMA J. Numer. Anal. 28, 770–784 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  4. DFO. http://www.coin-or.org/projects.html

  5. Fasano, G., Morales, J.L., Nocedal, J.: On the geometry phase in model-based algorithms for derivative-free optimization. Optim. Methods Softw. 24, 145–154 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  6. Gray, G.A., Kolda, T.G.: Algorithm 856: APPSPACK 4.0: Asynchronous parallel pattern search for derivative-free optimization. ACM Trans. Math. Softw. 32, 485–507 (2006)

    Article  MathSciNet  Google Scholar 

  7. Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: New perspectives on some classical and modern methods. SIAM Rev. 45, 385–482 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. MATLAB, The MathWorks Inc. http://www.mathworks.com

  9. Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20, 172–191 (2009). http://www.mcs.anl.gov/~more/dfo

    Article  MATH  MathSciNet  Google Scholar 

  10. Moré, J.J., Sorensen, D.C., Hillstrom, K.E., Garbow, B.S.: The MINPACK project. In: Cowell, W.J. (ed.) Sources and Development of Mathematical Software, pp. 88–111. Prentice-Hall, New York (1984). http://www.netlib.org/minpack

    Google Scholar 

  11. Powell, M.J.D.: Least Frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program. 100, 183–215 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  12. Powell, M.J.D.: Developments of NEWUOA for minimization without derivatives. IMA J. Numer. Anal. 28, 649–664 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  13. The Matrix Computation Toolbox. http://www.maths.manchester.ac.uk/~higham/mctoolbox

  14. Wild, S.M.: MNH: A derivative-free optimization algorithm using minimal norm Hessians. In: Tenth Copper Mountain Conference on Iterative Methods (April 2008)

Download references

Author information

Authors and Affiliations

  1. CMA-UNL, Department of Mathematics, FCT-UNL, Quinta da Torre, 2829-516, Caparica, Portugal

    A. L. Custódio

  2. INESC Coimbra, R. Antero de Quental, 199, 3000-033, Coimbra, Portugal

    H. Rocha

  3. CMUC, Department of Mathematics, University of Coimbra, 3001-454, Coimbra, Portugal

    L. N. Vicente

Authors
  1. A. L. Custódio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. Rocha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. L. N. Vicente
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. L. Custódio.

Additional information

Support has been provided by FCT under grants POCI/MAT/59442/2004 and PTDC/MAT/64838/2006.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Custódio, A.L., Rocha, H. & Vicente, L.N. Incorporating minimum Frobenius norm models in direct search. Comput Optim Appl 46, 265–278 (2010). https://doi.org/10.1007/s10589-009-9283-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-009-9283-0

Keywords

Search

Navigation