Global Optimization on the Sphere with Half-space Constraints: A Stochastic Hybrid Systems Approach
Matina Baradaran, Andrew R. Teel · 2019
This paper develops a stochastic, hybrid optimization algorithm for globally minimizing an arbitrary continuously differentiable (C1) function on the unit sphere intersected with an arbitrary half-space in ℝ3. Hysteresis switching between coordinate charts is used to enable the algorithm to fully explore the sphere by flowing. During flows, the optimization algorithm uses (projected) gradient descent when near the boundary of the half space. It may use an update rule inspired by accelerated gradient methods away from the boundary of the half space. It uses hysteresis switching between the two continuous-time update methods. Periodically, stochastic probing on the sphere is used to attempt to improve the value of the cost function. This stochastic step prevents the algorithm from getting stuck at singularities of the cost function's gradient that do not correspond to global minima. A stability analysis of the algorithm is provided and the algorithm is demonstrated on a numerical example.