∎

11institutetext: Charles Audet 22institutetext: GERAD and Département de
mathématiques et génie industriel, Polytechnique Montréal, Montréal, Québec,
Canada. Audet’s research is partially funded by the Natural Sciences and
Engineering Research Council (NSERC) of Canada, Discovery Grant #2020-04448.
ORCID 0000-0002-3043-5393
22email<EMAIL_ADDRESS>33institutetext: Warren Hare 44institutetext:
Department of Mathematics, University of British Columbia, Kelowna, British
Columbia, Canada.
Hare’s research is partially funded by the Natural Sciences and Engineering
Research Council (NSERC) of Canada, Discover Grant #2018-03865. ORCID
0000-0002-4240-3903
44email<EMAIL_ADDRESS>55institutetext: Gabriel Jarry-
Bolduc66institutetext: Department of Mathematics and Statistics, Saint Francis
Xavier University, Antigonish, Nova Scotia, Canada.
ORCID 0000-0002-1827-8508
66email<EMAIL_ADDRESS>
# The cosine measure relative to a subspace

Charles Audet  Warren Hare  Gabriel Jarry-Bolduc

###### Abstract

The _cosine measure_ was introduced in 2003 to quantify the richness of a
finite positive spanning sets of directions in the context of derivative-free
directional methods. A positive spanning set is a set of vectors whose
nonnegative linear combinations span the whole space. The present work extends
the definition of cosine measure. In particular, the paper studies cosine
measures relative to a subspace, and proposes a deterministic algorithm to
compute it. The paper also studies the situation in which the set of vectors
is infinite. The extended definition of the cosine measure might be useful for
subspace decomposition methods.

###### Keywords:

Positive spanning set positive basis cosine measure gradient approximation
subspace decomposition

##  1 Introduction

Given a set of vectors $D$ in $\mathbb{R}^{n}$, the concepts of spanning,
linear independence, and basis, are considered foundational to linear algebra.
Closely related, but less well studied, are the ideas of positive spanning,
positive linear independence, and positive basis Davi54b . All of these
notions can be defined considering a set’s properties relative to
$\mathbb{R}^{n}$ or relative to a linear subspace regis2016 .

In addition to the intrinsic mathematical interest in these concepts, positive
bases have been shown to be fundamental to the convergence analysis in direct-
search methods in derivative-free optimization. The first occurrence dates
from 1996 RMLewis_VTorczon_1996  and more recent presentations are found in
the textbooks audet2017derivative  and CoScVibook . A key tool in this
analysis is the cosine measure, introduced in KoLeTo03a . Algorithms to
compute the cosine measure are provided in hare2020deterministic ; regis2021 .
Results on the maximal value of the cosine measure for positive bases of
$\mathbb{R}^{n}$ are developed in hare2023nicely ; naevdal2018 . The notion of
cosine measure is also briefly investigated for _positive $k$-spanning set_ of
$\mathbb{R}^{n}$ in hare2024using . Until now, this cosine measure was only
deeply studied for positive spanning sets of $\mathbb{R}^{n}$. In this paper,
we explore the cosine measure relative to a subspace, which effectively
provides a measure of how well a subset of the positive spanning set
considered explores that subspace. The results herein will be of high value in
understanding the subspace decomposition methods which are recently gaining
traction in AuDeLe08 ; CartisRobert2023 ; Gratton2017direct ;
kimiaei2023subspace ; kozak2021stochastic ; xie2023new .

The main goals of this paper are to introduce the notion of cosine measure
relative to a subspace, to demonstrate its value in understanding positive
spanning properties of a set, and to provide a deterministic algorithm to
compute it. As a secondary goal, we provide several novel results examining
the case where the set of vectors is infinite.

The remainder of this paper is organized as follows. The notation is presented
in Section 2 and background results that are necessary to understand this
paper are provided. This includes positive spanning, positive linear
independence, positive basis, cosine measure, cosine vector set, and active
set. These final three definitions are extended to include “relative to a
subspace”. In Section 3, properties of a positive spanning set of a linear
subspace are investigated. It is shown that many known results regarding
$\mathbb{R}^{n}$ are easily adapted to working in a subspace or working with
an infinite set. In Section 4, the notion of cosine measure relative to a
subspace is explored. Several results are provided that link the positive
span, cosine measure, and cosine measure relative to a subspace. The case
where the cosine measure relative to a subspace is equal to $0$ is examined.
The section concludes with new results showing how the cosine measure relative
to a subspace can be used to provide a general error bound on the true
gradient of a smooth function. In Section 5, a deterministic algorithm to
compute the cosine measure relative to the span of the set is provided and
proven to return the correct results. In Section 6, the main results of this
paper are summarized.

##  2 Notation and Preliminaries

The zero vector in $\mathbb{R}^{n}$ is denoted by $\mathbf{0}_{n}$ and the
vector of all ones in $\mathbb{R}^{n}$ is denoted by $\mathbf{1}_{n}.$ When
the dimension of the vector is clear, we may omit the subscript. The $i^{th}$
coordinate vector in $\mathbb{R}^{n}$ is denoted $e_{i}$.

We denote by $B_{n}(x^{0};\Delta)$ the _open ball centered about
$x^{0}\in\mathbb{R}^{n}$ with radius $0<\Delta<\infty$_ and by
$\overline{B}_{n}(x^{0};\Delta)$ the _closed ball centered about $x^{0}$ with
radius $\Delta$._ That is

$\displaystyle
B_{n}(x^{0};\Delta)=\left\\{x\in\mathbb{R}^{n}:\|x-x^{0}\|<\Delta\right\\}\
\mbox{ and }\
\overline{B}_{n}(x^{0};\Delta)=\left\\{x\in\mathbb{R}^{n}:\|x-x^{0}\|\leq\Delta\right\\}.$

Given a set of vectors $D\subseteq\mathbb{R}^{n}$ (possibly infinite), the
cardinality of $D$ is denoted by $|D|$. The radius of the smallest ball
centered at the origin containing the set $D$ is denoted by $\Delta_{D}$ and
given by

$\displaystyle\Delta_{D}$ $\displaystyle=\sup_{d\in D}\|d\|.$ (1)

When useful, in this paper, a set of vectors is represented as a matrix where
each column represents a vector in the set. That is

$D=\\{d_{1},d_{2},\ldots,d_{m}\\}\mbox{ is interchangable with
}D=\begin{bmatrix}d_{1}&d_{2}&\ldots&d_{m}\end{bmatrix}.$

The dimension of a linear subspace $L\subseteq\mathbb{R}^{n}$ is denoted by
$\dim(L)$. A _trivial_ subspace $L\subset\mathbb{R}^{n}$ is a set of the form
$L=\\{\mathbf{0}_{n}\\}$ or $L=\emptyset.$ Similarly, a set $D$ in
$\mathbb{R}^{n}$ is said to be trivial if $D=\\{\mathbf{0}_{n}\\}$ or
$D=\emptyset.$ In this paper, the linear subspace considered are assumed to be
nontrivial.

We now focus on the key definitions studied in this paper. In the remaining of
this paper, the word linear may be omitted when discussing the notion of span,
subspace and basis. All these notions are defined for the linear case.

######  Definition 1 (span, positive span)

Let $D\subseteq\mathbb{R}^{n}$.

  1. i.

The span of $D$ is denoted by $\operatorname{span}(D)$ and defined by

$\operatorname{span}(D)=\left\\{x\in\mathbb{R}^{n}:x=\sum_{i=1}^{k}\alpha_{i}d_{i},k\in\operatorname{\mathbb{N}},d_{i}\in
D,\alpha_{i}\in\mathbb{R}\right\\}.$

  2. ii.

The positive span of $D$ is denoted by $\operatorname{pspan}(D)$ and defined
by

$\operatorname{pspan}(D)=\left\\{x\in\mathbb{R}^{n}:x=\sum_{i=1}^{k}\lambda_{i}d_{i},k\in\operatorname{\mathbb{N}},d_{i}\in
D,\lambda_{i}\geq 0\right\\}.$

Note that $\operatorname{span}(D)$ is always a linear subspace of
$\mathbb{R}^{n}.$ Moreover, $L$ is a linear subspace of $\mathbb{R}^{n}$ if
and only if $L=\operatorname{span}(L)$.

The _projection_ of a vector $v\in\mathbb{R}^{n}$ onto a linear subspace $L$
will be denoted by $\operatorname{Proj}_{L}v$. We will be particularly
interested in the projection onto $\operatorname{span}(D)$. For ease of
writing, we provide this with the special notation
$\operatorname{P}_{D}=\operatorname{Proj}_{\operatorname{span}(D)}$. In
Section 5, we shall make use of the well-known formula

$\operatorname{P}_{D}v=DD^{\dagger}v,$

where $D^{\dagger}$ denotes the _Moore–Penrose pseudoinverse of $D$_
(roman2007, , Chapter 7).

######  Definition 2 (spanning, positive spanning)

Let $D\subseteq\mathbb{R}^{n}$ and $L$ be a subspace of $\mathbb{R}^{n}$.

  1. i.

The set $D$ is said to be a _spanning set of $L,$_ or _spans $L$,_ if and only
if $\operatorname{span}(D)=L.$

  2. ii.

The set $D$ is said to be a _positive spanning set of $L,$_ or _positively
spans $L$,_ if and only if $\operatorname{pspan}(D)=L.$

It is easy to prove that, if $D$ (positively) spans $L$, then $D$ must be a
subset of $L$. Indeed, one always has

$D\subseteq\operatorname{pspan}(D)\subseteq\operatorname{span}(D).$

The term (positively) independent is used to mean that removing any vector
from the set changes the (positive) spanning properties of the set.

######  Definition 3 (independence, positive independence)

Let $D\subseteq\mathbb{R}^{n}$.

  1. i.

The set $D$ is said to be _dependent_ if and only if there exists a vector
$d\in D$ such that $d\in\operatorname{span}(D\setminus\\{d\\})$. Conversely,
$D$ is said to be _independent_ if and only if
$\operatorname{span}(D\setminus{\\{d\\}})\neq\operatorname{span}(D)$ for any
$d\in D$.

  2. ii.

The set $D$ is said to be _positively dependent_ if and only if there exists a
vector $d\in D$ such that $d\in\operatorname{pspan}(D\setminus\\{d\\})$.
Conversely, $D$ is said to be _positively independent_ if and only if
$\operatorname{pspan}(D\setminus{\\{d\\}})\neq\operatorname{pspan}(D)$ for any
$d\in D$.

Finally, we introduce the notion of a (positive) basis of a subspace.

######  Definition 4 (basis, positive basis)

Let $D\subseteq\mathbb{R}^{n}$ and $L$ be a subspace of $\mathbb{R}^{n}$.

  1. i.

The set $D$ is a _basis of $L$_ if and only if $D$ is independent with
$\operatorname{span}(D)=L.$

  2. ii.

The set $D$ is a _positive basis of $L$_ if and only if $D$ is positively
independent with $\operatorname{pspan}(D)=L.$

It is well known that if $D$ is a basis of $L$ then $|D|=\dim(L)$. It is shown
in (regis2016, , Cor. 2.4 & Thm 6.6) that the minimal cardinality of a
positive basis of a subspace $L$ is $\dim(L)+1$ and the maximal cardinality is
$2\dim(L).$ Positive bases of these sizes are called _minimal positive bases_
and _maximal positive bases_ (respectively). Positive bases with cardinality
strictly between $\dim(L)+1$ and $2\dim(L)$ are called _intermediate positive
bases_.

We end this section by recalling the definition of cosine measure and defining
the cosine measure relative to a subspace. The cosine measure is valuable tool
to quantify how well a set covers the space $\mathbb{R}^{n}.$ We will see that
the cosine measure relative to a subspace extends the value of this tool to
work with a subspace of $\mathbb{R}^{n}$. We begin with the definition of
cosine measure (as given in hare2023nicely ; regis2021 ) and the corresponding
cosine vector set (from hare2020deterministic ).

######  Definition 5 (cosine measure)

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty finite set of nonzero vectors.
The _cosine measure_ of $D$ is defined by

$\operatorname{cm}\left(D\right)\ =\
\min_{\begin{subarray}{c}u\,\in\,\mathbb{R}^{n}\\\
\|u\|=1\end{subarray}}\max_{d\,\in\,D}\frac{u^{\top}d}{\|d\|},$

and the _cosine vector set of $D$_, denoted by $\mathrm{cV}(D)$, is defined by

$\mathrm{cV}(D)\ =\ \underset{\begin{subarray}{c}u\,\in\,\mathbb{R}^{n}\\\
\|u\|=1\end{subarray}}{\operatorname{argmin}}\max_{d\,\in\,D}\frac{u^{\top}d}{\|d\|}.$

Note that the original definition of the cosine measure requires $D$ to be
finite. Another limitation of the cosine measure is that is it focuses on how
well the set covers the entire space $\mathbb{R}^{n}$. As a result, if $D$ is
a positive spanning set of a proper subspace, then the cosine measure will
always return $\operatorname{cm}\left(D\right)=0$ (Corollary 3 herein). To
address these limitations, we introduce the cosine measure relative to a
subspace, which provides information on how well a set covers a linear
subspace. Simultaneously, we define a corresponding cosine vector set and
allow for both concepts to be well-defined for infinite sets.

However, since an empty set, or the zero vector, provides no coverage of
$\mathbb{R}^{n}$, the cosine measure relative to a subspace is defined for
nonempty sets of nonzero vectors. If a set is empty, the cosine measure
(relative to a subspace) should be assumed to be undefined. If a set contains
the zero vector, then one should remove the vector and work with the remaining
set. If the remaining set is empty, then the result would again be undefined.

For the remainder of this paper we shall assume that the set $D$ is a nonempty
set of nonzero vectors.

######  Definition 6 (cosine measure relative to $L$)

Let $L\subseteq\mathbb{R}^{n}$ be a nontrivial linear subspace and let
$D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. The _cosine
measure of $D$ relative to $L$_ is denoted by $\operatorname{cm}_{L}(D)$ and
defined by

$\displaystyle\operatorname{cm}_{L}(D)\ =\
\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\sup_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{u^{\top}d}{\|d\|},$
(2)

and the _cosine vector set of $D$ relative to $L$_, denoted by
$\mathrm{cV}_{L}(D)$, is defined by

$\mathrm{cV}_{L}(D)\ =\ \underset{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}{\operatorname{argmin}}\sup_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{u^{\top}d}{\|d\|}.$

If $L=\mathbb{R}^{n}$ and $|D|$ is finite, then the cosine measure relative to
$L$ returns the classical cosine measure:
$\operatorname{cm}_{\mathbb{R}^{n}}(\cdot)=\operatorname{cm}\left(\cdot\right)$.
Indeed, if $D$ is finite, then the $\sup$ can be replaced by $\max$ in (2). If
$D$ is a trivial set or if $L$ is a trivial subspace of $\mathbb{R}^{n},$ then
the cosine measure and cosine vector set (relative to $L$) are undefined. When
$D$ is a nonempty set of nonzero vectors and $L$ is a nontrivial subspace, the
cosine measure relative to a subspace returns a value in $[-1,1]$. Besides,
the cosine vector set of $D$ relative to $L$ is well-defined and nonempty.
Notice that when $D$ is an infinite set, then the cosine vector set may be
infinite.

###### Remark 1

Given a nonempty set of nonzero vectors $D$ and a nontrivial linear subspace
$L$ in $\mathbb{R}^{n}$ such that $D\not\subseteq L,$ one might consider
projecting each normalized vector $d/\|d\|\in D$ onto $L$ before computing the
cosine measure of $D$ relative to $L.$ Denote by $\widetilde{D}$ the set
obtained from these projections and by $\widetilde{d}$ a vector in the set
$\widetilde{D}$. Note that the set $\widetilde{D}$ might contain the zero
vector. If the computations are done using the projected set $\widetilde{D},$
then it is crucial to keep the zero vector in the set $\widetilde{D}.$ The
cosine measure of $D$ relative to $L$ can be computed as follows whenever we
work from the projected set $\widetilde{D}$ rather than using the original set
$D$:

$\displaystyle\operatorname{cm}_{L}(D)$
$\displaystyle=\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\sup_{d\,\in\,D}\frac{u^{\top}d}{\|d\|}$
$\displaystyle=\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\sup_{d\,\in\,D}u^{\top}\left(\operatorname{Proj}_{L}\frac{d}{\|d\|}+\left(\frac{d}{\|d\|}-\operatorname{Proj}_{L}\frac{d}{\|d\|}\right)\right)$
$\displaystyle=\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\sup_{\widetilde{d}\,\in\,\widetilde{D}}u^{\top}\widetilde{d},$
(3)

as
$u^{\top}\left(\frac{d}{\|d\|}-\operatorname{Proj}_{L}\frac{d}{\|d\|}\right)=0$
for any $u\in L$.

The following example shows the importance of keeping the zero vector in the
projected set $\widetilde{D}$ if the computations are done from the projected
set $\widetilde{D}.$

###### Example 1

Let $D=\\{e_{1},e_{2}\\}\subseteq\mathbb{R}^{2}$ and
$L=\\{x\in\mathbb{R}^{2}:x_{2}=0\\}.$ Then

$\operatorname{cm}_{L}(D)\ =\ 0.$

The projection of $e_{1}$ onto $L$ is equal to $e_{1}$ and the projection of
$e_{2}$ onto $L$ is equal to $\mathbf{0}.$ We obtain the projected set
$\widetilde{D}=\\{e_{1},\mathbf{0}\\}.$ Computing the cosine measure of $D$
relative $L$ as defined in Equation (3), we obtain
$\operatorname{cm}_{L}(D)=0.$ However, if one removes the zero vector from
$\widetilde{D},$ the final result would be

$\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\sup_{\widetilde{d}\,\in\,\widetilde{D}\setminus\\{\mathbf{0}\\}}u^{\top}\widetilde{d}\
=\ -1\ \neq\ \operatorname{cm}_{L}(D).$

We shall often be interested in the special case when
$L=\operatorname{span}(D)$. For ease of writing, when the linear subspace
considered is the span of a set, we only write the set name and omit the word
span in the subscript. More precisely,

$\operatorname{cm}_{D}(\cdot)=\operatorname{cm}_{\operatorname{span}(D)}(\cdot)\quad\mbox{and}\quad\operatorname{cV}_{D}(\cdot)=\mathrm{cV}_{\operatorname{span}(D)}(\cdot).$

Finally, some analysis will require examining the active set of the cosine
measure relative to $L$.

######  Definition 7 (active set)

Let $L\subseteq\mathbb{R}^{n}$ be a nontrivial linear subspace and
$D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors.

The _active set for $D$ at a cosine vector $u\in\mathrm{cV}_{L}(D)$ relative
to $L$_ is denoted by $\operatorname{\mathcal{A}}_{L}(D,u)$ and defined by

$\operatorname{\mathcal{A}}_{L}(D,u)\ =\ \left\\{d\in
D\,:\,\frac{d^{\top}u}{\|d\|}=\operatorname{cm}_{L}(D)\right\\}.$

The _active set for $D$ relative to $L$_ is denoted by
$\overline{\operatorname{\mathcal{A}}}_{L}(D)$, and defined by

$\overline{\operatorname{\mathcal{A}}}_{L}(D)\ =\
\bigcup_{u\,\in\,\mathrm{cV}_{L}(D)}\operatorname{\mathcal{A}}_{L}(D,u).$

As above, we are mostly interested in the special case of
$L=\operatorname{span}(D)$. For this case we use the special notation

$\operatorname{\mathcal{A}}_{D}(\cdot,\cdot)=\operatorname{\mathcal{A}}_{\operatorname{span}(D)}(\cdot,\cdot).$

##  3 Properties of a positive spanning set of a linear subspace

In this section, properties of positive spanning sets of a linear subspace are
investigated. The results are developed to consider both the cases where $|D|$
is finite and $|D|$ is infinite. We begin by showing that a set $D$ contained
in a linear subspace $L$ is a positive spanning set of $L$ if and only if
$\operatorname{pspan}(D)=\operatorname{span}(D)=L.$

###### Lemma 1

Let $L\subseteq\mathbb{R}^{n}$ be a linear subspace. Then $D$ positively spans
$L$ if and only if $\operatorname{pspan}(D)=\operatorname{span}(D)=L.$

###### Proof

($\Rightarrow$) Suppose that $D$ positively spans $L$; i.e.,
$\operatorname{pspan}(D)=L$. This implies $D\subseteq L$ and therefore
$\operatorname{pspan}(D)\subseteq\operatorname{span}(D)\subseteq
L=\operatorname{pspan}(D)$.
$(\Leftarrow)$ Conversely, if
$\operatorname{pspan}(D)=\operatorname{span}(D)=L$, then $D$ positively spans
$L$ by definition.∎

We next show that if $|D|$ is infinity and the positive span is a linear
subspace, then the positive span can be created through a finite subset of
$D$. We use the following lemma.

###### Lemma 2

(Brown1988, , Theorem 2.11) Let $D\subseteq\mathbb{R}^{n}$ be a nonempty
(possibly infinite) set of nonzero vectors. Then $D$ contains a basis of
$\operatorname{span}(D)$.

###### Corollary 1

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors and $L$ be a linear subspace of $\mathbb{R}^{n}$. If
$\operatorname{pspan}(D)=L$, then there exists a finite subset of vectors
$C\subseteq D$ such that $\operatorname{pspan}(C)=L$.

###### Proof

If $D$ is a finite set, then take $C=D.$

Suppose $D$ is an infinite set and $\dim(L)\geq 1$. By Lemma 1,
$\operatorname{pspan}(D)=L$ implies $L=\operatorname{span}(D)$. By Lemma 2,
the set $D$ contains a basis of $\operatorname{span}(D)$. Denote this basis by
$B=\left\\{b_{1},b_{2},\ldots,b_{m}\right\\}$ where
$m=\dim(\operatorname{span}(D))$. Define $v=-\sum_{i=1}^{m}b_{i}.$ Since
$\operatorname{pspan}(D)=\operatorname{span}(D)$, the vector $v$ can be
written as

$v=\alpha_{1}d_{1}+d_{2}+\dots+\alpha_{k}d_{k}$

where $d_{i}\in D$ and $k$ is an integer greater or equal than 1. Since the
$\operatorname{pspan}(B\cup\\{v\\})=\operatorname{span}(D)$ (regis2016, ,
Theorem 5.1), we have

$\operatorname{pspan}(B\cup\left\\{d_{1},d_{2}\ldots,d_{k}\right\\})=\operatorname{pspan}(B\cup\\{v\\})=\operatorname{span}(D)=L.$

The set $B\cup\left\\{d_{1},d_{2}\ldots,d_{k}\right\\}$ is finite, so the
proof is complete. ∎

Note that the above result requires $D$ to be a positive spanning set. Indeed,
consider the floating ring set defined by
$D=\\{x\in\mathbb{R}^{3}:(x_{1})^{2}+(x_{2})^{2}=1,x_{3}=1\\}.$ It can be
shown that the set $D$ is positively independent hare2016cardinality . As
such, for any finite subset $C\subseteq D,$ we have
$\operatorname{pspan}(C)\neq\operatorname{pspan}(D).$

This inspires the following result about positive independence for an infinite
set of vectors.

###### Corollary 2

Let $D\subseteq\mathbb{R}^{n}$ be an infinite set of vectors. If $D$ is
positively independent, then
$\operatorname{pspan}(D)\neq\operatorname{span}(D).$

###### Proof

Let $E$ be a finite subset of $D$ with
$\operatorname{pspan}(E)=\operatorname{span}(D)$. If $D$ is positively
independent, then $\operatorname{pspan}(D)=\operatorname{pspan}(E)$ creates a
contradiction.∎

Notice that Corollary 2 is specific to infinite sets. Indeed, a finite set of
positively independent vectors $D$ such that
$\operatorname{pspan}(D)=\operatorname{span}(D)$ is a positive basis.

We now extend (regis2016, , Theorem 2.5) to the cases of infinite sets.

###### Theorem 3.1

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors. Then the following are equivalent.

  1. (i)

The set $D$ is a positive spanning set of $\operatorname{span}(D).$

  2. (ii)

For any $d\in D$, $-d$ is in $\operatorname{pspan}(D\setminus\\{d\\})$.

Moreover, these imply that there exists a finite subset $C\subseteq D$ such
that $\operatorname{pspan}(C)=\operatorname{pspan}(D)$.

Suppose $C$ is a finite subset of $D$ such that
$\operatorname{pspan}(C)=\operatorname{pspan}(D)$ (if $D$ is finite, then
$C=D$). Let $s=|C|\geq 1$. Then the following are equivalent.

  1. (iii)

The set $D$ is a positive spanning set of $\operatorname{span}(D).$

  2. (iv)

The set $C$ is a positive spanning set of $\operatorname{span}(D).$

  3. (v)

There exists $\alpha\in\mathbb{R}^{s}$, such that $\alpha>0$ and
$C\alpha=\mathbf{0}_{n}$.

  4. (vi)

There exists $\beta\in\mathbb{R}^{s}$, such that $\beta\geq 1$ and
$C\beta=\mathbf{0}_{n}$.

  5. (vii)

There exists $\gamma\in\mathbb{R}^{s}$ such that $\gamma\geq 0$ and
$C\gamma=-C\mathbf{1}_{s}$.

where items (v), (vi), and (vii), interpret $C$ as a matrix in
$\mathbb{R}^{n\times s}$.

###### Proof

Parts (i) and (ii) are equivalent by (regis2016, , Theorem 2.5). Suppose that
$D$ is a positive spanning set of $\operatorname{span}(D)$. By Corollary 1,
part (i) implies that there exists a finite subset $C\subseteq D$ such that
$\operatorname{pspan}(C)=\operatorname{span}(D).$ The proof of equivalence of
parts (iii) to (vii) is identical to the proof for finite sets provided in
(regis2016, , Theorem 2.5). ∎

Our next example shows the importance of
$\operatorname{pspan}(C)=\operatorname{pspan}(D)$ in the second half of
Theorem 3.1.

###### Example 2

Consider $D_{\infty}=\\{d:\|d\|=1,d_{1}\geq 0\\}\subseteq\mathbb{R}^{2}$. The
set $C=\\{e_{2},-e_{2}\\}$ is contained in $D_{\infty}$, but
$\operatorname{pspan}(C)\neq\operatorname{pspan}(D_{\infty})$. Notice that $C$
satisfies parts (v), (vi), and (vii) of Theorem 3.1, but $C$ is not a positive
spanning set of $\operatorname{span}(D_{\infty})$.

In practice, Theorem 3.1(vii) is useful to decide if a given set is a positive
spanning set. Theorem 3.1(vii) can also be used to show how to extend a set
that is not a positive spanning set into a positive spanning set by adding
only one vector.

###### Proposition 1

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors. Suppose $\operatorname{pspan}(D)\neq\operatorname{span}(D)$.
Let $m=\dim(\operatorname{span}(D))$ and $B=\\{b_{1},\cdots,b_{m}\\}\subseteq
D$ be a basis of $\operatorname{span}(D)$. Define the vector
$w=-\sum_{j=1}^{m}b_{j}.$ Then

  1. (i)

the set $D^{\prime}=D\cup\\{w\\}$ is a positive spanning set of
$\operatorname{span}(D)$, and

  2. (ii)

the set $D^{\prime\prime}=D\cup-B$ is a positive spanning set of
$\operatorname{span}(D)$.

###### Proof

(i) Let $C=B\cup\\{w\\}$. By (audet2017derivative, , Thm 6.4),
$\operatorname{pspan}(C)=\operatorname{span}(B)=\operatorname{span}(D)$. We
also have that the sum of the vectors of $C$ is the null vector. Therefore,
Theorem 3.1(v) ensures that
$\operatorname{pspan}(D^{\prime})=\operatorname{span}(D)$.
(ii) The result follows similarly using $C=B\cup(-B)$. ∎

One of the most useful properties of a positive spanning set of
$\mathbb{R}^{n}$ is that for any nonzero vector $v\in\mathbb{R}^{n},$ there
exists a vector $d$ in the positive spanning set for which

$\displaystyle v^{\top}d$ $\displaystyle>0.$

It follows that given $f\in\mathcal{C}^{1}$, a positive spanning set of
$\mathbb{R}^{n}$ contains a descent direction of $f$ at any point
$x^{0}\in\mathbb{R}^{n}$ where $\nabla f(x^{0})\neq\mathbf{0}_{n}.$ This
result can be generalized to the linear subspaces and infinite sets. To do
this, we apply the following lemma.

###### Lemma 3

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors. If $\operatorname{pspan}(D)\neq\operatorname{span}(D),$ then
all the vectors in $D$ are contained in a closed half-space of
$\operatorname{span}(D).$

###### Proof

Follows immediately from (rockafellar1970, , Corollary 11.7.3). ∎

###### Proposition 2

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors. Then $\operatorname{pspan}(D)=\operatorname{span}(D)$ if and
only if for any nonzero vector $v\in\operatorname{span}(D)$ there exists a
vector $d\in D$ such that

$v^{\top}d>0.$ (4)

###### Proof

($\Rightarrow$) Suppose $\operatorname{pspan}(D)=\operatorname{span}(D)$. Let
$v$ be a nonzero vector in $\operatorname{span}(D)$. As
$v\in\operatorname{pspan}(D)$, $v$ can be written as

$v=\alpha_{1}d_{1}+\alpha_{2}d_{2}+\dots+\alpha_{m}d_{m},$

where $\alpha_{j}\geq 0$ for all $j\in\\{1,2,\ldots,m\\}.$ It follows that

$0<v^{\top}v=\alpha_{1}d_{1}^{\top}v+\alpha_{2}d_{2}^{\top}v+\dots+\alpha_{m}d_{m}^{\top}v.$

Hence, we must have $d_{j}^{\top}v>0$ for at least one
$j\in\\{1,2,\ldots,m\\}.$
($\Leftarrow$) Conversely, suppose that given any
$v\in\operatorname{span}(D)\setminus\\{\mathbf{0}_{n}\\}$ there exists a $d\in
D$ such that $v^{\top}d>0$. If
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$, then by Lemma 3 there
exists $h\in\operatorname{span}(D)\setminus\\{\mathbf{0}_{n}\\}$ such that all
vectors in $D$ are contained in $\\{w\in\operatorname{span}(D):w^{\top}h\leq
0\\}$. This leads to a contradiction by taking $v=h$. ∎

In Proposition 2, if we let the nonzero vector $v$ be in $\mathbb{R}^{n}$
rather than $\operatorname{span}(D),$ then the result does not necessarily
hold. The forward direction is true if we replace the strict inequality in (4)
by an inequality. Proposition 3 provides a proof of this claim.

###### Proposition 3

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty (possibly infinite) set of
nonzero vectors. If $\operatorname{pspan}(D)=\operatorname{span}(D)$, then for
any vector $v\in\mathbb{R}^{n},$ there exists a vector $d\in D$ such that

$v^{\top}d\geq 0.$

###### Proof

Let $v\in\mathbb{R}^{n}$ and note that
$v^{\top}d=(\operatorname{P}_{D}v)^{\top}d$ for all $d\in D$. If
$\operatorname{P}_{D}v=\mathbf{0}_{n}$, then $v^{\top}d=0$ for all $d\in D$.
If $\operatorname{P}_{D}v\neq\mathbf{0}_{n},$ then by Proposition 2 there
exists $d\in D$ such that $(\operatorname{P}_{D}v)^{\top}d>0.$ ∎

The converse of Proposition 3 is not necessarily true. For example, consider
the set $D=\\{e_{1},-e_{1},e_{2}\\}\subseteq\mathbb{R}^{2}$. For this set, for
any vector $v\in\mathbb{R}^{2}$, there exists $d\in D$ such that
$v^{\top}d\geq 0$, however
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$.

In the next section, the notion of cosine measure relative to a linear
subspace is investigated.

##  4 Cosine measure relative to a subspace

Definition 6 extends the definition of the cosine measure to include the idea
of a cosine measure relative to a subspace. In this section we explore the
basic properties of this new definition. As we are most interested in the
cosine measure relative to $\operatorname{span}(D)$, many results focus on
$\operatorname{cm}_{D}(D)$.

Since the definition of the cosine measure assumes $D$ is finite, results
involving the cosine measure include the assumptions that $D$ in finite.

We begin with the obvious relationship between the cosine measure and the
cosine measure relative to a subspace.

###### Proposition 4

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty finite set of nonzero vectors,
$L$ be a nontrivial linear subspace of $\mathbb{R}^{n}$. Then

$\operatorname{cm}(D)\leq\operatorname{cm}_{L}(D)$

with equality if and only if $\mathrm{cV}(D)\cap L\neq\emptyset$.

###### Proof

Since $L$ is a nontrivial subspace of $\mathbb{R}^{n}$, the definitions of the
cosine measures ensure that

$\displaystyle\operatorname{cm}(D)\ =\
\min_{\begin{subarray}{c}u\,\in\,\mathbb{R}^{n}\\\
\|u\|=1\end{subarray}}\max_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{u^{\top}d}{\|d\|}\
\leq\ \min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\max_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{u^{\top}d}{\|d\|}\
=\ \operatorname{cm}_{L}(D).$

Now, suppose $\operatorname{cm}(D)=\operatorname{cm}_{L}(D).$ Let
$u^{*}\in\mathrm{cV}_{L}(D).$ Then $u^{*}$ must be in $\mathrm{cV}(D)$, so
$\mathrm{cV}\cap L\neq\emptyset.$ Conversely, suppose $\mathrm{cV}(D)\cap
L\neq\emptyset.$ Let $u^{\\#}\in\mathrm{cV}(D)\cap L.$ Then

$\displaystyle\operatorname{cm}(D)\ =\
\max_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{(u^{\\#})^{\top}d}{\|d\|}\geq\
\min_{\begin{subarray}{c}u\,\in\,L\\\
\|u\|=1\end{subarray}}\max_{\begin{subarray}{c}d\,\in\,D\end{subarray}}\frac{u^{\top}d}{\|d\|}\
=\ \operatorname{cm}_{L}(D).$

Since $\operatorname{cm}(D)\leq\operatorname{cm}_{L}(D)$, we must have
$\operatorname{cm}(D)=\operatorname{cm}_{L}(D).$ ∎

###  4.1 Relating $\operatorname{pspan}(D)$ and $\operatorname{cm}_{D}(D)$

We now turn our attention to how the cosine measure relative to a subspace
provides knowledge about positive spanning properties. We begin with an
example computing the cosine measure relative to a subspace. We will return to
this example after each result to illustrate what the information the cosine
measure relative to a subspace provides. In the following example, it is
relatively easy to find the exact value of the cosine measure relative to a
subspace since the subspaces considered are either one dimensional or two
dimensionals. A deterministic algorithm will be provided in Section 5.

###### Example 3

Consider the sets of directions
$D_{1}=\\{e_{1},-e_{1},e_{2},-e_{2}\\}\subseteq\mathbb{R}^{3}$ and
$D_{2}=\\{e_{1},-e_{1},e_{2}\\}\subseteq\mathbb{R}^{3}$ and the subspaces
$L=\\{x\in\mathbb{R}^{3}:4x_{1}=3x_{2},x_{3}=0\\}$ and
$M=\\{x\in\mathbb{R}^{3}:x_{1}=x_{3}=0\\}$. First, note that

$\begin{array}[]{rll}&\qquad\operatorname{cm}\left(D_{1}\right)=0,&\qquad\mathrm{cV}(D_{1})=\\{e_{3},-e_{3}\\}\\\
\text{and}&\qquad\operatorname{cm}\left(D_{2}\right)=0,&\qquad\mathrm{cV}(D_{2})=\\{v=(0,v_{2},v_{3})\,:\,\|v\|=1,\,v_{2}\leq
0\\}.\end{array}$

The shaded regions in Figure 1 represent the positive span of $D_{1}$ on the
left and of $D_{2}$ on the right. Both figures also show the subspaces $L$ and
$M$.

ML${}^{\operatorname{pspan}(D_{1})}$$-e_{1}$$e_{1}$$e_{2}$$-e_{2}$

ML${}^{\operatorname{pspan}(D_{2})}$$-e_{1}$$e_{1}$$e_{2}$

Figure 1: Illustrations of the positive spans of $D_{1}$ and $D_{2}$

There are exactly two unit vectors in $L$:

$u^{1}=\begin{bmatrix}0.6\\\ 0.8\\\ 0\end{bmatrix}\quad\mbox{and}\quad
u^{2}=\begin{bmatrix}-0.6\\\ -0.8\\\ 0\end{bmatrix}.$

The cosine measures and cosine vectors relative to the subspace $L$ are

$\begin{array}[]{rll}&\qquad\operatorname{cm}_{L}(D_{1})\ =\
\min\left\\{\displaystyle\max_{d\in
D_{1}}u^{\top}d\,:\,u\in\\{u^{1},u^{2}\\}\right\\}\ =\
0.8,&\qquad\mathrm{cV}_{L}(D_{1})\ =\ \\{u^{1},u^{2}\\}\\\
\text{and}&\qquad\operatorname{cm}_{L}(D_{2})\ =\
\min\left\\{\displaystyle\max_{d\in
D_{2}}u^{\top}d\,:\,u\in\\{u^{1},u^{2}\\}\right\\}\ =\
0.6,&\qquad\mathrm{cV}_{M}(D_{2})\ =\ \\{u^{2}\\}.\end{array}$

In the subspace $M,$ there are exactly two unit vectors: $e_{2}$ and $-e_{2}.$
We obtain

$\begin{array}[]{rll}&\qquad\operatorname{cm}_{M}(D_{1})\ =\
\min\left\\{\displaystyle\max_{d\in
D_{1}}u^{\top}d\,:\,u\in\\{e_{2},-e_{2}\\}\right\\}\ =\
1,&\qquad\mathrm{cV}_{L}(D_{1})\ =\ \\{e_{2},-e_{2}\\}\\\
\text{and}&\qquad\operatorname{cm}_{M}(D_{2})\ =\
\min\left\\{\displaystyle\max_{d\in
D_{2}}u^{\top}d\,:\,u\in\\{e_{2},-e_{2}\\}\right\\}\ =\
0,&\qquad\mathrm{cV}_{M}(D_{2})\ =\ \\{-e_{2}\\}.\end{array}$

Considering the subspaces $\operatorname{span}(D_{1})$ and
$\operatorname{span}(D_{2}),$ we find

$\begin{array}[]{rll}&\qquad\operatorname{cm}_{D_{1}}(D_{1})=1/\sqrt{2},&\qquad\mathrm{cV}_{D_{1}}(D_{1})\
=\ \\{(v_{1},v_{2},0)\,:\,|v_{1}|=|v_{2}|=1/\sqrt{2}\\}\\\
\text{and}&\qquad\operatorname{cm}_{D_{2}}(D_{2})=0,&\qquad\mathrm{cV}_{D_{2}}(D_{2})\
=\ \\{-e_{2}\\}.\\\ \end{array}$

Given a nontrivial finite set $D\subseteq\mathbb{R}^{n},$ it is known that
$\operatorname{cm}(D)>0$ if and only if $D$ positively spans $\mathbb{R}^{n}$
(regis2021, , Theorem 4.2). Note that since
$\operatorname{pspan}(D)\subseteq\operatorname{span}(D)$, the previous result
can be expressed as follows: given a nontrivial finite set
$D\subseteq\mathbb{R}^{n},$ we have $\operatorname{cm}(D)>0$ if and only if
$\operatorname{pspan}(D)=\operatorname{span}(D).$ Thus, neither $D_{1}$ nor
$D_{2}$ in Example 3 is a positive spanning set of $\mathbb{R}^{3}$. The
cosine measure provides no further information.

The next proposition shows the ability of the cosine measure relative to a
subspace to detect if the subspace is contained in the positive span of $D$.

###### Proposition 5

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors and
$L\subseteq\operatorname{span}(D)$ be a nontrivial linear subspace. Then
$L\subseteq\operatorname{pspan}(D)$ if and only if
$\operatorname{cm}_{L}(D)>0.$ In particular,
$\operatorname{pspan}(D)=\operatorname{span}(D)$ if and only if
$\operatorname{cm}_{D}(D)>0$.

###### Proof

($\Rightarrow$) Suppose $L\subseteq\operatorname{pspan}(D)$. Let
$u^{*}\in\mathrm{cV}_{L}(D)$. Since $u^{*}\in L$, we have that $u^{*}$ can be
expressed as $u^{*}=\alpha_{1}d_{1}+\alpha_{2}d_{2}+\dots+\alpha_{m}d_{m},$
where $\alpha_{j}\geq 0$ for all $j\in\\{1,2,\ldots,m\\}.$ Similar to
Proposition 2,
$1=(u^{*})^{\top}u^{*}=\alpha_{1}d_{1}^{\top}u^{*}+\alpha_{2}d_{2}^{\top}u^{*}+\dots+\alpha_{m}d_{m}^{\top}u^{*}$
implies $d_{j}^{\top}v>0$ for at least one $j\in\\{1,2,\ldots,m\\}.$ Thus
$\operatorname{cm}_{L}(D)>0$.

($\Leftarrow$) Conversely, suppose $\operatorname{cm}_{L}(D)>0$. This implies
that given any $v\in L$ with $\|v\|=1$ there exists $d\in D$ such that
$v^{\top}d>0$. If $L$ is not a subset of $\operatorname{pspan}(D)$, then
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$, so applying Lemma 1 in
the same manner as Proposition 2 leads to the same contradiction. Thus
$L\subseteq\operatorname{pspan}(D)$.

The final statement comes from setting $L=\operatorname{span}(D)$. ∎

In Example 3, $\operatorname{cm}_{L}(D_{1})>0,\operatorname{cm}_{L}(D_{2})>0$,
$\operatorname{cm}_{M}(D_{1})>0$; thus
$L\subseteq\operatorname{pspan}(D_{1})$,
$L\subseteq\operatorname{pspan}(D_{2})$, and
$M\subseteq\operatorname{pspan}(D_{1})$. Also,
$\operatorname{cm}_{D_{1}}(D_{1})>0$, so
$\operatorname{pspan}(D_{1})=\operatorname{span}(D_{1})$. However,
$\operatorname{cm}_{M}(D_{2})\leq 0$, so $M$ is not a subspace of
$\operatorname{pspan}(D_{2})$. Also, $\operatorname{cm}_{D_{2}}(D_{2})=0$, so
$\operatorname{pspan}(D_{2})\neq\operatorname{span}(D_{2})$.

Next we prove the claim in the introduction: “if $D$ is a positive spanning
set of a proper subspace, then the cosine measure will always return $0$”.

###### Corollary 3

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty finite set of nonzero vectors.
Suppose $\operatorname{span}(D)\neq\mathbb{R}^{n}$. If
$\operatorname{pspan}(D)=\operatorname{span}(D)$, then
$\operatorname{cm}(D)=0$.

###### Proof

Select any $v\in\mathbb{R}^{n}$ with $\|v\|=1$. Let
$v_{D}=\operatorname{P}_{D}v$ and $v_{D^{\perp}}=v-v_{D}$. Since
$\operatorname{pspan}(D)=\operatorname{span}(D)$, Proposition 5 implies
$\operatorname{cm}_{D}(D)>0$, which further implies

$\max_{d\,\in\,D}\frac{(v_{D})^{\top}d}{\|d\|}\ \geq\ 0,$

with equality only if $v_{D}=\mathbf{0}_{n}$. Since $v_{D^{\perp}}$ is in the
orthogonal subspace to $D$, $(v_{D^{\perp}})^{\top}d=0$ for all $d\in D$.
Thus,

$\max_{d\,\in\,D}\frac{(v)^{\top}d}{\|d\|}\ =\
\max_{d\,\in\,D}\frac{(v_{D})^{\top}d}{\|d\|}+\max_{d\,\in
D}\frac{(v_{D^{\perp}})^{\top}d}{\|d\|}\ \geq\ 0,$

with equality only if $v_{D}=\mathbf{0}_{n}$. Selecting $v$ to be in the
orthogonal subspace to $\operatorname{span}(D)$ now demonstrates
$\operatorname{cm}(D)=0$. ∎

In Example 3, $\operatorname{span}(D_{1})\neq\mathbb{R}^{3}$ and
$\operatorname{cm}(D_{1})=0$, so Corollary 3 allows for the possibility that
$\operatorname{pspan}(D_{1})=\operatorname{span}(D_{1})$. However, notice that
this is not sufficient to ensure that result, as $D_{2}$ in Example 3 also has
$\operatorname{cm}(D_{2})=0$, but
$\operatorname{pspan}(D_{2})\neq\operatorname{span}(D_{2})$. Hence, Corollary
3 cannot be made into an ‘if and only if’ statement.

The next theorem further investigates the relation between the value of the
cosine measure and the value of the cosine measure relative to the subspace
$\operatorname{span}(D).$

###### Theorem 4.1

Let $D$ be a nonempty finite set of nonzero vectors in $\mathbb{R}^{n}$. If
$\operatorname{cm}(D)\neq\operatorname{cm}_{D}(D),$ then
$\operatorname{pspan}(D)=\operatorname{span}(D)\neq\mathbb{R}^{n}$.

###### Proof

If $\operatorname{cm}(D)\neq\operatorname{cm}_{D}(D),$ then Proposition 4
using $L=\mathbb{R}^{n}$ implies that
$\operatorname{span}(D)\neq\mathbb{R}^{n}$.

For eventual contradiction, suppose
$\operatorname{cm}(D)\neq\operatorname{cm}_{D}(D)$ and
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$. From Proposition 4,
$\operatorname{cm}(D)\neq\operatorname{cm}_{D}(D)$ implies that
$\operatorname{cm}(D)<\operatorname{cm}_{D}(D)$. From Proposition 5,
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$ implies that
$\operatorname{cm}_{D}(D)\leq 0$. Hence, we have

$\displaystyle\operatorname{cm}(D)$
$\displaystyle<\operatorname{cm}_{D}(D)\leq 0.$ (5)

Let $v\in\mathrm{cV}(D)$ and notice that Proposition 4 implies
$v\notin\operatorname{span}(D)$. Let $v_{D}=\operatorname{P}_{D}v$ and notice
that $v^{\top}d=v_{D}^{\top}d$ for all $d\in D$. This implies that

$\operatorname{cm}(D)=\max_{d\,\in D}v^{\top}\frac{d}{\|d\|}=\max_{d\,\in
D}v_{D}^{\top}\frac{d}{\|d\|},$

which further implies $v_{D}\neq\mathbf{0}_{n}$. Define $\ell=\|v_{D}\|$.
Considering $v_{D}\in\operatorname{span}(D)$ and $\|\frac{1}{\ell}v_{D}\|=1$,
we obtain

$\operatorname{cm}_{D}(D)\leq\max_{d\,\in
D}\left(\frac{1}{\ell}v_{D}\right)^{\top}\frac{d}{\|d\|}=\frac{1}{\ell}\operatorname{cm}(D)\
<\ \operatorname{cm}(D),$

where the last inequality comes from $0<\ell<1$ and $\operatorname{cm}(D)<0$.
This contradicts inequality (5), so the initial supposition cannot hold.∎

Returning to Example 3, notice that
$\operatorname{cm}(D_{1})=\operatorname{cm}_{D_{1}}(D_{1})$, and indeed we
have
$\operatorname{span}(D_{1})=\operatorname{pspan}(D_{1})\neq\mathbb{R}^{3}$. In
Example 3, we find the
$\operatorname{cm}(D_{2})=\operatorname{cm}_{D_{2}}(D_{2})=0$, so Theorem 4.1
does not apply. In the next section, we explore what
$\operatorname{cm}_{D}(D)=0$ tells us about $D$.

###  4.2 Consequence of $\operatorname{cm}_{D}(D)=0$

In this section, we focus exclusively on properties of
$\operatorname{cm}_{D}(D)$. Since the results do not involve
$\operatorname{cm}(D),$ we no longer require the assumption that $D$ is a
finite set. However, for the sake of simplicity, we continue to assume that
$D$ is a nonempty set of nonzero vectors.

To explore the consequences of $\operatorname{cm}_{D}(D)=0$ we first begin by
examining the other extreme case: $\operatorname{cm}_{D}(D)=1$.

###### Proposition 6

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. Define
$U=\\{u\in\operatorname{span}(D):\|u\|=1\\}$ and
$\widehat{D}=\operatorname{cl}\\{d/\|d\|:d\in D\\}$, where $\operatorname{cl}$
denotes the closure of the set. Then the following are equivalent.

  1. (i)

$U=\widehat{D}$,

  2. (ii)

$\operatorname{cm}_{D}(D)=1$,

  3. (iii)

$\mathrm{cV}_{D}(D)=U$,

  4. (iv)

$\overline{\operatorname{\mathcal{A}}}_{D}(D)=U$.

###### Proof

Clearly (i) implies (ii), (iii), and (iv). Therefore we only need to show (ii)
implies (i).
Suppose $\operatorname{cm}_{D}(D)=1$. By construction, $\widehat{D}\subseteq
U$. Let $u^{*}\in U$. By definition of the cosine measure relative to
$\operatorname{span}(D)$,

$1=\operatorname{cm}_{D}(D)=\min_{u\,\in\,\operatorname{span}(D)\\\
\begin{subarray}{c}\|u\|=1\end{subarray}}\sup_{d\,\in
D}\frac{u^{\top}d}{\|d\|}=\min_{\begin{subarray}{c}u\,\in\,\operatorname{span}(D)\\\
\|u\|=1\end{subarray}}\sup_{\hat{d}\in\widehat{D}}u^{\top}\hat{d}\leq\sup_{\hat{d}\in\widehat{D}}(u^{*})^{\top}\hat{d}\leq\|u^{*}\|=1,$

where the last inequality is true by Cauchy–Schwarz. Moreover, the last
inequality is an equality if and only if $\hat{d}=u^{*}$. Since equality holds
across the above, this implies $u^{*}\in\widehat{D}$. Thus
$U\subseteq\widehat{D}$, which provides (i) and the proof is complete.∎

An important consequence of Proposition 6 is that if $|D|=2$, then either
$\operatorname{cm}_{D}(D)=1$ or $\operatorname{cm}_{D}(D)<0$.

###### Corollary 4

Let $D\subseteq\mathbb{R}^{n}$ be a set of nonzero vectors with exactly 2
vectors. Then either $\operatorname{cm}_{D}(D)=1$ or
$\operatorname{cm}_{D}(D)<0$.

###### Proof

Let $D=\\{d_{1},d_{2}\\}$. Set
$u=-\left(\frac{d_{1}}{\|d_{1}\|}+\frac{d_{2}}{\|d_{2}\|}\right)$. If
$u=\mathbf{0}_{n}$, then Proposition 6 creates
$\widehat{D}=\\{\frac{d_{1}}{\|d_{1}\|},-\frac{d_{1}}{\|d_{1}\|}\\}=U$, so
$\operatorname{cm}_{D}(D)=1$. If $u\neq\mathbf{0}_{n}$, then set
$u^{*}=u/\|u\|$ and notice

$\operatorname{cm}_{D}(D)\leq\max\left\\{\frac{(u^{*})^{\top}d_{1}}{\|d_{1}\|},\frac{(u^{*})^{\top}d_{2}}{\|d_{2}\|}\right\\}=\frac{1}{\|u\|}\left(-1-\frac{d_{1}^{\top}d_{2}}{\|d_{1}\|\|d_{2}\|}\right)<0.$

∎

We now begin our examination of the consequences of
$\operatorname{cm}_{D}(D)=0$. Our goal is to show that
$\operatorname{cm}_{D}(D)=0$ if and only if $D$ contains a finite nontrivial
subset that is a positive spanning. The proof is reductionist in nature and
uses the following lemma, which shows that if $\operatorname{cm}_{D}(D)=0$,
then there exists a subset $V\subseteq D$ that is strictly smaller than $D$
and has $\operatorname{cm}_{V}(V)\geq 0$.

###### Lemma 4

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. If
$\operatorname{cm}_{D}(D)=0$, then there exists a finite subset $V\subseteq D$
such that $1<|V|<|D|$ and $\operatorname{cm}_{V}(V)\geq 0$.

###### Proof

Let $u^{*}\in\mathrm{cV}_{D}(D)$. Define
$H=\\{v\in\operatorname{span}(D):(u^{*})^{\top}v=0\\}$ and $V=D\cap H$. Since
$\operatorname{cm}_{D}(D)=0$, by definition there exists at least one vector
in $V$.

If $|D|=|V|$, then $V=D$, which implies $(u^{*})^{\top}d=0$ for all $d\in D$.
This yields $(u^{*})^{\top}v=0$ for all $v\in\operatorname{span}(D)$, which
implies $u^{*}=\mathbf{0}_{n}$ contradicting $\|u^{*}\|=1$. Thus, $|V|<|D|$.

Finally, for eventual contradiction, suppose $\operatorname{cm}_{V}(V)<0$.
This implies that there exists $v^{*}\in\operatorname{span}(V)$ such that
$(v^{*})^{\top}d<0$ for all $d\in V$. For $\epsilon>0$, define

$u^{\prime}=u^{*}+\epsilon v^{*}\in\operatorname{span}(D).$

Given any $d\in V$, we have

$\displaystyle(u^{\prime})^{\top}d$ $\displaystyle=(u^{*}+\epsilon
v^{*})^{\top}d=(u^{*})^{\top}d+(\epsilon v^{*})^{\top}d<0,$

as $(u^{*})^{\top}d=0$ and $(\epsilon v^{*})^{\top}d<0$. Given $d\in
D\setminus V$, we have

$\displaystyle(u^{\prime})^{\top}d$ $\displaystyle=(u^{*})^{\top}d+(\epsilon
v^{*})^{\top}d\leq\max_{d\in D\setminus
V}\left(\|d\|\frac{(u^{*})^{\top}d}{\|d\|}\right)+(\epsilon v^{*})^{\top}d.$

Since $u^{*}\in\mathrm{cV}_{D}(D)$, we have

$\max_{d\in D\setminus V}\left(\|d\|\frac{(u^{*})^{\top}d}{\|d\|}\right)<0.$

Thus, for $\epsilon$ sufficiently small $(u^{\prime})^{\top}d<0$ for all $d\in
D$. The vector $u^{\prime}$ contradicts $\operatorname{cm}_{D}(D)=0$, and
therefore we must have $\operatorname{cm}_{V}(V)\geq 0$.

Finally, $|V|>1$, as if $|V|=1$, then $\operatorname{cm}_{V}(V)=-1$. If $V$ is
not finite, then apply Theorem 3.1 to reduce to a finite subset. ∎

We now present the main result for this subsection.

###### Theorem 4.2

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. Suppose
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$. Then
$\operatorname{cm}_{D}(D)=0$ if and only if $D$ contains a nonempty finite
proper subset $V$ such that $\operatorname{pspan}(V)=\operatorname{span}(V)$.

###### Proof

First, note that $\operatorname{pspan}(D)\neq\operatorname{span}(D)$ implies
$\operatorname{cm}_{D}(D)\leq 0$.

($\Leftarrow$) Suppose there exists a nonempty proper subset $V\subset D$ such
that $\operatorname{pspan}(V)=\operatorname{span}(V).$ Let
$u^{\ast}\in\mathrm{cV}_{D}(D)$ and define $u^{\ast}_{V}=P_{V}u^{\ast}$ and
$u^{\ast}_{V^{\perp}}=u^{\ast}-u^{\ast}_{V}$. Since $u^{\ast}_{V^{\perp}}$ is
in the orthogonal subspace to $V$, we have

$\sup_{d\,\in\,V}\frac{(u^{\ast})^{\top}v}{\|v\|}=\sup_{d\,\in\,V}\frac{(u_{V}^{\ast})^{\top}v}{\|v\|}\leq\sup_{d\,\in\,D}\frac{(u_{V}^{\ast})^{\top}d}{\|d\|}=\sup_{d\,\in
D}\frac{(u^{\ast})^{\top}d}{\|d\|}-\sup_{d\,\in
D}\frac{(u^{\ast}_{V^{\perp}})^{\top}d}{\|d\|}\leq\operatorname{cm}_{D}(D)\leq
0.$ (6)

If $u^{\ast}_{V}\neq\mathbf{0}_{n},$ then Proposition 2 would imply the
existence of $v\in V$ with $(u_{V}^{\ast})^{\top}v>0$, therefore equation (6)
implies that $u^{\ast}_{V}=\mathbf{0}_{n}$. Substituting
$u^{\ast}_{V}=\mathbf{0}_{n}$ in equation (6) shows
$\operatorname{cm}_{D}(D)=0$.

($\Rightarrow$) Suppose $\operatorname{cm}_{D}(D)=0$. Without loss of
generality, we assume $D$ is finite. (Indeed, if $D$ is not finite, then apply
Theorem 3.1 to drop to a finite set.) Let $m=|D|$. Note that $m\geq 3$, as
$|D|=1$ implies $\operatorname{cm}_{D}(D)=-1$ and $|D|=2$ implies
$\operatorname{cm}_{D}(D)=1$ or $\operatorname{cm}_{D}(D)<0$.

By Lemma 4, there exists a nonempty proper subset $D_{1}\subseteq D$ such that
$1<|D_{1}|<m$ and $\operatorname{cm}_{D_{1}}(D_{1})\geq 0$. If
$\operatorname{cm}_{D_{1}}(D_{1})>0$, then $V=D_{1}$ is our desired set. If
$\operatorname{cm}_{D_{1}}(D_{1})=0$, then $|D_{1}|>2$ and therefore we can
repeat the procedure as necessary to generate a nonempty proper subset
$D_{k}\subset D_{k-1}$ such that $2\leq|D_{k}|<|D_{k-1}|\leq m-k$ and
$\operatorname{cm}_{{D_{k}}}(D_{k})\geq 0$. This process must terminate before
$k=m-1$ or a contradiction is created. When the procedure is terminated we
have $\operatorname{cm}_{{D_{k}}}(D_{k})>0$, so $V=D_{k}$ is our desired set.
∎

The previous theorem can be adapted to the cosine measure of $D$ or
reformulated to discuss dimensions of subspaces.

###### Corollary 5

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors.

  1. (i)

Suppose $\operatorname{pspan}(D)\neq\mathbb{R}^{n}$. Then
$\operatorname{cm}(D)=0$ if and only if $D$ contains a nonempty proper subset
$V$ such that $\operatorname{pspan}(V)=\operatorname{span}(V)$.

  2. (ii)

Suppose $\operatorname{pspan}(D)\neq\operatorname{span}(D)$. Then
$\operatorname{cm}_{D}(D)=0$ if and only if $D$ contains a positive basis of a
linear subspace $L\subset\operatorname{span}(D)$ with
$1\leq\dim(L)<\dim(\operatorname{span}(D)).$

  3. (iii)

Suppose $\operatorname{pspan}(D)\neq\operatorname{span}(D)$. Then
$\operatorname{cm}_{D}(D)=0$ if and only if $D$ contains a minimal positive
basis of a linear subspace $L\subset\operatorname{span}(D)$ with
$1\leq\dim(L)<\dim(\operatorname{span}(D)).$

###### Proof

Item (i) is immediate from Theorem 4.2. Item (ii) results from rephrasing
Theorem 4.2 in terms of positive bases. Item (iii) follows from
(Romanowicz1987, , Theorem 1), where it is shown that a positive basis of a
linear subspace can be partitioned to minimal positive bases (Romanowicz1987,
, Theorem 1). ∎

###  4.3 Bounding the norm of the gradient in directional direct-search
methods

Directional methods such as the Generalized Pattern Search (GPS) Torczon1997
and the Mesh Adaptive Direct Search (MADS)Audet2006  algorithms are
foundational methods in derivative-free optimization audet2017derivative ;
CoScVibook . Their convergence rely on applying poll steps, evaluating
$f(x^{k}+d)$, $d\in D$ where $D$ is a positive basis for $\mathbb{R}^{n}$, to
seek improvement in the objective function. An important result is that in the
case of a failed poll step (i.e., $f(x^{k})\leq f(x^{k}+d)$ for all $d\in D$),
the cosine measure of $D$ combined with the radius of $D$ provides an error
bound on the gradient of $f$ (assuming $\nabla f$ is Lipschitz continuous). We
provide a formal statement below from CoScVibook , but recommend seeing
dolan2003 ; kolda2003  for alternate presentations.

Given the nature of directional direct-search algorithm, in this subsection we
continue to assume that $\mathbf{0}_{n}\notin D$.

###### Theorem 4.3

(CoScVibook, , Theorem 2.8) Let $D\subseteq\mathbb{R}^{n}$ be a nonempty
finite subset of nonzero vectors with radius $\Delta_{D}$. Let
$f:\operatorname{dom}f\subseteq\mathbb{R}^{n}\to\mathbb{R}$ and
$x^{0}\in\operatorname{dom}f$. Suppose $D$ positively spans $\mathbb{R}^{n}$
and $f(x^{0})\leq f(x^{0}+d)$ for all $d\in D.$ If $\nabla f$ is Lipschitz
continuous with constant $L_{\nabla f}\geq 0$ in an open set containing the
ball $B_{n}(x^{0};\Delta_{D})$, then

$\displaystyle\|\nabla f(x^{0})\|$ $\displaystyle\leq\frac{1}{2}L_{\nabla
f}\operatorname{cm}(D)^{-1}\Delta_{D}.$

We next present two extensions of this result. Theorem 4.4(i) directly extends
Theorem 4.3 to allow for subspaces and infinite sets. (Setting
$L=\mathbb{R}^{n}$ and $D$ finite in Theorem 4.4(i) reproduces Theorem 4.3.)
Theorem 4.4(ii) presents a new result, demonstrating a stronger error bound in
the situation where the set $D$ contains symmetry.

###### Theorem 4.4

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. Suppose
the radius of $D$ is finite $(0<\Delta_{D}<\infty)$. Let
$f:\operatorname{dom}f\subseteq\mathbb{R}^{n}\to\mathbb{R}$ and
$x^{0}\in\operatorname{dom}f$. In addition, suppose
$\operatorname{pspan}(D)=\operatorname{span}(D)$ and $f(x^{0})\leq f(x^{0}+d)$
for all $d\in D.$

  1. (i)

If $\nabla f$ is Lipschitz continuous with constant $L_{\nabla f}\geq 0$ in an
open set containing the ball $\overline{B}_{n}(x^{0};\Delta_{D})$, then

$\displaystyle\|\operatorname{P}_{D}\nabla f(x^{0})\|$
$\displaystyle\leq\frac{1}{2}L_{\nabla
f}\operatorname{cm}_{D}(D)^{-1}\Delta_{D}.$ (7)

  2. (ii)

Suppose in addition that for each $d\in D$ there exists $\alpha_{d}>0$ such
that $-\alpha_{d}d\in D$. If $\nabla^{2}f$ is Lipschitz continuous with
constant $L_{\nabla^{2}f}\geq 0$ in an open set containing the ball
$\overline{B}_{n}(x^{0};\Delta_{D})$, then

$\displaystyle\|\operatorname{P}_{D}\nabla f(x^{0})\|$
$\displaystyle\leq\frac{1}{3}\alpha_{\max}L_{\nabla^{2}f}\operatorname{cm}_{D}(D)^{-1}\Delta_{D}^{2},$
(8)

where $\alpha_{\max}=\sup_{d\in D}\\{\alpha_{d}\\}$.

###### Proof

(i) Let $v=-\operatorname{P}_{D}\nabla f(x^{0})$. If $v\neq\mathbf{0}_{n}$,
then by definition, we have

$\displaystyle\operatorname{cm}_{D}(D)$ $\displaystyle\leq\sup_{d\in
D}\frac{v^{\top}d}{\|v\|\|d\|}$

and therefore there exists a $d\in D$ such that

$\displaystyle\operatorname{cm}_{D}(D)\|v\|\|d\|$ $\displaystyle\leq
v^{\top}d.$

If $v=\mathbf{0}_{n}$, the above holds trivially. Therefore, there exists a
vector $d\in D$ such that

$\displaystyle\operatorname{cm}_{D}(D)\|\operatorname{P}_{D}\nabla
f(x^{0})\|\|d\|$ $\displaystyle\leq-\left(\operatorname{P}_{D}\nabla
f(x^{0})\right)^{\top}d.$ (9)

Applying Taylor’s Theorem and the assumption that $f(x^{0})-f(x^{0}+d)\leq 0$
for all $d\in D$, we have

$\displaystyle-\left(\operatorname{P}_{D}\nabla
f(x^{0})\right)^{\top}d=-\nabla f(x^{0})^{\top}d$
$\displaystyle=f(x^{0})-f(x^{0}+d)+R_{1}(x^{0};d)\leq R_{1}(x^{0};d)$ (10)

where $R_{1}$ is the first-order remainder term. Combining equations (9) and
(10), then noting that $|R_{1}(x^{0};d)|\leq\frac{1}{2}L_{\nabla f}\|d\|^{2}$,
yields

$\displaystyle\operatorname{cm}_{D}(D)\|\operatorname{P}_{D}\nabla
f(x^{0})\|\|d\|$ $\displaystyle\leq R_{1}(x^{0};d)\leq\frac{1}{2}L_{\nabla
f}\|d\|^{2}.$

Since $\operatorname{span}(D)=\operatorname{pspan}(D)$, we know that
$\operatorname{cm}_{D}(D)>0.$ Equation (7) follows using the fact
$\|d\|\leq\Delta_{D}$ for all $d\in D.$

(ii) Suppose that for each $d\in D$ there exists $\alpha_{d}>0$ such that
$-\alpha_{d}d\in D$ and let $\alpha_{\max}=\sup_{d\in D}\\{\alpha_{d}\\}$. If
$\alpha_{\max}=\infty$, then the result holds trivially, so we assume
$\alpha_{\max}<\infty$.

Taylor’s Theorem and the assumption that $f(x^{0})-f(x^{0}+d)\leq 0$ for all
$d\in D$, yields

$\displaystyle-\nabla f(x^{0})^{\top}d$
$\displaystyle=f(x^{0})-f(x^{0}+d)+\frac{1}{2}d^{\top}\nabla^{2}f(x^{0})d+R_{2}(x^{0};d),$
$\displaystyle-\nabla f(x^{0})^{\top}d$
$\displaystyle\leq\frac{1}{2}d^{\top}\nabla^{2}f(x)d+R_{2}(x^{0};d)$ (11)

and similarly,

$\displaystyle-\nabla f(x^{0})^{\top}(-\alpha_{d}d)$
$\displaystyle\leq\frac{\alpha_{d}^{2}}{2}d^{\top}\nabla^{2}f(x^{0})d+R_{2}(x^{0};-\alpha_{d}d),$
(12)

where $R_{2}$ is the second-order remainder term. Multiplying (11) by
$\alpha^{2}$ and subtracting (12), we get

$\displaystyle-(\alpha_{d}^{2}+\alpha_{d})\nabla
f(x^{0})^{\top}d=-(\alpha_{d}^{2}+\alpha_{d})\left(\operatorname{P}_{D}\nabla
f(x^{0})\right)^{\top}d\leq\alpha_{d}^{2}R_{2}(x^{0};d)-R_{2}(x^{0};-\alpha_{d}d)$
(13)

Therefore, combining equations (9) and (13), then noting that
$|R_{2}(x^{0};d)|\leq\frac{1}{6}L_{\nabla^{2}f}\|d\|^{3}$, we find

$\displaystyle(\alpha_{d}^{2}+\alpha_{d})\operatorname{cm}_{D}(D)\|\operatorname{P}_{D}\nabla
f(x^{0})\|\|d\|$
$\displaystyle\leq\alpha_{d}^{2}R_{2}(x^{0};d)-R_{2}(x^{0};-\alpha_{d}d)$
$\displaystyle\leq\alpha_{d}^{2}\frac{L_{\nabla^{2}f}}{6}\|d\|^{3}+\frac{L_{\nabla^{2}f}}{6}\|-\alpha_{d}d\|^{3}$
$\displaystyle\leq(\alpha_{d}^{2}+\alpha_{d}^{3})\frac{L_{\nabla^{2}f}}{3}\|d\|^{3}$

Using the bounds $\|d\|\leq\Delta_{D}$ and $\alpha_{d}\leq\alpha_{\max}$, we
obtain (8). ∎

Theorem 4.4 could be used in directional direct-search methods in several
different manners. One obvious example would be to use it to generate a
stopping condition, particularly in the case where
$\operatorname{span}(D)=\operatorname{pspan}(D)$. In the case of reduced
subspace methods where $\operatorname{span}(D)\neq\operatorname{pspan}(D)$,
Theorem 4.4 could be used to create flags indicating when it is time switch to
a different subspace.

While convergence of the directional direct-search methods requires the use of
positive spanning sets, it is easy to conceive of an implementation that does
not enforce positive spanning sets at every iteration. The following corollary
demonstrates how Theorem 4.4 might be used to help determine next steps in the
case of a failed poll step where $D$ is not a positive spanning set.

###### Corollary 6

Let $D\subseteq\mathbb{R}^{n}$ be a nonempty set of nonzero vectors. Suppose
the radius of $D$ is finite $(0<\Delta_{D}<\infty)$. Let
$f:\operatorname{dom}f\subseteq\mathbb{R}^{n}\to\mathbb{R}$ and
$x^{0}\in\operatorname{dom}f$. In addition, suppose
$\operatorname{pspan}(D)\neq\operatorname{span}(D)$ and $f(x^{0})\leq
f(x^{0}+d)$ for all $d\in D.$

Let $B=\\{d_{1},d_{2}\ldots,d_{m}\\}\subseteq D$ be a basis of
$\operatorname{span}(D)$. Define

$w=-\Delta_{D}\frac{\sum_{j=1}^{m}d_{j}}{\|\sum_{j=1}^{m}d_{j}\|},\quad
D^{\prime}=D\cup\\{w\\},\quad\mbox{and}\quad D^{\prime\prime}=D\cup-D.$

  1. (i)

If $\nabla f$ is Lipschitz continuous with constant $L_{\nabla f}\geq 0$ in an
open set containing the ball $\overline{B}_{n}(x^{0};\Delta_{D})$, then at
least one of the following holds:

$\displaystyle f(x^{0}+w)<f(x^{0})\quad\mbox{\em
or}\quad\|\operatorname{P}_{D}\nabla f(x^{0})\|$
$\displaystyle\leq\frac{1}{2}L_{\nabla
f}\operatorname{cm}_{D}(D^{\prime})^{-1}\Delta_{D}.$ (14)

  2. (ii)

If $\nabla^{2}f$ is Lipschitz continuous with constant $L_{\nabla^{2}f}\geq 0$
in an open set containing the ball $\overline{B}_{n}(x^{0};\Delta_{D})$, then
then at least one of the following holds

$\displaystyle f(x^{0}-d)<f(x^{0})\mbox{ for some }d\in D\quad\mbox{\em
or}\quad\|\operatorname{P}_{D}\nabla f(x^{0})\|$
$\displaystyle\leq\frac{1}{3}L_{\nabla^{2}f}\operatorname{cm}_{D}(D^{\prime\prime})^{-1}\Delta_{D}^{2}.$
(15)

###### Proof

(i) Suppose $f(x^{0})\leq f(x^{0}+w)$. By Proposition 1, $D^{\prime}$ is a
positive spanning set. The result follows from Theorem 4.4(i), noting that the
scaling of $w$ makes $\Delta_{D^{\prime}}=\Delta_{D}$.
(ii) Suppose $f(x^{0})\leq f(x^{0}-d)$ for all $d\in D$. By Proposition 1,
$D^{\prime\prime}$ is a positive spanning set. The result follows from Theorem
4.4, noting that $\Delta_{D^{\prime\prime}}=\Delta_{D}$ and $\alpha_{d}=1$ for
all $d\in D$. ∎

##  5 Computing the cosine measure relative to a subspace

Section 4 established the value of the cosine measure relative to a subspace.
In this section, we investigate how to compute $\operatorname{cm}_{D}(D)$ for
a nonempty finite set of nonzero vectors. In Example 3, we were able to
compute the cosine measure relative to a subspace since the subspace
considered were either 1-dimensional or 2-dimensional. In this section, we
provide a general deterministic algorithm to compute the cosine measure
relative to a subspace. Note that Algorithm 1 assumes $D$ is finite and
$\mathbf{0}_{n}\notin D$. Reasons for both are clear. If $D$ is infinite, then
we must confront the challenge of how to express the set in a manner suitable
for algorithmic use. If we allowed $\mathbf{0}_{n}\in D$, then the first step
of the algorithm would simply become remove $\mathbf{0}_{n}$ from $D$.

Algorithm 1 is a modification of the algorithm in hare2020deterministic  to
allow for subspaces and for the case where $D$ is not a positive spanning set.
To allow for the scenario where $D$ is not a positive spanning set, Algorithm
1 begins by checking if $\operatorname{pspan}(D)=\operatorname{span}(D)$.
Recall that this can be done by solving a linear program using Theorem
3.1(vii). Within the algorithm ps is used as a flag to store whether $D$ is a
positive spanning set (ps = 1) or not (ps = -1). This flag is used in line
(2.1) to control whether $\gamma_{B}$ is positive or negative. The notation
$\mathbf{G}(B)$ represents the _Gram matrix_ of $B$. That is
$\mathbf{G}(B)=B^{\top}B.$

Given a nonempty finite set $D$ of $q$ nonzero vectors in $\mathbb{R}^{n},$

0\. Normalize: set $D\leftarrow\\{d/\|d\|:d\in D\\}$.

1\. Determine if $\operatorname{pspan}(D)=\operatorname{span}(D)$ and define

$\begin{aligned} \quad(1.1)&\quad{\tt
ps}=\left\\{\begin{array}[]{rl}1,&\mbox{if}~{}\operatorname{pspan}(D)=\operatorname{span}(D)\\\
-1,&\mbox{if}~{}\operatorname{pspan}(D)\neq\operatorname{span}(D).\\\
\end{array}\right.\end{aligned}$

2\. Let $m=\dim(\operatorname{span}(D))\geq 1.$ For all bases $B$ of
$\operatorname{span}(D)$ contained in $D,$ compute

$\begin{aligned} \quad(2.1)&\quad\gamma_{B}=({\tt
ps})\frac{1}{\sqrt{\mathbf{1}_{m}\top\mathbf{G}(B)^{-1}\mathbf{1}_{m}}}&&\text{(pos.
if $\operatorname{pspan}(D)=\operatorname{span}(D)$, neg. otherwise)},\\\
\quad(2.2)&\quad
u_{B}=\gamma_{B}\left(B^{\top}\right)^{\dagger}\mathbf{1}_{m}&&\text{(the unit
vector associated to $\gamma_{B}$)},\\\ \quad(2.3)&\quad
p_{B}=\begin{bmatrix}[p_{B}]_{1}&\cdots&[p_{B}]_{q}\end{bmatrix}=(u_{B})^{\top}D&&\text{(the
dot product vector)},\\\ \quad(2.4)&\quad\mathring{p}_{B}=\max_{1\leq j\leq
q}[p_{B}]_{j}&&\mbox{(the maximum value in $p_{B}$)}.\\\ \end{aligned}$

3\. Return

$\begin{aligned}
\quad(3.1)&\quad\operatorname{cm}_{D}(D)=\left\\{\begin{array}[]{lll}\displaystyle\min_{B\,\subseteq\,D}\mathring{p}_{B},&\mbox{if}~{}{\tt
ps}=1&~{}(\operatorname{pspan}(D)=\operatorname{span}(D)),\\\
\displaystyle\min\left\\{\min_{B\,\subseteq\,D}\mathring{p}_{B},0\right\\},&\mbox{if}~{}{\tt
ps}=-1&~{}(\operatorname{pspan}(D)\neq\operatorname{span}(D)).\\\
\end{array}\right.\\\
\quad(3.2)&\quad\mathrm{cV}_{D}(D)=\left\\{\begin{array}[]{ll}\displaystyle\\{u_{B}:\mathring{p}_{B}=\operatorname{cm}_{D}(D)\\},&\mbox{if}~{}\operatorname{cm}_{D}(D)\neq
0,\\\
\displaystyle\\{u\in\operatorname{span}(D):D^{\top}u\leq\mathbf{0}_{q},\|u\|=1\\},&\mbox{if}~{}\operatorname{cm}_{D}(D)=0.\\\
\end{array}\right.\end{aligned}$

Algorithm 1 The cosine measure of a finite set $D$ relative to
$\operatorname{span}(D)$

To prove that the algorithm returns the correct cosine measure and the cosine
vector set, we begin by introducing several results that can be viewed as a
generalization of the results in hare2020deterministic ; naevdal2018 . The
following lemma is an adaptation of Lemma 1 in naevdal2018 .

###### Lemma 5

Let $B=\begin{bmatrix}d_{1}&\cdots&d_{m}\end{bmatrix}$ be a basis of
$S_{B}=\operatorname{span}(B)$ in $\mathbb{R}^{n}$ written in matrix form
where $1\leq m\leq n$ and where each $d_{j}$ is a unit vector. Then there
exist a unit vectors $u_{B}\in S_{B}$ such that

$(u_{B})^{\top}d_{1}=\dots=(u_{B})^{\top}d_{m}=\gamma_{B},$

and

$((-1)u_{B})^{\top}d_{1}=\dots=((-1)u_{B})^{\top}d_{m}=(-1)\gamma_{B}.$

where

$\displaystyle\gamma_{B}$
$\displaystyle=\frac{1}{\sqrt{\mathbf{1}_{m}^{\top}\mathbf{G}(B)^{-1}\mathbf{1}_{m}}}>0.$
(16)

Moreover,

$\displaystyle u_{B}$
$\displaystyle=\gamma_{B}(B^{\top})^{\dagger}\mathbf{1}_{m}.$ (17)

The proof is essentially identical to the proof of (naevdal2018, , Lemma 1) by
replacing $\mathbb{R}^{n}$ with $S_{B}.$

###### Lemma 6

Let $B=\\{d_{1},\cdots,d_{m}\\}$ be a basis of $S_{B}=\operatorname{span}(B)$
in $\mathbb{R}^{n}$ and where each $d_{j}$ is a unit vector. Suppose $u$ is a
unit vector in $S_{B}$ such that $u^{\top}d_{1}=\dots=u^{\top}d_{m}=\alpha>0.$
Then $\alpha=\gamma_{B},$ where $\gamma_{B}$ is defined as in (16).

The previous lemma can be proved using a similar process than the proof of
Lemma 13 in hare2020deterministic . Next, we recall a lemma that will be
useful to prove the key theorem of this section.

###### Lemma 7

(hare2020deterministic, , Lemma 16) Let $\epsilon\neq 0$ and let $u$ and $v$
be unit vectors in $\mathbb{R}^{n}.$ Then

  1. (i)

$\|u+\epsilon v\|=1$ if and only if $\epsilon=-2u^{\top}v$, and

  2. (ii)

$\|u+\epsilon v\|<1$ implies $\|u-\epsilon v\|>1$.

  3. (iii)

Assume $\|u\pm\epsilon v\|\neq 0.$ Then

$\displaystyle\frac{u\pm\epsilon v}{\|u\pm\epsilon v\|}=u\iff v=\pm u.$

###### Theorem 5.1

Let $D$ be a nonempty set of nonzero vectors in $\mathbb{R}^{n}$ with
$\operatorname{cm}_{D}(D)\neq 0.$ Let $u_{B}\in\mathrm{cV}_{D}(D)$. Then

$\operatorname{span}(\operatorname{\mathcal{A}}_{D}(D,u_{B}))=\operatorname{span}(D).$

###### Proof

Without loss of generality, assume that all vectors $d$ in $D$ are unit
vectors. Suppose that
$\operatorname{span}(\operatorname{\mathcal{A}}_{D}(D,u_{B}))\neq\operatorname{span}(D)$,
i.e., the rank of $\operatorname{\mathcal{A}}_{D}(D,u_{B})$ is strictly less
than $\dim(\operatorname{span}(D)).$ This implies that the kernel of
$\operatorname{\mathcal{A}}_{D}(D,u_{B})$ is nonempty. Let
$v\in\operatorname{span}(D)$ be a unit vector in the kernel of
$\operatorname{\mathcal{A}}_{D}(D,u_{B})$. This means that $d^{\top}v=0$ for
all $d$ in $\operatorname{\mathcal{A}}_{D}(D,u_{B}).$

Notice that, if $d\in D\setminus\operatorname{\mathcal{A}}_{D}(D,u_{B}),$ then

$d^{\top}u_{B}<\operatorname{cm}_{D}(D).$

Consider the vector $u_{B}+\epsilon v\in\operatorname{span}(D).$ Since
$\operatorname{cm}_{D}(D)\neq 0,$ it follows that $u_{B}\neq\pm v$ as
$u_{B}^{\top}d\neq 0$ for all $d\in\operatorname{\mathcal{A}}_{D}(D,u_{B}).$
Hence, using Lemma 7(iii), for sufficiently small $\epsilon>0$ and not equal
to $|-2u_{B}^{\top}v|,$ we have

$\frac{d^{\top}(u_{B}\pm\epsilon v)}{\|u_{B}\pm\epsilon
v\|}<\operatorname{cm}_{D}(D)$

for all $d\in D\setminus\operatorname{\mathcal{A}}_{D}(D,u_{B}).$ Moreover,
since $d^{\top}v=0,$ it follows that

$\frac{d^{\top}(u_{B}\pm\epsilon v)}{\|u_{B}\pm\epsilon
v\|}=\frac{d^{\top}u_{B}}{\|u_{B}\pm\epsilon v\|}\pm
0=\frac{\operatorname{cm}_{D}(D)}{\|u_{B}\pm\epsilon v\|}$

for all $d\in\operatorname{\mathcal{A}}_{D}(D,u_{B})$ and where
$\operatorname{cm}_{D}(D)\neq 0$ by assumption. By Lemma 7(i),
$\epsilon\neq-2u_{B}^{\top}v$ implies that $\|u_{B}+\epsilon v\|\neq 1.$ By
Lemma 7(ii), if $\|u_{B}+\epsilon v\|<1$, then $\|u_{B}-\epsilon v\|>1.$
Select $w$ in $\\{u_{B}+\epsilon v,u_{B}-\epsilon v\\}$ such that $\|w\|>1.$
Then

$\frac{d^{\top}w}{\|w\|}<\operatorname{cm}_{D}(D)$

for all $d\in D.$ This contradicts the definition of cosine measure.

Therefore,
$\operatorname{span}(D)\subseteq\operatorname{span}(\operatorname{\mathcal{A}}_{D}(D,u_{B}))\subseteq\operatorname{span}(D)$,
and the result follows. ∎

Theorem 5.1 can be viewed as an extension of Proposition 17 in
hare2020deterministic  for the following two reasons: the linear subspace
$\operatorname{span}(D)$ is considered rather than the whole space
$\mathbb{R}^{n}$; and the assumption that the set $D$ considered is a positive
spanning set is deleted and replaced by the more general condition that
$\operatorname{cm}_{D}(D)\neq 0$.

The following corollary follows from Theorem 5.1 and the fact that a spanning
set of a vector space contains a basis of the vector space (Brown1988, ,
Theorem 2.11).

###### Corollary 7

Let $D$ be a nonempty set of nonzero vectors in $\mathbb{R}^{n}$ such that
$\operatorname{cm}_{D}(D)\neq 0.$ Let $u_{B}\in\mathrm{cV}(D).$ Then
$\operatorname{\mathcal{A}}_{D}(D,u_{B})$ contains a basis of
$\operatorname{span}(D).$

We are now ready to show that Algorithm 1 returns the desired values.

###### Theorem 5.2

Let $D=\\{d_{1},\dots,d_{q}\\}$ be a set of $q\geq 1$ nonzero vectors in
$\mathbb{R}^{n}.$ Then Algorithm 1 returns $\operatorname{cm}_{D}(D)$ and
$\mathrm{cV}_{D}(D)$.

###### Proof

Without loss of generality, assume that all vectors $d_{j}$ are unit vectors.
Since $q\geq 1$, $\mathrm{cV}_{D}(D)\neq\emptyset$. Let
$u_{B}\in\mathrm{cV}_{D}(D)$. Define

${\tt
ps}=\left\\{\begin{array}[]{rl}1,&\mbox{if}~{}\operatorname{pspan}(D)=\operatorname{span}(D)\\\
-1,&\mbox{if}~{}\operatorname{pspan}(D)\neq\operatorname{span}(D).\\\
\end{array}\right.$

Case (i) ${\tt ps=1}.$ Suppose ${\tt ps=1}.$ By Proposition 5, this implies
$\operatorname{cm}_{D}(D)>0.$ Let $u_{B}\in\mathrm{cV}_{D}(D)$. By Corollary
7, $\operatorname{\mathcal{A}}_{D}(D,u_{B})$ contains a basis of
$\operatorname{span}(D)$. Without loss of generality, let this basis (written
in matrix form) be $B_{*}=\begin{bmatrix}d_{1}&\cdots&d_{m}\end{bmatrix}$
where $m=\dim(\operatorname{span}(D))\geq 1.$ Hence,

$\displaystyle\operatorname{cm}_{D}(D)=d_{1}^{\top}u_{B}=\cdots=d_{m}^{\top}u_{B}>0.$

By Lemma 6,

$\displaystyle\operatorname{cm}_{D}(D)=\gamma_{B_{*}}=(1)\frac{1}{\sqrt{\mathbf{1}_{m}^{\top}\mathbf{G}(B_{*})^{-1}\mathbf{1}_{m}}}$

Note that $\mathring{p}_{B_{\ast}}=\max_{1\leq j\leq
q}d_{j}^{\top}u_{B}=\gamma_{B_{\ast}}$ since
$\gamma_{B_{\ast}}=\operatorname{cm}_{D}(D).$ Therefore, we have

$\displaystyle\operatorname{cm}_{D}(D)=\min_{B\subseteq
D}\mathring{p}_{B}=\mathring{p}_{B_{\ast}}.$

Taking all the vectors $u_{B}$ associated to $\mathring{p}_{B}$ such that
$\operatorname{cm}_{D}(D)=\mathring{p}_{B}$ in Step (3.2) returns the complete
set $\mathrm{cV}_{D}(D).$

Case (ii) ${\tt ps=-1}.$ Suppose ${\tt ps=-1}.$ Then either
$\operatorname{cm}_{D}(D)<0$ or $\operatorname{cm}_{D}(D)=0.$ When
$\operatorname{cm}_{D}(D)<0,$ using any $u_{B}\in\mathrm{cV}_{D}(D)$,
Corollary 7 guarantees that the $\operatorname{\mathcal{A}}_{D}(D,u_{B})$
contains a basis of $\operatorname{span}(D)$. A similar process than the
previous case shows that the cosine measure is equal to

$\operatorname{cm}_{D}(D)=\min_{B\subseteq D}\mathring{p}_{B}.$

If $\operatorname{cm}_{D}(D)=0$, then Corollary 7 does not apply, so
$\min_{B\subseteq D}\mathring{p}_{B}$ can be $0$ or strictly positive. (If
$\operatorname{cm}_{D}(D)=0$, then
$\operatorname{cm}_{D}(D)\leq\min_{B\subseteq D}\mathring{p}_{B}$ implies that
this value cannot be negative.) Therefore,

$\min\left\\{\min_{B\,\subseteq\,D}\mathring{p}_{B},0\right\\}$

returns the exact cosine measure when ${\tt ps=-1}.$

When $\operatorname{cm}_{D}(D)<0,$ then the first branch of Step (3.2) returns
the complete vector set $\mathrm{cV}_{D}(D)$ by Theorem 5.1. When
$\operatorname{cm}_{D}(D)=0,$ then finding all unit vectors $u$ in
$\operatorname{span}(D)$ such that $D^{\top}u\leq\mathbf{0}_{q}$ provides the
complete vector set, which is the second branch in Step (3.2). ∎

##  6 Conclusion

This paper introduces the definitions of the cosine measure relative to a
subspace, and the related cosine vector set relative to a subspace. These
definitions not only generalize the cosine measure and cosine vector set to
allow for working in subspaces, but also generalize these ideas to work for
infinite sets.

Novel results demonstrate the value of these new definitions for working with
sets that are not positive spanning. Proposition 1 shows that any nonempty set
of vectors can be extended to positive spanning set of its span by adding at
most one vector to the set. Section 4 provides several properties of the
cosine measure relative to a subspace. Theorem 4.1 shows that if the cosine
measure of a set $D$ differs from the cosine measure relative to the span of
$D$, then $D$ is a positive spanning set of its span and
$\operatorname{span}(D)$ must be a proper subspace of $\mathbb{R}^{n}.$
Theorem 4.2 proves that the cosine measure relative to
$\operatorname{span}(D)$ is equal to zero if and only if the set $D$ contains
a positive spanning set of the span of a proper nonempty subset of $D$.
Theorem 4.4 uses the notion of cosine measure relative to a subspace to define
two error bounds on the projected gradient of a smooth function. In the case
where the set is not a positive spanning set of its span, Corollary 6
introduces results that could be valuable when the poll step of a derivative-
free algorithm fails. Lastly, a deterministic algorithm is proposed to compute
the cosine measure relative to its span. The algorithm is designed to accept a
non-positive spanning set as an input. Combined, these results demonstrate
that the cosine measure relative to a subspace is a valuable and practical
tool to quantify the positive spanning properties of a set relative to a
subspace. On a final note, an implementation of Algorithm 1 in MATLAB is
available upon request.

## References

  * (1) C. Audet and J. Dennis, Mesh adaptive direct search algorithms for constrained optimization, SIAM Journal on Optimization, 17 (2006), pp. 188–217.
  * (2) C. Audet, J. Dennis, Jr., and S. Le Digabel, Parallel space decomposition of the mesh adaptive direct search algorithm, SIAM Journal on Optimization, 19 (2008), pp. 1150–1170.
  * (3) C. Audet and W. Hare, Derivative-Free and Blackbox Optimization, Springer Series in Operations Research and Financial Engineering, Springer, Cham, Switzerland, 2017.
  * (4) W. Brown, A Second Course in Linear Algebra, Wiley, 1988.
  * (5) C. Cartis and L. Roberts, Scalable subspace methods for derivative-free nonlinear least-squares optimization, Mathematical Programming, 199 (2023), pp. 461–524.
  * (6) A. Conn, K. Scheinberg, and L. Vicente, Introduction to Derivative-Free Optimization, MOS-SIAM Series on Optimization, SIAM, Philadelphia, 2009.
  * (7) C. Davis, Theory of positive linear dependence, American Journal of Mathematics, 76 (1954), pp. 733–746.
  * (8) E. Dolan, R. Lewis, and V. Torczon, On the local convergence of pattern search, SIAM Journal on Optimization, 14 (2003), pp. 567–583.
  * (9) S. Gratton, C. Royer, L. Vicente, and Z. Zhang, Direct search based on probabilistic feasible descent for bound and linearly constrained problems, Computational Optimization and Applications, 72 (2019), pp. 525–559.
  * (10) W. Hare and G. Jarry-Bolduc, A deterministic algorithm to compute the cosine measure of a finite positive spanning set, Optimization Letters, 14 (2020), pp. 1305–1316.
  * (11) W. Hare, G. Jarry-Bolduc, S. Kerleau, and C. Royer, Using orthogonally structured positive bases for constructing positive $k$-spanning sets with cosine measure guarantees, Linear Algebra and its Applications, 680 (2024), pp. 183–207.
  * (12) W. Hare, G. Jarry-Bolduc, and C. Planiden, Nicely structured positive bases with maximal cosine measure, Optimization Letters, (2023), pp. 1–21.
  * (13) W. Hare and H. Song, On the cardinality of positively linearly independent sets, Optimization Letters, 10 (2016), pp. 649–654.
  * (14) M. Kimiaei, A. Neumaier, and P. Faramarzi, New subspace method for unconstrained derivative-free optimization, ACM Transactions on Mathematical Software, 49 (2023).
  * (15) T. Kolda, R. Lewis, and V. Torczon, Optimization by direct search: New perspectives on some classical and modern methods, SIAM Review, 45 (2003), pp. 385–482.
  * (16) T. Kolda, R. Lewis, and V. Torczon, Optimization by direct search: New perspectives on some classical and modern methods, SIAM Review, 45 (2003), pp. 385–482.
  * (17) D. Kozak, S. Becker, A. Doostan, and L. Tenorio, A stochastic subspace approach to gradient-free optimization in high dimensions, Computational Optimization and Applications, 79 (2021), pp. 339–368.
  * (18) R. Lewis and V. Torczon, Rank ordering and positive bases in pattern search algorithms, Tech. Rep. TR96-71, ICASE, NASA Langley Research Center, 1996\.
  * (19) G. Nævdal, Positive bases with maximal cosine measure, Optimization Letters, (2018), pp. 1–8.
  * (20) R. Regis, On the properties of positive spanning sets and positive bases, Optimization and Engineering, 17 (2016), pp. 229–262.
  * (21) , On the properties of the cosine measure and the uniform angle subspace, Computational Optimization and Applications, 78 (2021), pp. 915–952.
  * (22) R. Rockafellar, Convex analysis, vol. 28.;28;, Princeton University Press, Princeton, New Jersey, 1970.
  * (23) S. Roman, Advanced Linear Algebra, vol. 135, Springer, New York, 3rd ed., 2007.
  * (24) Z. Romanowicz, Geometric structure of positive bases in linear spaces, Applicationes Mathematicae, 19 (1987), pp. 557–567.
  * (25) V. Torczon, On the convergence of pattern search algorithms, SIAM Journal on Optimization, 7 (1997), pp. 1–25.
  * (26) P. Xie and Y. Yuan, A new two-dimensional model-based subspace method for large-scale unconstrained derivative-free optimization: 2d-mosub, arXiv preprint arXiv:2309.14855, (2023).