On the properties of positive spanning sets and positive bases
On the properties of positive spanning sets and positive bases
复制标题
关于正跨越集和正基的性质
DOI：
10.1007/s11081-015-9286-x
复制
发表时间：
2016
影响因子：
2.1
通讯作者：
R. Regis
中科院分区：
文献类型：
--
作者：
R. Regis
正跨度和正基的概念在无导数优化中是很重要的。事实上，一个众所周知的结果是，如果一个连续可微的目标函数在$$\mathbb{R}^n$$Rn上的梯度在一个点上是非零的，那么在$$\mathbb{R}^n$$Rn的任何正基（或任何正生成集）中的一个向量是目标函数从该点的下降方向。本文总结了基本结果，并探讨了额外的属性，积极的支撑集，积极的独立集和积极的基地，是潜在的有用的设计导数自由优化算法。特别是，它提供了这些特殊的向量集，以前没有提到的文献中的建设程序。证明了可逆线性变换保持正独立性和正生成性。此外，本文还引入了正生成集与正独立集之间的线性等价概念，简化了它们的结构分析。线性等价原来是Coope和Price（SIAM J Optim 11：859-869，2001）引入的正碱基之间的结构等价概念的推广。进一步阐明了线性无关集、生成集和普通基的哪些性质可以推广到正无关集、正生成集和正基。例如，线性独立集总是可以扩展到线性空间的基，但正独立集却不能总是扩展到正基。此外，$$R^n$$Rn中线性独立集的最大大小是n，但当$$n \ge 3$$n≥3时，$$\mathbb{R}^n$$Rn中正独立集的大小没有限制。只要有可能，结果证明了更一般的情况下，框架的凸锥，而不是专注于线性空间的正基。此外，本文还讨论了一些用于确定给定向量集是否正独立或是否正跨越$$\mathbb{R}^n$$Rn的线性子空间的算法。最后，它提供了一个算法，用于将任何有限向量集扩展到一个正的生成集$\mathbb{R}^n$$Rn，只使用相对较少的额外向量。
The concepts of positive span and positive basis are important in derivative-free optimization. In fact, a well-known result is that if the gradient of a continuously differentiable objective function on $$\mathbb{R}^n$$Rn is nonzero at a point, then one of the vectors in any positive basis (or any positive spanning set) of $$\mathbb{R}^n$$Rn is a descent direction for the objective function from that point. This article summarizes the basic results and explores additional properties of positive spanning sets, positively independent sets and positive bases that are potentially useful in the design of derivative-free optimization algorithms. In particular, it provides construction procedures for these special sets of vectors that were not previously mentioned in the literature. It also proves that invertible linear transformations preserve positive independence and the positive spanning property. Moreover, this article introduces the notion of linear equivalence between positive spanning sets and between positively independent sets to simplify the analysis of their structures. Linear equivalence turns out to be a generalization of the concept of structural equivalence between positive bases that was introduced by Coope and Price (SIAM J Optim 11:859–869, 2001). Furthermore, this article clarifies which properties of linearly independent sets, spanning sets and ordinary bases carry over to positively independent sets, positive spanning sets, and positive bases. For example, a linearly independent set can always be extended to a basis of a linear space but a positively independent set cannot always be extended to a positive basis. Also, the maximum size of a linearly independent set in $$R^n$$Rn is n but there is no limit to the size of a positively independent set in $$\mathbb{R}^n$$Rn when $$n \ge 3$$n≥3. Whenever possible, the results are proved for the more general case of frames of convex cones instead of focusing only on positive bases of linear spaces. In addition, this article discusses some algorithms for determining whether a given set of vectors is positively independent or whether it positively spans a linear subspace of $$\mathbb{R}^n$$Rn. Finally, it provides an algorithm for extending any finite set of vectors to a positive spanning set of $$\mathbb{R}^n$$Rn using only a relatively small number of additional vectors.