A Derivative-Free Geometric Algorithm for Optimization on a Sphere (CSIAM Transactions on Applied Mathematics, 2020)
Optimization on a unit sphere finds crucial applications in science and engineering. However, derivatives of the objective function may be difficult to compute orcorrupted by noises, or even not available in many applications. Hence, we propose aDerivative-Free Geometric Algorithm (DFGA) which, to the best of our knowledge, isthe first derivative-free algorithm that takes trust region framework and explores thespherical geometry to solve the optimization problem with a spherical constraint. Nicegeometry of the spherical surface allows us to pursue the optimization at each iterationin a local tangent space of the sphere. Particularly, by applying Householder and Cayley transformations, DFGA builds a quadratic trust region model on the local tangentspace such that the local optimization can essentially be treated as an unconstrainedoptimization. Under mild assumptions, we show that there exists a subsequence ofthe iterates generated by DFGA converging to a stationary point of this spherical optimization. Furthermore, under the Łojasiewicz property, we show that all the iteratesgenerated 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 withoutusing derivatives.