A Collection of Nonsmooth Riemannian Optimization Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Collection of Nonsmooth Riemannian Optimization Problems

  • Chapter
  • First Online:
Nonsmooth Optimization and Its Applications

Part of the book series: International Series of Numerical Mathematics ((ISNM,volume 170))

Abstract

Nonsmooth Riemannian optimization is still a scarcely explored subfield of optimization theory that concerns the general problem of minimizing (or maximizing) over a domain endowed with a manifold structure, a real-valued function that is not everywhere differentiable. The purpose of this paper is to illustrate, by means of nine concrete examples, that nonsmooth Riemannian optimization finds numerous applications in engineering and the sciences.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 14299
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. P.-A. Absil and K. A. Gallivan. Joint diagonalization on the oblique manifold for independent component analysis. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 5, pages V–945–V–948, 2006.

    Google Scholar 

  2. P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ, 2008.

    Book  Google Scholar 

  3. Roy L. Adler, Jean-Pierre Dedieu, Joseph Y. Margulies, Marco Martens, and Mike Shub. Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal., 22(3):359–390, July 2002.

    Article  MathSciNet  Google Scholar 

  4. Orly Alter, Patrick O. Brown, and David Botstein. Singular value decomposition for genome-wide expression data processing and modeling. PNAS, 97(18):10101–10106, 2000.

    Article  Google Scholar 

  5. Miroslav Bačák, Ronny Bergmann, Gabriele Steidl, and Andreas Weinmann. A second order nonsmooth variational model for restoring manifold-valued images. SIAM J. Sci. Comput., 38(1):A567–A597, 2016.

    Article  MathSciNet  Google Scholar 

  6. E. Birgin, J. Martínez, and M. Raydan. Nonmonotone spectral projected gradient methods on convex sets. SIAM Journal on Optimization, 10(4):1196–1211, 2000.

    Article  MathSciNet  Google Scholar 

  7. Pierre B. Borckmans and P.-A. Absil. Fast oriented bounding box computation using particle swarm optimization. In Proceedings of the 18th European Symposium on Artificial Neural Networks (ESANN), 2010.

    Google Scholar 

  8. Pierre B. Borckmans, Mariya Ishteva, and P.-A. Absil. A modified particle swarm optimization algorithm for the best low multilinear rank approximation of higher-order tensors. In Marco Dorigo et al., editor, Swarm Intelligence, volume 6234 of Lecture Notes in Computer Science, pages 13–23. Springer-Verlag, 2010.

    Google Scholar 

  9. Pierre B. Borckmans, S. Easter Selvan, Nicolas Boumal, and P.-A. Absil. A Riemannian subgradient algorithm for economic dispatch with valve-point effect. J. Comput. Applied. Math., 255:848–866, 2013.

    Google Scholar 

  10. Nicolas Boumal, Bamdev Mishra, P.-A. Absil, and Rodolphe Sepulchre. Manopt, a Matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 15:1455–1459, 2014.

    Google Scholar 

  11. D. S. Broomhead and M. J. Kirby. Dimensionality reduction using secant-based projection methods: the induced dynamics in projected systems. Nonlinear Dynam., 41(1–3):47–67, 2005.

    Article  MathSciNet  Google Scholar 

  12. Léopold Cambier and P.-A. Absil. Robust low-rank matrix completion by Riemannian optimization. SIAM Journal on Scientific Computing, 38(5):S440–S460, 2016.

    Google Scholar 

  13. Chi Keung Chan. Minimum Bounding Boxes and Volume Decomposition of Cad Models. PhD thesis, University of Hong Kong (People’s Republic of China), 2003.

    Google Scholar 

  14. A. Chattopadhyay, S. E. Selvan, and U. Amato. A derivative-free Riemannian Powell’s method, minimizing Hartley-entropy-based ICA contrast. IEEE Transactions on Neural Networks and Learning Systems, PP(99):1–1, 2015.

    Google Scholar 

  15. Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434–448, 2007.

    Google Scholar 

  16. Laurent Demanet and Paul Hand. Scaling law for recovering the sparsest element in a subspace. Information and Inference: A Journal of the IMA, 3(4):295–309, 2014.

    Article  MathSciNet  Google Scholar 

  17. G. Dirr, U. Helmke, and C. Lageman. Nonsmooth Riemannian optimization with applications to sphere packing and grasping. In Lagrangian and Hamiltonian methods for nonlinear control 2006, volume 366 of Lecture Notes in Control and Inform. Sci., pages 29–45. Springer, Berlin, 2007.

    Google Scholar 

  18. David L. Donoho and Jared Tanner. Sparse nonnegative solution of underdetermined linear equations by linear programming. PNAS, 102(27):9446–9451, 2005.

    Article  MathSciNet  Google Scholar 

  19. David W. Dreisigmeyer. Direct search algorithms over Riemannian manifolds. Optimization Online 2007-08-1742, December 2006.

    Google Scholar 

  20. David W. Dreisigmeyer. A quasi-isometric embedding algorithm, 2017.

    Google Scholar 

  21. C. Ericson. Real-Time Collision Detection. CRC Press, Inc., Boca Raton, FL, USA, 2004.

    Book  Google Scholar 

  22. D. Gabay. Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl., 37(2):177–219, 1982.

    Article  MathSciNet  Google Scholar 

  23. Matthieu Genicot, Wen Huang, and Nickolay T. Trendafilov. Weakly correlated sparse components with nearly orthonormal loadings. In Geometric Science of Information, pages 484–490, 2015.

    Google Scholar 

  24. R. H. Gohary and T. N. Davidson. Noncoherent MIMO communication: Grassmannian constellations and efficient detection. IEEE Trans. Inform. Theory, 55(3):1176–1205, 2009.

    Article  MathSciNet  Google Scholar 

  25. Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, third edition, 1996.

    Google Scholar 

  26. S. Gottschalk, M. C. Lin, and D. Manocha. Obbtree: A hierarchical structure for rapid interference detection. In SIGGRAPH ’96 Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 171–180, New York, NY, 1996. ACM.

    Google Scholar 

  27. P. Grohs and S. Hosseini. Nonsmooth trust region algorithms for locally Lipschitz functions on Riemannian manifolds. IMA J. Numer. Anal., 36(3):1167–1192, 2016.

    Article  MathSciNet  Google Scholar 

  28. P. Grohs and S. Hosseini. ε-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds. Adv. Comput. Math., 42(2):333–360, 2016.

    Google Scholar 

  29. P. Grohs and M. Sprecher. Total variation regularization on Riemannian manifolds by iteratively reweighted minimization. Inf. Inference, 5(4):353–378, 2016.

    Article  MathSciNet  Google Scholar 

  30. S. Hosseini, W. Huang, and R. Yousefpour. Line search algorithms for locally Lipschitz functions on Riemannian manifolds. November 2016. INS Preprint No. 1626.

    Google Scholar 

  31. S. Hosseini and A. Uschmajew. A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim., 27(1):173–189, 2017.

    Article  MathSciNet  Google Scholar 

  32. Wen Huang. Optimization Algorithms on Riemannian Manifolds with Applications. PhD thesis, Department of Mathematics, Florida State University, November 2013.

    Google Scholar 

  33. Wen Huang, P.-A. Absil, and K. A. Gallivan. Intrinsic representation of tangent vectors and vector transports on matrix manifolds. Numerische Mathematik, 136(2):523–543, Jun 2017.

    Google Scholar 

  34. Wen Huang, P.-A. Absil, K. A. Gallivan, and Paul Hand. ROPTLIB: an object-oriented C++ library for optimization on Riemannian manifolds. Technical Report FSU16-14, Florida State University, 2016.

    Google Scholar 

  35. Wen Huang, K. A. Gallivan, and P.-A. Absil. A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM J. Optim., 25(3):1660–1685, 2015.

    Google Scholar 

  36. V. V. Ivanov. The theory of approximate methods and their application to the numerical solution of singular integral equations. Noordhoff International Publishing, Schuttersveld 9, P. O. Box 26, Leyden, The Netherlands, 1976.

    Google Scholar 

  37. Ian T Jolliffe, Nickolay T Trendafilov, and Mudassir Uddin. A modified principal component technique based on the lasso. Journal of Computational and Graphical Statistics, 12(3):531–547, 2003.

    Google Scholar 

  38. M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre. Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim, 20(5):2327–2351, 2010.

    Article  MathSciNet  Google Scholar 

  39. Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. J. Mach. Learn. Res., 11:517–553, 2010.

    MathSciNet  MATH  Google Scholar 

  40. Martin Kleinsteuber and Hao Shen. Intrinsic Newton’s method on oblique manifolds for overdetermined blind source separation. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems – MTNS, pages 2139–2143, 2010.

    Google Scholar 

  41. Artiom Kovnatsky, Klaus Glashoff, and Michael M. Bronstein. MADMM: A generic algorithm for non-smooth optimization on manifolds. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision – ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part V, pages 680–696. Springer International Publishing, Cham, 2016.

    Chapter  Google Scholar 

  42. C. Lageman and U. Helmke. Optimization methods for the sphere packing problem on Grassmannians. In Taming heterogeneity and complexity of embedded control, pages 393–408. ISTE, London, 2007.

    Google Scholar 

  43. Christian Lageman. Convergence of gradient-like dynamical systems and optimization algorithms. PhD thesis, Julius-Maximilians-Universität Würzburg, 2007.

    Google Scholar 

  44. Adrian S. Lewis and Michael L. Overton. Nonsmooth optimization via quasi-Newton methods. Mathematical Programming, 141(1):135–163, 2013.

    Article  MathSciNet  Google Scholar 

  45. V. Morozov. Methods for Solving Incorrectly Posed Problems. Springer-Verlag, 1984.

    Book  Google Scholar 

  46. Karl Pearson. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(11):559–572, 1901.

    MATH  Google Scholar 

  47. Q. Qu, J. Sun, and J. Wright. Finding a sparse vector in a subspace: linear sparsity using alternating directions. IEEE Trans. Inform. Theory, 62(10):5855–5880, 2016.

    Article  MathSciNet  Google Scholar 

  48. Wolfgang Ring and Benedikt Wirth. Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim., 22(2):596–627, 2012.

    Article  MathSciNet  Google Scholar 

  49. L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Phys. D, 60(1–4):259–268, 1992. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991).

    Google Scholar 

  50. Hiroyuki Sato. A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions. Computational Optimization and Applications, 64(2):101–118, 2016.

    Article  MathSciNet  Google Scholar 

  51. P. J. Schneider and D. Eberly. Geometric Tools for Computer Graphics. Elsevier Science Inc., New York, NY, USA, 2002.

    Google Scholar 

  52. S. Easter Selvan, Pierre B. Borckmans, A. Chattopadhyay, and P.-A. Absil. Spherical mesh adaptive direct search for separating quasi-uncorrelated sources by range-based independent component analysis. Neural Comput., 25(9):2486–2522, 2013.

    Google Scholar 

  53. S. Easter Selvan, S. Thomas George, and R. Balakrishnan. Range-based ICA using a nonsmooth quasi-Newton optimizer for electroencephalographic source localization in focal epilepsy. Neural Computation, 27(3):628–671, 2015.

    Article  MathSciNet  Google Scholar 

  54. Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B, 58(1):267–288, 1996.

    MathSciNet  MATH  Google Scholar 

  55. A. N. Tikhonov and V. Y. Arsenin. Solutions of ill posed problems. V. H. Winston and Sons, 1977.

    MATH  Google Scholar 

  56. James Townsend, Niklas Koep, and Sebastian Weichwald. Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation. Journal of Machine Learning Research, 17(137):1–5, 2016.

    MathSciNet  MATH  Google Scholar 

  57. Nickolay T. Trendafilov. From simple structure to sparse components: a review. Computational Statistics, 29(3):431–454, Jun 2014.

    Article  MathSciNet  Google Scholar 

  58. C. Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297. Kluwer Academic Publishers Group, Dordrecht, 1994.

    Book  Google Scholar 

  59. F. Vrins, J. A. Lee, and M. Verleysen. A minimum-range approach to blind extraction of bounded sources. IEEE Transactions on Neural Networks, 18(3):809–822, May 2007.

    Article  Google Scholar 

  60. D.C. Walters and G.B. Sheble. Genetic algorithm solution of economic dispatch with valve point loading. Power Systems, IEEE Transactions on, 8(3):1325–1332, Aug 1993.

    Article  Google Scholar 

  61. Ke Wei, Jian-Feng Cai, Tony F. Chan, and Shingyu Leung. Guarantees of Riemannian optimization for low rank matrix recovery. SIAM Journal on Matrix Analysis and Applications, 37(3):1198–1222, 2016.

    Article  MathSciNet  Google Scholar 

  62. Allen J. Wood, Bruce F. Wollenberg, and Gerald B. Sheblé. Power Generation Operation and Control. John Wiley & Sons, Hoboken, New Jersey, third edition, 2014.

    Google Scholar 

  63. L. Zheng and D. N. C. Tse. Communication on the Grassmann manifold: a geometric approach to the noncoherent multiple-antenna channel. IEEE Trans. Inform. Theory, 48(2):359–383, 2002.

    Article  MathSciNet  Google Scholar 

  64. Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15(2):265–286, 2006.

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office. This work was supported by the Belgian FNRS through grant FRFC 2.4585.12.

Author information

Authors and Affiliations

  1. ICTEAM Institute, University of Louvain, Louvain-la-Neuve, Belgium

    P.-A. Absil

  2. Hausdorff Center for Mathematics and Institute for Numerical Simulation, University of Bonn, Bonn, Germany

    S. Hosseini

Authors
  1. P.-A. Absil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Hosseini
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P.-A. Absil .

Editor information

Editors and Affiliations

  1. IAV GmbH, Gifhorn, Germany

    Seyedehsomayeh Hosseini

  2. Department of Mathematics, Wayne State University, Detroit, MI, USA

    Boris S. Mordukhovich

  3. Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany

    André Uschmajew

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Absil, PA., Hosseini, S. (2019). A Collection of Nonsmooth Riemannian Optimization Problems. In: Hosseini, S., Mordukhovich, B., Uschmajew, A. (eds) Nonsmooth Optimization and Its Applications. International Series of Numerical Mathematics, vol 170. Birkhäuser, Cham. https://doi.org/10.1007/978-3-030-11370-4_1

Download citation

Publish with us

Policies and ethics