Abstract
In this paper, a complete characterization of the \({\text {B}}\)-subdifferential with explicit formula for the projection mapping onto the generalized spectraplex (aka generalized matrix simplex) is derived. The derivation is based on complete characterizations of the \({\text {B}}\)-subdifferential as well as the Han-Sun Jacobian of the projection mapping onto the generalized simplex. The formula provides tools for further computations and nonsmooth analysis involving this projection.
Similar content being viewed by others
Notes
The general case is derived by a similar proof through replacing suitably p by \(p'\) and w by \(w'\) as (21).
References
Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2013)
Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003)
Ding, C.: An Introduction to a Class of Matrix Optimization Problems. Ph.D Thesis, National University of Singapore (2012)
Ding, C., Sun, D.F., Toh, K.-C.: An introduction to a class of matrix cone programming. Math. Program. 144, 141–179 (2014)
Ding, C., Sun, D.F., Sun, J., Toh, K.-C.: Spectral operators of matrices. Math. Program. 168, 509–531 (2018)
Ding, C., Sun, D.F., Ye, J.J.: First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints. Math. Program. 147, 539–579 (2014)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2003)
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)
Hu, S., Li, G.: B-subdifferentials of the projection onto the standard matrix simplex. Comput. Optim. Appl. 80, 914–941 (2021)
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, pp. 114–125. Akademi-Verlag, Berlin (1988)
Lewis, A.S.: The convex analysis of unitarily invariant matrix functions. J. Conv. Anal. 2, 173–183 (1995)
Lewis, A.S.: Convex analysis on the Hermitian matrices. SIAM J. Optim. 6, 164–177 (1996)
Li, X.D., 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)
Lin, Y., Hu, S.: B-subdifferentials of the projection onto the generalized simplex. Asia-Pac. J. Oper. Res. (2021). https://doi.org/10.1142/S0217595921500202
Mordukhovich, B.M.: Generalized differential calculus for nonsmooth set-valued mappings. J. Math. Anal. Appl. 183, 250–288 (1994)
Mordukhovich, B.M.: Variational Analysis and Applications. Springer, Berlin (2018)
Pang, J.S.: Newton’s method for B-subdifferentiable equations. Math. Oper. Res. 15, 311–341 (1990)
Pang, J.S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993)
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)
Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)
Rademacher, H.: Über partielle und totale differenzierbarkeit von funktionen mehrerer Variabeln und Über die Transformation der Doppelintegrale. Math. Ann. 79, 340–359 (1919)
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)
Sun, D.F., Sun, J.: Semismoothness matrix valued functions. Math. Oper. Res. 27, 150–169 (2002)
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)
Sun, D.F., Toh, K.-C., Yuan, Y.C., Zhao, X.Y.: SDPNAL+: a Matlab software for semidefinite programming with bound constraints. Optim. Methods Softw. 35, 87–115 (2020)
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms and Applications. Kluwer Academic Publishers, Boston (2000)
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)
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)
Acknowledgements
The authors are grateful to the editors and the anonymous referees’ for their valuable comments. This work is partially supported by National Science Foundation of China (Grant Nos. 11771328,11801502 and 12171128) and the Natural Science Foundation of Zhejiang Province, China (Grant Nos. LD19A010002 and LY22A010022).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Russell Luke.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Lin, Y., Hu, S. \({\text {B}}\)-Subdifferential of the Projection onto the Generalized Spectraplex. J Optim Theory Appl 192, 702–724 (2022). https://doi.org/10.1007/s10957-021-01988-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-021-01988-8