The purpose of this paper is twofold: first, to introduce deterministic strategies for directional direct-search methods, including new instances of the mesh adaptive direct-search (MADS) and the generating set search (GSS) class of algorithms, which utilize a nice distribution of PoLL directions when compared to other strategies, and second, to introduce variants of each algorithm which utilize a minimal positive basis at each step. The strategies base their PoLL directions on the use of the QR decomposition to obtain an orthogonal set of directions or on using the equal angular directions from a regular simplex centered at the origin with vertices on the unit sphere. Test results are presented on a set of smooth, nonsmooth, unconstrained, and constrained problems that give comparisons between the various implementations of these directional direct-search methods. 1. Introduction In [1], Vicente and Custódio introduced a framework for directional direct-search methods (DSM) encompassing both the MADS [2] class of algorithms (using an underlying mesh and simple decrease) and the Gss [3] class of algorithms (using sufficient decrease under a forcing function ) for black-box optimization problems of the form where the objective function is nonsmooth, possibly discontinuous and is the set of feasible points. The algorithms under this framework are shown to have first order convergence results in the Rockafellar sense [4] for discontinuous functions. The framework is shown in Algorithm 1. Algorithm 1: The directional direct-search method of [ 1]. While both algorithms fall under this framework and are shown to have the same convergence results, there are tradeoffs for either choice. The MADS class of algorithms not only requires a bit more complexity in choosing polling directions, but also requires simple decrease in order to accept an iteration as successful. Under the given framework, any instance of Gss requires sufficient decrease using a forcing function that must be chosen under unknown criteria. The sufficient decrease condition, however, can be implemented in such a way that it is mostly negligible and the method for choosing polling directions is simpler because of the absence of a mesh. Each iteration of this DSM framework is characterized by two steps, a SEARCH and a POLL. The POLL step may be opportunistic (the POLL stops if a successful point has been found) and is governed by a POLL size parameter (MADS denotes this ) such that under certain assumptions. These assumptions include the requirement that at each iteration either the set of SEARCH
References
[1]
L. N. Vicente and A. L. Custódio, “Analysis of direct searches for discontinuous functions,” Mathematical Programming, vol. 133, pp. 299–325, 2012.
[2]
C. Audet and J. E. Dennis, “Mesh adaptive direct search algorithms for constrained optimization,” SIAM Journal on Optimization, vol. 17, no. 1, pp. 188–217, 2006.
[3]
T. G. Kolda, R. M. Lewis, and V. Torczon, “Optimization by direct search: new perspectives on some classical and modern methods,” SIAM Review, vol. 45, no. 3, pp. 385–482, 2003.
[4]
R. T. Rockafellar, “Generalized directional derivatives and subgradients of nonconvex functions,” Canadian Journal of Mathematics, vol. 32, no. 2, pp. 257–280, 1980.
[5]
M. A. Abramson and C. Audet, “Convergence of mesh adaptive direct search to second-order stationary points,” SIAM Journal on Optimization, vol. 17, no. 2, pp. 606–619, 2006.
[6]
F. H. Clarke, Optimization and Nonsmooth Analysis, SIAM, Philadelphia, Pa, USA, 1983.
[7]
V. Torczon, “On the convergence of pattern search algorithms,” SIAM Journal on Optimization, vol. 7, no. 1, pp. 1–25, 1997.
[8]
M. A. Abramson, C. Audet, J. Dennis, and S. Le Digabel, “OrthoMADS: a deterministic MADS instance with orthogonal directions,” SIAM Journal on Optimization, vol. 20, no. 2, pp. 948–966, 2009.
[9]
I. D. Coope and C. J. Price, “Frame based methods for unconstrained optimization,” Journal of Optimization Theory and Applications, vol. 107, no. 2, pp. 261–274, 2000.
[10]
J. H. Halton, “On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,” Numerische Mathematik, vol. 2, no. 1, pp. 84–90, 1960.
[11]
B. Van Dyke and T. J. Asaki, “Using qr decomposition to obtain a new instance of mesh adaptive direct search with uniformly distributed polling directions,” Journal of Optimization Theory and Applications, vol. 159, no. 3, pp. 805–821, 2013.
[12]
C. Audet, A. Ianni, S. le Digabel, and C. Tribes, “Reducing the number of function evaluations in mesh adaptive direct search algorithms,” SIAM Journal on Optimization, vol. 24, no. 2, pp. 621–642, 2014.
[13]
P. Alberto, F. Nogueira, H. Rocha, and L. N. Vicente, “Pattern search methods for user-provided points: application to molecular geometry problems,” SIAM Journal on Optimization, vol. 14, no. 4, pp. 1216–1236, 2004.
[14]
K. R. Fowler, J. P. Reese, C. E. Kees et al., “Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems,” Advances in Water Resources, vol. 31, no. 5, pp. 743–757, 2008.
[15]
J. J. Moré, B. S. Garbow, and K. E. Hillstrom, “Testing unconstrained optimization software,” ACM Transactions on Mathematical Software, vol. 7, no. 1, pp. 17–41, 1981.
[16]
L. Luksan and J. Vlcek, “Test problems for unconstrained optimization,” Tech. Rep. 897, Academy of Sciences of the Czech Republic, Institute of Computer Science, 2003.
[17]
N. Karmitsa, “Test problems for large-scale nonsmooth minimization,” Reports of the Department of Mathamatical Information Technology, Series B. Scientific Computing. Technical Report B. 4/2007, University of Jyv？skyl？, 2007.
[18]
L. Luksan and J. Vlcek, “Test problems for nonsmooth unconstrained and linearly constrained optimization,” Tech. Rep. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic, January 2000.
[19]
X.-S. Yang, “Appendix A: test problems in optimization,” in Engineering Optimization, pp. 261–266, 2010.
[20]
L. Luksan, M. Tuma, J. Vlcek et al., “UFO 2011 interactive system for universal functional optimization,” Tech. Rep. 1151, Academy of Sciences of the Czech Republic, Institute of Computer Science, December 2011.
[21]
L. Z. Lu and C. E. M. Pearce, “Some new bounds for singular values and eigenvalues of matrix products,” Annals of Operations Research, vol. 98, pp. 141–148, 2000.
[22]
C. Audet, A. L. Custódio, and J. E. Dennis Jr., “Erratum: mesh adaptive direct search algorithms for constrained optimization,” The SIAM Journal on Optimization, vol. 18, no. 4, pp. 1501–1503, 2008.
[23]
I. M. Sobol, “On the distribution of points in a cube and the approximate evaluation of integrals,” USSR Computational Mathematics and Mathematical Physics, vol. 7, no. 4, pp. 86–112, 1967.
[24]
J. J. More and S. M. Wild, “Benchmarking derivative-free optimization algorithms,” SIAM Journal on Optimization, vol. 20, no. 1, pp. 172–191, 2009.
[25]
M. Ledoux, The Concentration of Measure Phenomenon, American Mathematical Society, Providence, RI, USA, 2001.
[26]
C. Audet and J. E. Dennis Jr., “A progressive barrier for derivative-free nonlinear programming,” SIAM Journal on Optimization, vol. 20, no. 1, pp. 445–472, 2009.
