Abstract
The purpose of this paper is to introduce a new instance of the Mesh Adaptive Direct Search (Mads) class of algorithms, which utilizes a more uniform distribution of poll directions than do other common instances, such as OrthoMads and LtMads. Our new implementation, called QrMads, bases its poll directions on an equal area partitioning of the n-dimensional unit sphere and the QR decomposition to obtain an orthogonal set of directions. While each instance produces directions which are dense in the limit, QrMads directions are more uniformly distributed in the unit sphere. This uniformity is the key to enhanced performance in higher dimensions and for constrained problems. The trade-off is that QrMads is no longer deterministic and at each iteration the set of polling directions is no longer orthogonal. Instead, at each iteration, the poll directions are only ‘nearly orthogonal,’ becoming increasingly closer to orthogonal as the mesh size decreases. Finally, we present a variety of test results on smooth, nonsmooth, unconstrained, and constrained problems and compare them to OrthoMads on the same set of problems.
Similar content being viewed by others
References
Audet, C., Dennis, J. Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188–217 (2006)
Abramson, M.A., Audet, C.: Convergence of mesh adaptive direct search to second-order stationary points. SIAM J. Optim. 17(2), 606–619 (2006)
Clarke, F.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1983)
Vicente, L., Custódio, A.: Analysis of direct searches for discontinuous functions. Math. Program. 133(1–2), 299–325 (2012)
Rockafellar, R.: Generalized directional derivatives and subgradients of nonconvex functions. Can. J. Math. 32(2), 257–280 (1980)
Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7(1), 1–25 (1997)
Abramson, M., Audet, C., Dennis, J. Jr., Le Digabel, S.: ORTHOMADS: a deterministic MADS instance with orthogonal directions. SIAM J. Optim. 10(2), 948–966 (2009)
Coope, I.D., Price, C.J.: Frame-based methods for unconstrained optimization. J. Optim. Theory Appl. 107(2), 261–274 (2000)
Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2(1), 84–90 (1960)
Leopardi, P.: A partition of the unit sphere into regions of equal area and small diameter. Electron. Trans. Numer. Anal. 25, 309–327 (2006)
Leopardi, P.: Distributing points on the sphere: partitions, separation, quadrature and energy. Ph.D. thesis, University of New South Wales (2007)
Leopardi, P.: Diameter bounds for equal area partitions of the unit sphere. Electron. Trans. Numer. Anal. 35, 1–16 (2009)
Audet, C., Custódio, A.L., Dennis, J. Jr.: Erratum: mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 18(4), 1501–1503 (2008)
Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17–41 (1981)
Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Tech. Rep. No. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)
Karmitsa, N.: Test problems for large-scale nonsmooth minimization. Tech. Rep. No. B. 4/2007, University of Jyväskylä (2007)
Ledoux, M.: The Concentration of Measure Phenomenon. Am. Math. Soc., Providence (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Van Dyke, B., Asaki, T.J. Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions. J Optim Theory Appl 159, 805–821 (2013). https://doi.org/10.1007/s10957-013-0356-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-013-0356-y