Year: 2020
Author: Yannan Chen, Min Xi, Hongchao Zhang
CSIAM Transactions on Applied Mathematics, Vol. 1 (2020), Iss. 4 : pp. 766–801
Abstract
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 Ł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 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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/csiam-am.2020-0026
CSIAM Transactions on Applied Mathematics, Vol. 1 (2020), Iss. 4 : pp. 766–801
Published online: 2020-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 36
Keywords: Derivative-free optimization spherical optimization geometry trust region method Łojasiewicz property global convergence convergence rate hypergraph partitioning.
Author Details
-
A Derivative-free Trust-region Method for Optimization on the Ellipsoid
Xie, Pengcheng
Journal of Physics: Conference Series, Vol. 2620 (2023), Iss. 1 P.012007
https://doi.org/10.1088/1742-6596/2620/1/012007 [Citations: 3]