[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An efficient derivative-free algorithm for bound constrained mixed-integer optimization

  • Special Issue
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

Abstract

Mixed integer optimization is very important and complicated task in the optimization field, which widely exists in the engineering problems. In order to improve the efficiency of derivative-free algorithm when solving the mixed integer optimization problems, we propose an efficient derivative-free algorithm, which is based on the modified minimal positive base and the technique of search directions rotation. The method using the modified minimal positive base only needs at most \(n+1\) function evaluations at every iteration, compared with the derivative-free algorithms based on the maximal 2n positive base, where n is the number of variables. Meantime, the technique of search directions rotation we proposed can overcome the disadvantage of the method based on the minimal positive base which can cause undesirable large angles between some positive base directions and large unexplored feasible domain. Accordingly the convergence to stationary points is proved. To evaluate the performance of our method, we compare it with two classical algorithms on 50 benchmark problems. The results of numerical experiments show that the method can reduce the number of function evaluations and improve the efficiency of the algorithm.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Audet C, Dennis JE (2001) Pattern search algorithms for mixed variable programming. SIAM J Optim 11(3):573–594

    Article  MathSciNet  Google Scholar 

  2. Abramson MA (2002) Pattern Search Algorithms for Mixed Variable General Constrained Optimization Problems. Rice University, Houston

    Google Scholar 

  3. Abramson MA, Audet C, Dennis JE (2007) Filter pattern search algorithms for mixed variable constrained optimization problems. Pac J Optim 3(3):573–594

    MathSciNet  Google Scholar 

  4. Lucidi S, Piccialli V, Sciandrone M (2005) An algorithm model for mixed variable programming. SIAM J Optim 15(4):1057–1084

    Article  MathSciNet  Google Scholar 

  5. Sriver TA, Chrissis JW, Abramson MA (2009) Pattern search ranking and selection algorithms for mixed variable simulation-based optimization. Eur J Op Res 198(3):878–890

    Article  MathSciNet  Google Scholar 

  6. Abramson MA, Audet C, Chrissis JW et al (2009) Mesh adaptive direct search algorithms for mixed variable optimization. Optim Lett 3(1):35–47

    Article  MathSciNet  Google Scholar 

  7. Liuzzi G, Lucidi S, Rinaldi F (2012) Derivative-free methods for bound constrained mixed-integer optimization. Comput Optim Appl 53(2):505–526

    Article  MathSciNet  Google Scholar 

  8. Liuzzi G, Lucidi S, Rinaldi F (2014) Derivative-free methods for mixed-integer constrained optimization problems. J Optim Theory Appl 164(3):933–965

    Article  MathSciNet  Google Scholar 

  9. Newby E, Ali MM (2015) A trust-region-based derivative free algorithm for mixed integer programming. Comput Optim Appl 60(1):199–229

    Article  MathSciNet  Google Scholar 

  10. Mller J, Shoemaker CA, Pich R (2013) SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems. Comput Op Res 40(5):1383–1400

    Article  MathSciNet  Google Scholar 

  11. Mller JMISO (2016) mixed-integer surrogate optimization framework. Optim Eng 17(1):1–27

    MathSciNet  Google Scholar 

  12. Guo JY, Lu WX, Yang QC, Miao TS (2019) The application of 0–1 mixed integer nonlinear programming optimization model based on a surrogate model to identify the groundwater pollution source. J Contam Hydrol 220:18–25

    Article  CAS  PubMed  Google Scholar 

  13. Bjarne G, Henrik A (2019) ReLU networks as surrogate models in mixed-integer linear programs. Comput Chem Eng 131:16580

    Google Scholar 

  14. Audet C, Dennis JE (2006) Mesh adaptive direct search algorithms for constrained optimization. SIAM J Optim 17(1):188–217

    Article  MathSciNet  Google Scholar 

  15. Lucidi S, Sciandrone M (2002) A derivative-free algorithm for bound constrained optimization. Comput Optim Appl 21(2):119–142

    Article  MathSciNet  Google Scholar 

  16. Ianni A, Audet C, Digabel SL, Tribes C (2014) Reducing the number of function evaluations in mesh adaptive direct search algorithms. SIAM J Optim 24(2):621–642

    Article  MathSciNet  Google Scholar 

  17. Cust AL (2006) Using simplex gradients of nonsmooth functions in direct search methods. IMA J Numer Anal 28(28):770–784

    MathSciNet  Google Scholar 

  18. MATHWORKS, I. MATLAB GADS toolbox. (2005) http://www.mathworks.com/products/gads/

  19. Elster C, Neumaier A (1995) A grid algorithm for bound-constrained optimization of noisy functions. IMA J Numer Anal 15:585–608

    Article  MathSciNet  Google Scholar 

  20. Hock W, Schittkowski K (1981) Test examples for nonlinear programming codes. Lecture notes in economics and mathematical systems. J Optim Theory Appl 187:26–122

    Google Scholar 

  21. Schittkowski K (1987) More Test Examples for Nonlinear Programming Codes, vol 282. Lecture Notes in Economics and Mathematical Systems. Springer, Berlin

    Google Scholar 

  22. Hedar A Test functions for unconstrained global optimization. http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_?les/TestGO_?les/Page364. htm. Accessed 15 Feb 2013

  23. MorE JJ, Wild AS (2009) Benchmarking derivative-free optimization algorithms. SIAM J Optim 20:172–191

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The study of Yang was funded by Yanta Scholars Foundation of Xian University of Finance and Economics.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Xidian University, Xi’an, 710071, Shaanxi, China

    Shanxue Yang & Hongwei Liu

  2. School of Statistics, Xi’an University of Finance and Economics, Xi’an, 710100, Shaanxi, China

    Shanxue Yang

  3. College of Mathematics and Statistics, Huanggang Normal University, Huanggang, 438000, Hubei, China

    Chen Pan

Authors
  1. Shanxue Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongwei Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chen Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chen Pan.

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

Yang, S., Liu, H. & Pan, C. An efficient derivative-free algorithm for bound constrained mixed-integer optimization. Evol. Intel. 17, 11–20 (2024). https://doi.org/10.1007/s12065-019-00326-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-019-00326-2

Keywords

Search

Navigation