Using orthogonally structured positive bases for constructing positive k-spanning sets with cosine measure guarantees

DOI10.1016/J.LAA.2023.10.006MaRDI QIDQ6087872zbMATH OpenFDO

Authors Warren L. Hare, Gabriel Jarry-Bolduc, Sébastien Kerleau, C. W. Royer

Publication date 16 November 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.06383

\(k\)-cosine measure cosine measure derivative-free optimization positive \(k\)-bases positive \(k\)-spanning sets positive bases positive spanning sets

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Canonical forms, reductions, classification (15A21)

Abstract: Positive spanning sets span a given vector space by nonnegative linear combinations of their elements. These have attracted significant attention in recent years, owing to their extensive use in derivative-free optimization. In this setting, the quality of a positive spanning set is assessed through its cosine measure, a geometric quantity that expresses how well such a set covers the space of interest. In this paper, we investigate the construction of positive

k

-spanning sets with geometrical guarantees. Our results build on a recently identified type of positive spanning sets called orthogonally structured positive bases. We first describe how to identify such sets and compute their cosine measure efficiently. We then focus our study on positive

k

-spanning sets, for which we provide a complete description, as well as a new notion of cosine measure that accounts for the resilient nature of such sets. By combining our results, we are able to use orthogonally structured positive bases to create positive

k

-spanning sets with guarantees on the value of their cosine measures.

Review text

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)]).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Using orthogonally structured positive bases for constructing positive \(k\)-spanning sets with cosine measure guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087872)