×

zbMATH — the first resource for mathematics

Unified approach for solving box-constrained models with continuous or discrete variables by non monotone direct search methods. (English) Zbl 1417.90119
Summary: This paper is an outgrowth of previous works devoted to the application of non monotone direct search methods (DSMs) to locate the global minimum of an objective function subjected to bounds on its variables defined in the Euclidean space. This paper proves that DSMs can be easily adapted for solving models with discrete variables, as long as these variables are regularly spaced along each coordinate. Convergence is established without imposing additional conditions on the objective function, but the construction of the search directions plays a fundamental role. Moreover, function evaluations are carried out only on discrete feasible points, avoiding spurious computations on non feasible points. The paper describes a pseudo code and a preliminary code written in C, which is applied to solve a discretized version of a continuous problem with encouraging results.

MSC:
90C26 Nonconvex programming, global optimization
Software:
BOBYQA; MultiMin; DFLBOX; DFL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramson, MA; Audet, C.; Chrissis, JW; Walston, JG, Mesh adaptive direct search algorithms for mixed variable optimization, Optim. Lett., 3, 35-47, (2009) · Zbl 1154.90551
[2] Audet, C.; Dennis, J., Pattern search algorithms for mixed variable programming, SIAM J. Optim., 11, 573-594, (2001) · Zbl 1035.90048
[3] Audet, C.; Kokkolaras, M., Blackbox and derivative-free optimization: theory, algorithms and applications, Optim. Eng., 17, 1-2, (2016) · Zbl 1364.90008
[4] Custodio, A.L., Scheinberg, K., Nunes Vicente, L.: Methodologies and software for derivative-free optimization. Internal Report (2017). http://www.mat.uc.pt/ lnv/papers/dfo-survey.pdf
[5] García-Palomares, UM, Software companion for DFO approach for bounded and discrete variables, Researchgate., (2016)
[6] García-Palomares, UM; Costa-Montenegro, E.; Asorey-Cacheda, R.; González-Castaño, FJ, Adapting derivative free optimization methods to engineering. Models with discrete variables, Optim. Eng., 13, 579-594, (2012) · Zbl 1293.65092
[7] García-Palomares, UM; García-Urrea, IJ; Rodríguez-Hernández, PS, On sequential and parallel non monotone derivative free algorithms for box constrained optimization, Optim. Methods Softw., 28, 1233-1261, (2013) · Zbl 1278.65088
[8] García-Palomares, UM; González-Castaño, FJ; Burguillo-Rial, JC, A combined global & local search (CGLS) approach to global optimization, J. Global Optim., 34, 409-426, (2006) · Zbl 1149.90426
[9] García-Palomares, UM; Rodríguez, JF, New sequential and parallel derivative-free algorithms for unconstrained minimization, SIAM J. Optim., 13, 79-96, (2002) · Zbl 1049.90133
[10] Gratton, S.; Toint, PL; Troltzsch, A., An active-set trust-region method for derivative-free nonlinear bound-constrained optimization, Optim. Methods Softw., 26, 873-894, (2011) · Zbl 1229.90138
[11] (2017). https://www.inverseproblem.co.nz/OPTI/index.php/Main/HomePage. Accessed 21 Oct 2017
[12] Lewis, RM; Torczon, VJ, Pattern search algorithms for bound constrained minimization, SIAM J. Optim., 9, 1082-1099, (1999) · Zbl 1031.90047
[13] Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for bound constrained mixed-integer optimization, Comput. Optim. Appl., 53, 505-526, (2012) · Zbl 1257.90058
[14] Moré, JJ; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[15] Newby, E.: General solution methods for mixed integer quadratic programming and derivative free mixed integer non-linear programming problems. Dissertation Thesis, University of the Witwatersrand (2013)
[16] Newby, E.; Ali, M., A trust region based derivative free algorithm for mixed integer programs, Comput. Optim. Appl., 60, 199-229, (2015) · Zbl 1308.90112
[17] Ng, K.-M.: A continuation approach for solving nonlinear optimization problems with discrete variables. Dissertation Thesis, Stanford University (2002)
[18] Pintér, J.; Pardalos, P. (ed.); Romeijn, H. (ed.), Global optimization software, test problems, and applications, No. 2, 515-569, (2002), Dordrecht · Zbl 1029.90058
[19] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Cambridge Report NA2009/06, University of Cambridge (2009)
[20] Ríos, LM; Sahidinis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Global Optim., 56, 1247-1293, (2013) · Zbl 1272.90116
[21] Rodríguez-Hernández, P.S.: (2016). http://webs.uvigo.es/pedro.rodriguez/pub/DFO_GGR. Accessed 5 July 2016
[22] Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013) · Zbl 1278.90005
[23] Torczon, V.J.: Multi-directional search: a direct search algorithm for parallel machines. PhD Thesis, Rice University, Houston, TX (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.