zbMATH — the first resource for mathematics

Positive bases with maximal cosine measure. (English) Zbl 1429.90099
Summary: Positive spanning sets and positive bases are important in the construction of derivative-free optimization algorithms. The convergence properties of the algorithms might be tied to the cosine measure of the positive basis that is used, and having higher cosine measure might in general be preferable. In this paper, the upper bound of the cosine measure for certain positive bases in \(\mathbb{R}^n\) are found. In particular, if the size of the positive basis is \(n+1\) (the minimal positive bases), the maximal value of the cosine measure is \(1 / n\). A straightforward corollary is that the maximal cosine measure for any positive spanning set of size \(n+1\) is \(1 / n\). If the size of a positive basis is \(2n\) (the maximal positive bases) the maximal cosine measure is \(1/\sqrt{n}\). In all the cases described, the positive bases achieving these upper bounds are characterized.
Reviewer: Reviewer (Berlin)

90C56 Derivative-free methods and methods using generalized derivatives
Full Text: DOI
[1] Alberto, P.; Nogueira, F.; Rocha, H.; Vicente, LN, Pattern search methods for user-provided points: application to molecular geometry problems, SIAM J. Optim., 14, 1216-1236, (2004) · Zbl 1079.90126
[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., Hare, W.: Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer, Berlin (2017) · Zbl 1391.90001
[4] Audet, C.; Ianni, A.; Digabel, SL; Tribes, C., Reducing the number of function evaluations in mesh adaptive direct search algorithms, SIAM J. Optim., 24, 621-642, (2014) · Zbl 1297.90149
[5] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on optimization, vol. 8. Society of Industrial and Applied Mathematics and the Mathematical Programming Society, Philadelphia (2009) · Zbl 1163.49001
[6] Davis, C., Theory of positive linear dependence, Am. Math. J., 76, 733-746, (1954) · Zbl 0058.25201
[7] Dodangeh, M.; Vicente, LN; Zhang, Z., On the optimal order of worst case complexity of direct search, Optim. Lett., 10, 699-708, (2016) · Zbl 1346.90764
[8] Hare, W.; Song, H., On the cardinality of positively linearly independent sets, Optim. Lett., 10, 649-654, (2016) · Zbl 1336.90106
[9] Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013) · Zbl 1267.15001
[10] Kolda, TG; Lewis, RM; Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482, (2003) · Zbl 1059.90146
[11] Lewis, R.M., Torczon, V.: Rank ordering and positive bases in pattern search algorithms. NASA Contractor Report 201628, ICASE Report No. 96-71, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center (1999) · Zbl 1031.90047
[12] Regis, RG, On the properties of positive spanning sets and positive bases, Optim. Eng., 17, 229-262, (2016) · Zbl 1364.90364
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.