A Derivative-Free Geometric Algorithm for Optimization on a Sphere

Abstract

Optimization on a unit sphere finds crucial applications in science and engi-neering. 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 Cay-ley 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 op-timization. Furthermore, under the Łojasiewicz 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 clus-tering and image segmentation problems resulted from hypergraph partitioning, indi-cate DFGA is very robust and efficient for solving optimization on a sphere without using derivatives.

Keywords

Derivative-free optimization / spherical optimization / geometry / trust region method / Łojasiewicz property / global convergence / convergence rate / hypergraph partitioning