Hare, Warren; Jarry-Bolduc, Gabriel A deterministic algorithm to compute the cosine measure of a finite positive spanning set. (English) Zbl 1448.90101 Optim. Lett. 14, No. 6, 1305-1316 (2020). Summary: Originally developed in 1954, positive bases and positive spanning sets have been found to be a valuable concept in derivative-free optimization (DFO). The quality of a positive basis (or positive spanning set) can be quantified via the cosine measure and convergence properties of certain DFO algorithms are intimately linked to the value of this measure. However, it is unclear how to compute the cosine measure for a positive basis from the definition. In this paper, a deterministic algorithm to compute the cosine measure of any positive basis or finite positive spanning set is provided. The algorithm is proven to return the exact value of the cosine measure in finite time. Cited in 4 Documents MSC: 90C56 Derivative-free methods and methods using generalized derivatives Keywords:cosine measure; positive basis; positive spanning set Software:OrthoMADS; PSwarm; IMFIL PDFBibTeX XMLCite \textit{W. Hare} and \textit{G. Jarry-Bolduc}, Optim. Lett. 14, No. 6, 1305--1316 (2020; Zbl 1448.90101) Full Text: DOI arXiv References: [1] Abramson, M.; Audet, C.; Dennis, J.; Le Digabel, S., Orthomads: a deterministic mads instance with orthogonal directions, SIAM J. Optim., 20, 948-966 (2009) · Zbl 1189.90202 [2] Audet, C., A short proof on the cardinality of maximal positive bases, Optim. Lett., 5, 191-194 (2011) · Zbl 1211.90190 [3] Audet, C.; Dennis, J., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217 (2006) · Zbl 1112.90078 [4] Audet, C.; Hare, W., Derivative-Free and Blackbox Optimization (2017), Cham: Springer, Cham · Zbl 1391.90001 [5] Audet, C.; Ianni, A.; Le Digabel, S.; Tribes, C., Reducing the number of function evaluations in mesh adaptive direct search algorithms, SIAM J. Optim., 24, 621-642 (2014) · Zbl 1297.90149 [6] Brown, W., A Second Course in Linear Algebra (1988), New York: Wiley, New York · Zbl 0642.15001 [7] Conn, A.; Scheinberg, K.; Vicente, L., Introduction to Derivative-Free Optimization (2009), Philadelphia: SIAM, Philadelphia · Zbl 1163.49001 [8] Coope, I.; Price, C., On the convergence of grid-based methods for unconstrained optimization, SIAM J. Optim., 11, 859-869 (2001) · Zbl 1035.90107 [9] Coope, I.; Price, C., Positive bases in numerical optimization, Comput. Optim. Appl., 21, 169-175 (2002) · Zbl 0988.90036 [10] Custódio, A.; Dennis, J.; Vicente, L., Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer. Anal., 28, 770-784 (2008) · Zbl 1156.65059 [11] Davis, C., Theory of positive linear dependence, Am. J. Math., 76, 733-746 (1954) · Zbl 0058.25201 [12] Dodangeh, M.; Vicente, L.; Zhang, Z., On the optimal order of worst case complexity of direct search, Optim. Lett., 10, 699-708 (2016) · Zbl 1346.90764 [13] Golub, G.; Van Loan, C., Matrix Computations (2013), Baltimore: The Johns Hopkins University Press, Baltimore · Zbl 1268.65037 [14] Kelley, C., Implicit Filtering (2011), Philadelphia: SIAM, Philadelphia · Zbl 1246.68017 [15] Kolda, T.; Lewis, R.; Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482 (2003) · Zbl 1059.90146 [16] Lewis, R., Torczon, V.: Rank ordering and positive bases in pattern search algorithms. Tech. report, Institute for Computer Applications in Science and Engineering, Hampton VA (1996) [17] McKinney, R., Positive bases for linear spaces, Trans. Am. Math. Soc., 103, 131-148 (1962) · Zbl 0115.32901 [18] Nævdal, G., Positive bases with maximal cosine measure, Optim. Lett., 13, 1-8 (2018) [19] Reay, J., A new proof of the Bonnice-Klee theorem, Proc. Am. Math. Soc., 16, 585-587 (1965) · Zbl 0138.37501 [20] Reay, J., Unique minimal representations with positive bases, Am. Math. Mon., 73, 253-261 (1966) · Zbl 0137.15103 [21] Regis, R., On the properties of positive spanning sets and positive bases, Optim. Eng., 17, 229-262 (2016) · Zbl 1364.90364 [22] Romanowicz, Z., Geometric structure of positive bases in linear spaces, Appl. Math., 19, 557-567 (1987) · Zbl 0725.15002 [23] Shephard, G., Diagrams for positive bases, J. Lond. Math. Soc., 2, 165-175 (1971) · Zbl 0225.15004 [24] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25 (1997) · Zbl 0884.65053 [25] Van Dyke, B.; Asaki, T., 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) · Zbl 1284.90081 [26] Vaz, A.; Vicente, L., PSwarm: a hybrid solver for linearly constrained global derivative-free optimization, Optim. Methods Softw., 24, 669-685 (2009) · Zbl 1177.90327 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.