$${\text {B}}$$ -subdifferentials of the projection onto the matrix simplex | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

\({\text {B}}\)-subdifferentials of the projection onto the matrix simplex

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

An important tool in matrix optimization problems is the strong semismoothness of the projection mapping onto the cone of real symmetric positive semidefinite matrices, and the explicit formula for its \({\text {B}}\)(ouligand)-subdifferentials. In this paper, we examine the corresponding results for the so-called matrix simplex, that is, the set of real symmetric positive semidefinite matrices whose traces are equal to one. This result complements the current literature and enlarges the toolbox of matrix spectral operators whose \({\text {B}}\)-subdifferentials are explicitly formulated. Since the matrix simplex frequently arises in subproblems for solving matrix optimization problems, the derived results can potentially serve as a useful tool for efficiently solving these problems. As an illustration, we present a numerical example to demonstrate that the proposed approach can outperform the existing approaches which used projection mapping onto positive semidefinite matrix cone directly.

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

Access this article

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

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer-Verlag, New York (2000)

    Book  Google Scholar 

  2. Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003)

    Article  MathSciNet  Google Scholar 

  3. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  4. Comon, P., Golub, G., Lim, L.-H., Mourrain, B.: Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30, 1254–1279 (2008)

    Article  MathSciNet  Google Scholar 

  5. Ding, C.: An introduction to a class of matrix optimization problems. Ph.D. thesis, National University of Singapore, (2012)

  6. Ding, C., Sun, D.F., Toh, K.-C.: An introduction to a class of matrix cone programming. Math. Program. 144, 141–179 (2014)

    Article  MathSciNet  Google Scholar 

  7. Ding, C., Sun, D.F., Sun, J., Toh, K.-C.: Spectral operators of matrices. Math. Program. 168, 509–531 (2018)

    Article  MathSciNet  Google Scholar 

  8. Ding, C., Sun, D.F., Sun, J., Toh, K.-C.: Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian. SIAM J. Optim. 30, 630–659 (2020)

    Article  MathSciNet  Google Scholar 

  9. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  Google Scholar 

  10. Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer-Verlag, New York (2003)

    MATH  Google Scholar 

  11. Han, J.Y., Sun, D.F.: Newton and quasi-Newton methods for normal maps with polyhedral sets. J. Optim. Theory Appl. 94, 659–676 (1997)

    Article  MathSciNet  Google Scholar 

  12. Hartshorne, R.: Algebraic Geometry. Graduate Texts in Mathematics. Springer, New York (1977)

    Book  Google Scholar 

  13. Kummer, B.: Newton‘s method for non-differentiable functions. In: Guddat, J., Bank, B., Hollatz, H., Kall, P., Karte, D., Kummer, B., Lommatzsch, K., Tammer, L., Vlach, M., Zimmermann, K. (eds.) Advances in Mathematical Optimization. Akademi-Verlag, Berlin (1988)

    Google Scholar 

  14. Landsberg, J.M.: Tensors: Geometry and Applications. Graduate Studies in Mathematics 128, AMS, Providence, RI, (2012)

  15. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl. 149, M. Putinar and S. Sullivant, eds., pp. 157–270, Springer, New York, (2009)

  16. Li, G., Qi, L., Yu, G.: Semismoothness of the maximum eigenvalue function of a symmetric tensor and its application. Linear Algebra Appl. 438, 813–833 (2013)

    Article  MathSciNet  Google Scholar 

  17. Li, X., Sun, D.F., Toh, K.-C.: QSDPNAL: a two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming. Math. Program. Comput. 10, 703–743 (2018)

    Article  MathSciNet  Google Scholar 

  18. Nesterov, Y.: A method for solving the convex programming problem with convergence rate \(O(1/k^2)\). Dokl. Akad. Nauk SSSR 269, 543–547 (1983)

    MathSciNet  Google Scholar 

  19. Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155–1179 (2014)

    Article  MathSciNet  Google Scholar 

  20. Pang, J.S.: Newton‘s method for B-differentiable equations. Math. Oper. Res. 15, 311–341 (1990)

    Article  MathSciNet  Google Scholar 

  21. Pang, J.S., Ralph, D.: Piecewise smoothness, local invertibility, and parametric analysis of normal maps. Math. Oper. Res. 21, 401–426 (1996)

    Article  MathSciNet  Google Scholar 

  22. Pang, J.S., Sun, D.F., Sun, J.: Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems. Math. Oper. Res. 28, 272–284 (2003)

    Article  MathSciNet  Google Scholar 

  23. Pang, J.S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM. J. Optim. 3, 443–465 (1993)

    Article  MathSciNet  Google Scholar 

  24. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)

    Article  MathSciNet  Google Scholar 

  25. Qi, L., Sun, J.: A nonsmooth version of Newton‘s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  Google Scholar 

  26. Robinson, S.M.: Generalized equations. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming: The State of the Art, pp. 346–367. Springer-Verlag, Berlin (1983)

    Chapter  Google Scholar 

  27. Rockafellar, R.T., Wets, R.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften. Springer, Berlin (1998)

    Google Scholar 

  28. Sun, D.F., Sun, J.: Strong semismoothness of eigenvalues of symmetric matrices and its applications in inverse eigenvalue problems. SIAM J. Numer. Anal. 40, 2352–2367 (2003)

    Article  Google Scholar 

  29. Sun, D.F., Sun, J.: Semismoothness matrix valued functions. Math. Oper. Res. 27, 150–169 (2002)

    Article  MathSciNet  Google Scholar 

  30. Sun, D.F., Toh, K.-C., Yuan, Y.C., Zhao, X.Y.: SDPNAL\(+\): a Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35, 87–115 (2020)

    Article  MathSciNet  Google Scholar 

  31. Sturm, J.F.: SeDuMi 1.02: a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(12), 625–653 (1999)

    Article  MathSciNet  Google Scholar 

  32. Toh, K.-C., Todd, M.J., Tutuncu, R.H.: SDPT3: a Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545–581 (1999)

    Article  MathSciNet  Google Scholar 

  33. Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)

    Article  MathSciNet  Google Scholar 

  34. Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms and Applications. Kluwer Academic Publishers, Boston (2000)

    Book  Google Scholar 

  35. Yang, L.Q., Sun, D.F., Toh, K.-C.: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7, 331–366 (2015)

    Article  MathSciNet  Google Scholar 

  36. Zhao, X.Y., Sun, D.F., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is partially supported by National Science Foundation of China (Grant Nos. 11771328 and 12171128), Young Elite Scientists Sponsorship Program by Tianjin, and the Natural Science Foundation of Zhejiang Province, China (Grant No. LD19A010002). The second author’s work is partially supported by a research grant from Australian Research Council (Grant No. DP190100555).

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou, 310018, China

    Shenglong Hu

  2. Department of Applied Mathematics, University of New South Wales, Sydney, 2052, Australia

    Guoyin Li

Authors
  1. Shenglong Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guoyin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shenglong Hu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hu, S., Li, G. \({\text {B}}\)-subdifferentials of the projection onto the matrix simplex. Comput Optim Appl 80, 915–941 (2021). https://doi.org/10.1007/s10589-021-00316-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-021-00316-0

Keywords

Mathematics Subject Classification

Search

Navigation