论文标题
基于概率下降的直接搜索
Direct search based on probabilistic descent in reduced spaces
论文作者
论文摘要
在本文中，我们研究了一种通用直接搜索算法，其中使用随机子空间定义了轮询方向。由于与这些子空间中使用的子空间和方向相关的概率属性，因此得出了这种方法的复杂性保证。我们的分析至关重要地扩展了以前的确定性和概率论证，这是放宽对规范确定性方向的需求。结果，我们的方法涵盖了可以使用我们的子空间和方向属性来表征的各种新的最佳轮询策略。通过利用随机子空间嵌入和素描矩阵的结果，我们表明，对于我们的框架随机实例，获得了更好的复杂性界限。数值研究证实了随机分组的益处，尤其是在解决中等尺寸的问题时在子空间中完成的好处。
In this paper, we study a generic direct-search algorithm in which the polling directions are defined using random subspaces. Complexity guarantees for such an approach are derived thanks to probabilistic properties related to both the subspaces and the directions used within these subspaces. Our analysis crucially extends previous deterministic and probabilistic arguments by relaxing the need for directions to be deterministically bounded in norm. As a result, our approach encompasses a wide range of new optimal polling strategies that can be characterized using our subspace and direction properties. By leveraging results on random subspace embeddings and sketching matrices, we show that better complexity bounds are obtained for randomized instances of our framework. A numerical investigation confirms the benefit of randomization, particularly when done in subspaces, when solving problems of moderately large dimension.
