Using orthogonally structured positive bases for constructing positive \(k\)-spanning sets with cosine measure guarantees (Q6087872)

In what follows all vectors and subspaces lie in the real space \(\mathbb{R}^{n}\). A positive spanning set (PSS) \(\mathcal{D}\) for a nonzero subspace \( \mathbb{L}\) is a finite set of nonzero vectors such that every element of \( \mathbb{L}\) is a linear combination of the vectors in \(\mathcal{D}\) with nonnegative coefficients. In this case we write \(\mathrm{pspan}(\mathcal{D}):=\mathbb{ L}\). We say that \(\mathcal{D}\) is a positive basis for \(\mathbb{L}\) if \(\mathrm{pspan}(\mathcal{D}):=\mathbb{L}\) and no proper subset of \(\mathcal{D}\) is a PSS for \(\mathbb{L}\). Every positive basis for a subspace \(\mathbb{L}\neq 0\) has dimension \(\dim (\mathbb{L)}+s(\mathcal{D})\) where \(1\leq s(\mathcal{D} )\leq \dim (\mathbb{L)}\). A major motivation for interest in positive bases lies in their application to derivative-free optimization (see, for example, [\textit{W. Hare} and \textit{G. Jarry-Bolduc}, SIAM J. Optim. 30, No. 1, 853--884 (2020; Zbl 1461.90170); \textit{R. G. Regis}, Optim. Eng. 17, No. 1, 229--262 (2016; Zbl 1364.90364); \textit{A. R. Conn} et al., Introduction to derivative-free optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (2009; Zbl 1163.49001)]). The cosine measure \(\mathrm{cm}(\mathcal{D})\) of an nonempty family of nonzero vectors is defined to be \(\min_{u}\max_{d}u^{T}d/\left\Vert d\right\Vert \) where the maximum is over all \(d\in \mathcal{D}\) and the minimum is over all \(u\in \mathbb{R}^{n}\) with \(\left\Vert u\right\Vert =1\). It can be shown that \(\mathrm{cm}(\mathcal{D})>0\) \(\iff \) \(\mathcal{D}\) is a PSS for \(\mathbb{R}^{n}\). One of the goals of this paper is to find a more efficient way to compute \(\mathrm{cm}( \mathcal{D})\) for a positive basis. Linked to this is the concept of an orthogonally structured positive basis (OSPB) which can be characterized as follows. Suppose that \(\mathcal{D}\) is a positive basis for \(\mathbb{R}^{n}\) and chose a matrix \(D\) whose columns are the vectors from \(\mathcal{D}\) in some order; the Gram matrix \(G(D):=D^{T}D\) is uniquely determined by \( \mathcal{D}\) up to similarity by a permutation matrix. The authors show that \(\mathcal{D}\) is an OSPB for \(\mathbb{R}^{n}\) if and only if \(G(D)\) is similar under a permutation matrix to a block diagonal matrix with \(s( \mathcal{D})\) blocks on the diagonal and that this decomposition provides a more efficient way to determine \(\mathrm{cm}(\mathcal{D})\) for an OSPB. The last section of the paper shows how these results can be generalized to cover positive \(k\)-spanning sets (see [\textit{D. A. Marcus}, Discrete Appl. Math. 9, 47--67 (1984; Zbl 0545.52006)]).