Volume 1, Issue 4
A Derivative-Free Geometric Algorithm for Optimization on a Sphere

Yannan Chen, Min Xi & Hongchao Zhang

CSIAM Trans. Appl. Math., 1 (2020), pp. 766-801.

Published online: 2020-12

Export citation
  • 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.

  • Keywords

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

  • AMS Subject Headings

65K05, 90C30, 90C56

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-1-766, author = {Yannan and Chen and and 10045 and and Yannan Chen and Min and Xi and and 10046 and and Min Xi and Hongchao and Zhang and and 10047 and and Hongchao Zhang}, title = {A Derivative-Free Geometric Algorithm for Optimization on a Sphere}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2020}, volume = {1}, number = {4}, pages = {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.

}, issn = {2708-0579}, doi = {https://doi.org/10.4208/csiam-am.2020-0026}, url = {http://global-sci.org/intro/article_detail/csiam-am/18545.html} }
TY - JOUR T1 - A Derivative-Free Geometric Algorithm for Optimization on a Sphere AU - Chen , Yannan AU - Xi , Min AU - Zhang , Hongchao JO - CSIAM Transactions on Applied Mathematics VL - 4 SP - 766 EP - 801 PY - 2020 DA - 2020/12 SN - 1 DO - http://doi.org/10.4208/csiam-am.2020-0026 UR - https://global-sci.org/intro/article_detail/csiam-am/18545.html KW - Derivative-free optimization, spherical optimization, geometry, trust region method, Łojasiewicz property, global convergence, convergence rate, hypergraph partitioning. AB -

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.

Yannan Chen, Min Xi & Hongchao Zhang. (2020). A Derivative-Free Geometric Algorithm for Optimization on a Sphere. CSIAM Transactions on Applied Mathematics. 1 (4). 766-801. doi:10.4208/csiam-am.2020-0026
Copy to clipboard
The citation has been copied to your clipboard