A Derivative-Free Geometric Algorithm for Optimization on a Sphere
A Derivative-Free Geometric Algorithm for Optimization on a Sphere
复制标题
DOI：
10.4208/csiam-am.2020-0026
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yannan Chen
中科院分区：
文献类型：
--
作者：
Yannan Chen
.单位球面上的优化在科学和工程中有着重要的应用。然而，目标函数的导数可能难以计算或被噪声破坏，甚至在许多应用中不可用。因此，我们提出了一个无导数几何算法（DFGA），据我们所知，这是第一个无导数算法，采用信赖域框架，探索球面几何来解决具有球面约束的优化问题。良好的几何形状的球面允许我们追求的优化在每一次迭代中的局部切空间的球。特别地，通过应用Householder和Cayley变换，DFGA在局部切空间上建立二次信赖域模型，使得局部优化本质上可以被视为无约束优化。在温和的假设下，我们证明了存在一个子序列的DFGA产生的迭代收敛到这个球形优化的一个稳定点。在Lojasiewicz性质下，我们证明了DFGA生成的所有迭代至少以线性或次线性收敛速度收敛.通过对超图划分所导致的球面定位问题、子空间聚类问题和图像分割问题的数值实验，表明DFGA在求解球面上的优化问题时，不需要使用导数，具有很好的鲁棒性和效率.
. Optimization on a unit sphere finds crucial applications in science and engineering. However, derivatives of the objective function may be difficult to compute or corrupted by noises, or even not available in many applications. Hence, we propose a Derivative-Free Geometric Algorithm (DFGA) which, to the best of our knowledge, is the first derivative-free algorithm that takes trust region framework and explores the spherical geometry to solve the optimization problem with a spherical constraint. Nice geometry of the spherical surface allows us to pursue the optimization at each iteration in a local tangent space of the sphere. Particularly, by applying Householder and Cayley transformations, DFGA builds a quadratic trust region model on the local tangent space such that the local optimization can essentially be treated as an unconstrained optimization. Under mild assumptions, we show that there exists a subsequence of the iterates generated by DFGA converging to a stationary point of this spherical optimization. Furthermore, under the (cid:32)Lojasiewicz property, we show that all the iterates generated by DFGA will converge with at least a linear or sublinear convergence rate. Our numerical experiments on solving the spherical location problems, subspace clustering and image segmentation problems resulted from hypergraph partitioning, indicate DFGA is very robust and efficient for solving optimization on a sphere without using derivatives.