论文标题
关于无衍生信任区域算法的线性和二次模型的复杂性常数
On complexity constants of linear and quadratic models for derivative-free trust-region algorithms
论文作者
论文摘要
复杂性分析已成为优化算法收敛分析的重要工具。对于无衍生优化算法，它没有什么不同。有趣的是，在发展复杂性结果时出现的几个常数隐藏了问题的维度。这项工作组织了一些有关基于线性和二次模型的无衍生信任区域算法中出现的界限的结果。所有常数均由样品集的质量，问题的维度和样本点数量明确给出。我们扩展了一些结果，以允许“不精确”的插值集。我们还提供了与文献中已经存在的不确定案例中现有的证据更清晰的证据。
Complexity analysis has become an important tool in the convergence analysis of optimization algorithms. For derivative-free optimization algorithms, it is not different. Interestingly, several constants that appear when developing complexity results hide the dimensions of the problem. This work organizes several results in literature about bounds that appear in derivative-free trust-region algorithms based on linear and quadratic models. All the constants are given explicitly by the quality of the sample set, dimension of the problem and number of sample points. We extend some results to allow "inexact" interpolation sets. We also provide a clearer proof than those already existing in literature for the underdetermined case.
