Skip to main content
SpringerLink
Log in

Optimizing radial basis functions by d.c. programming and its use in direct search for global derivative-free optimization

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In this paper, we address the global optimization of functions subject to bound and linear constraints without using derivatives of the objective function. We investigate the use of derivative-free models based on radial basis functions (RBFs) in the search step of direct-search methods of directional type. We also study the application of algorithms based on difference of convex (d.c.) functions programming to solve the resulting subproblems which consist of the minimization of the RBF models subject to simple bounds on the variables. Extensive numerical results are reported with a test set of bound and linearly constrained 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

  • Ali MM, Khompatraporn C, Zabinsky ZB (2005) A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J Glob Optim 31:635–672

    Article  Google Scholar 

  • Le Thi HA, Pham Dinh T (1997) Convex analysis approach to d.c. programming: theory, algorithms and applications. Acta Math Vietnam 22:289–355

    Google Scholar 

  • Le Thi HA, Pham Dinh T (1998) D.C. optimization algorithms for solving the trust-region subproblem. SIAM J Optim 8:476–505

    Article  Google Scholar 

  • Le Thi HA, Pham Dinh T (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133:23–46

    Article  Google Scholar 

  • Björkman M, Holmström K (2000) Global optimization of costly nonconvex functions using radial basis functions. Optim Eng 1:373–397

    Article  Google Scholar 

  • Conn AR, Scheinberg K, Vicente LN (2009) Introduction to derivative-free optimization. MPS-SIAM series on optimization. SIAM, Philadelphia

    Book  Google Scholar 

  • Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201–213

    Article  Google Scholar 

  • Fourer R, Gay DM, Kernighan BW (1990) A modeling language for mathematical programming. Manag Sci 36:519–554

    Article  Google Scholar 

  • Griffin JD, Kolda TG (2010) Asynchronous parallel hybrid optimization combining DIRECT and GSS. Optim Methods Softw 25:797–817

    Article  Google Scholar 

  • Gutmann H-M (2001) A radial basis function method for global optimization. J Glob Optim 19:201–227

    Article  Google Scholar 

  • Hedar A-R, Fukushima M (2004) Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization. Optim Methods Softw 19:291–308

    Article  Google Scholar 

  • Ingber L, Rosen B (1992) Genetic algorithms and very fast simulated reannealing: a comparison. Math Comput Model 16:87–100

    Article  Google Scholar 

  • Ji Y, Zhang K-C, Qu S-J (2006) A deterministic global optimization algorithm. Appl Math Comput 185:382–387

    Article  Google Scholar 

  • Jones D, Perttunen C, Stuckman B (1993) Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79:157–181

    Article  Google Scholar 

  • Käck J-E (2004) Constrained global optimization with radial basis functions. Technical report research report MdH-IMa-2004, Department of Mathematics and Physics, Mälardalen University, Västerås, Sweden

  • Kiseleva E, Stepanchuk T (2003) On the efficiency of a global non-differentiable optimization algorithm based on the method of optimal set partitioning. J Glob Optim 25:209–235

    Article  Google Scholar 

  • Kolda TG, Lewis RM, Torczon V (2003) Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev 45:385–482

    Article  Google Scholar 

  • Locatelli M (2003) A note on the Griewank test function. J Glob Optim 25:169–174

    Article  Google Scholar 

  • Locatelli M, Schoen F (2002) Fast global optimization of difficult Lennard–Jones clusters. Comput Optim Appl 21:55–70

    Article  Google Scholar 

  • Michalewicz Z (1994) Evolutionary computation techniques for nonlinear programming problems. Int Trans Oper Res 1:223–240

    Article  Google Scholar 

  • Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, Berlin

    Google Scholar 

  • Mongeau M, Karsenty H, Rouzé V, Hiriart-Urruty J-B (2000) Comparison of public-domain software for black box global optimization. Optim Methods Softw 13:203–226

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Oeuvray R (2005) Trust-region methods based on radial basis functions with application to biomedical imaging. PhD thesis, Institut de Mathématiques, École Polytechnique Fédérale de Lausanne, Switzerland

  • Oeuvray R, Bierlaire M (2009) BOOSTERS: a derivative-free algorithm based on radial basis functions. Int J Model Simul 29:4634–4636

    Google Scholar 

  • Parsopoulos KE, Plagianakos VP, Magoulas GD, Vrahatis MN (2001) Stretching technique for obtaining global minimizers through particle swarm optimization. In: Proc of the particle swarm optimization workshop, Indianapolis, USA, pp 22–29

    Google Scholar 

  • Pham Dinh T, Elbernoussi S (1988) Duality in d.c. (difference of convex functions) optimization. In: Subgradient methods, vol 84. Birkhäuser, Basel, pp 276–294

    Google Scholar 

  • Regis RG, Shoemaker CA (2005) Constrained global optimization of expensive black box functions using radial basis functions. J Glob Optim 31:153–171

    Article  Google Scholar 

  • Regis RG, Shoemaker CA (2007a) Improved strategies for radial basis function methods for global optimization. J Glob Optim 37:113–135

    Article  Google Scholar 

  • Regis RG, Shoemaker CA (2007b) Parallel radial basis function methods for the global optimization of expensive functions. Eur J Oper Res 182:514–535

    Article  Google Scholar 

  • Regis RG, Shoemaker CA (2007c) A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J Comput 19:497–509

    Article  Google Scholar 

  • Runarsson TP, Yao X (2000) Stochastic ranking for constrained evolutionary optimization. IEEE Trans Evol Comput 4:284–294

    Article  Google Scholar 

  • Vaz AIF, Vicente LN (2007) A particle swarm pattern search method for bound constrained global optimization. J Glob Optim 39:197–219

    Article  Google Scholar 

  • Vaz AIF, Vicente LN (2009) Pswarm: a hybrid solver for linearly constrained global derivative-free optimization. Optim Methods Softw 24:669–685

    Article  Google Scholar 

  • Wild SM, Shoemaker CA (2011) Global convergence of radial basis function trust region derivative-free algorithms. SIAM J Optim. doi:10.1137/09074927x

  • Wild SM, Regis RG, Shoemaker CA (2008) ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J Sci Comput 30:3197–3219

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory of Theoretical and Applied Computer Science (LITA EA 3097), Paul Verlaine University, Metz, Ile du Saulcy, 57045, Metz, France

    H. A. Le Thi

  2. Department of Production and Systems, University of Minho, Campus de Gualtar, 4710-057, Braga, Portugal

    A. I. F. Vaz

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

    L. N. Vicente

Authors
  1. H. A. Le Thi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. I. F. Vaz
    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. I. F. Vaz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Le Thi, H.A., Vaz, A.I.F. & Vicente, L.N. Optimizing radial basis functions by d.c. programming and its use in direct search for global derivative-free optimization. TOP 20, 190–214 (2012). https://doi.org/10.1007/s11750-011-0193-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-011-0193-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation