Journal of the Operations Research Society of China >

2019 , Vol. 7 >Issue 2: 285 - 301

DOI: https://doi.org/10.1007/s40305-019-00245-0

Optimality Conditions for Rank-Constrained Matrix Optimization

Expand
  • 1 Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, China;
    2 School of Mathematical Sciences, Harbin Normal University, Harbin 150025, China

Received date: 2018-05-30

  Revised date: 2019-01-11

  Online published: 2019-06-30

Supported by

This research was supported by the National Natural Science Foundation of China (Nos. 11431002 and 11371116).

Fold

Abstract

In this paper, we comprehensively study optimality conditions for rank-constrained matrix optimization (RCMO). By calculating the Clarke tangent and normal cones to a rank-constrained set, along with the given Fréchet, Mordukhovich normal cones, we investigate four kinds of stationary points of the RCMO and analyze the relations between each stationary point and local/global minimizer of the RCMO. Furthermore, the second-order optimality condition of the RCMO is achieved with the help of the Clarke tangent cone.

Key words： Matrix optimization; Rank constraint; Normal cone; First-order optimality condition; Second-order optimality condition

Cite this article

Xin-Rong Li, Wen Song, Nai-Hua Xiu . Optimality Conditions for Rank-Constrained Matrix Optimization[J]. Journal of the Operations Research Society of China, 2019 , 7(2) : 285 -301 . DOI: 10.1007/s40305-019-00245-0

References

[1] Le, H.Y.:A variational approach of the rank function. J. Span. Soc. Stat. Oper. Res. 7(4), 207-240(2013)
[2] David, J.:Algorithms for Analysis and Design of Robust Controllers. PhD thesis, Kat. Univ. (1994)
[3] Fazel, M.:Matrix Rank Minimization with Applications. PhD thesis, Stanford University (2002)
[4] Natarajan, B.K.:Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227-234(1995)
[5] Vandenberghe, L., Boyd, S.:Semidefinite programming. SIAM Rev. 38(1), 49-95(1996)
[6] Chen, Y.Q., Xiu, N.H., Peng, D.T.:Global solutions of non-Lipschitz S2-Sp minimization over the positive semidefinite cone. Optim. Lett. 8(7), 2053-2064(2014)
[7] Gao, Y.:Structured Low Rank Matrix Optimization Problems:A Penalty Approach. PhD thesis, National University of Singapore (2010)
[8] Nie, F.P., Huang, H., Ding, C.:Low-rank matrix recovery via efficient Schatten p-norm minimization. In:Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pp. 655-661. AAAI Press, Toronto (2012)
[9] Lu, Z.S., Zhang, Y., Li, X.R.:Penalty decomposition methods for rank minimization. Optim. Methods Softw. 30, 531-558(2015)
[10] Delgado, R.A., Aguero, J.C., Goodwin, G.C.:A rank-constrained optimization approach:application to factor analysis. IFAC Proc. Vol. 47(3), 10373-10378(2014)
[11] Wen, Z.W., Yin, W.T., Zhang, Y.:Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Program. Comput. 4(4), 333-361(2012)
[12] Bi, S., Pan, S., Sun, D.:A Multi-stage Convex Relaxation Approach to Noisy Structured Low-Rank Matrix Recovery, available at https://www.researchgate.net/publication/314948486(2017)
[13] Zhou, S., Xiu, N., Qi, H.:Robust Euclidean Embedding via EDM Optimization, available at http://ww.researchgate.net/pubulication/323945500(2018)
[14] Cason, T.P., Absil, P.A., Van Dooren, P.:Iterative methods for low rank approximation of graph similarity matrices. Linear Algebra Appl. 438(4), 1863-1882(2013)
[15] Schneider, R., Uschmajew, A.:Convergence results for projected line-search methods on varieties of low-rank matrices via Lojasiewicz inequality. SIAM J. Optim. 25(1), 622-646(2015)
[16] Zhou, G.F.:Rank-Constrained Optimization:A Riemannian Manifold Approach. PhD thesis, Florida State University (2015)
[17] Zhou, G.F., Huang, W., Gallivan, K.A., Dooren, P.V., Absil, P.A.:A Riemannian rank-adaptive method for low-rank optimization. Neurocomputing 192, 72-80(2016)
[18] Luke, D.R.:Prox-regularity of rank constraint sets and implications for algorithms. J. Math. Imaging Vis. 47(3), 231-238(2013)
[19] Horn, R.A., Johnson, C.R.:Matrix Analysis, 2nd edn. Cambridge University Press, New York (2013)
[20] Hiriart-Urruty, J.B., Le, H.Y.:From Eckart and Young approximation to Moreau envelopes and vice versa. Rairo Recherche Operationnelle 47, 299-310(2013)
[21] Helmke, U., Shayman, M.A.:Critical points of matrix least squares distance functions. Linear Algebra Appl. 215, 1-19(1995)
[22] Rockafellar, R.T., Wets, R.J.:Variational Analysis. Springer, Berlin (1998)
[23] Mordukhovich, B.S.:Variational Analysis and Generalized Differentiation I:Basic Theory, Ⅱ:Applications. Springer, Berlin (2006)
[24] Guttman, L.:Enlargement methods for computing the inverse matrix. Ann. Math. Stat. 17, 336-343(1946)
[25] Hosseini, S., Luke, D.R., Uschmajew, A.:Tangent and Normal Cones for Low-Rank Matrices. Preprint, available at http://neitzel.ins.uni-bonn.de/research/pub/hosseini/LowRankCones.pdf (2017)
[26] Beck, A., Eldar, Y.:Sparsity constrained nonlinear optimization:optimality conditions and algorithms. SIAM J. Optim. 23, 1480-1509(2013)
[27] Negahban, S., Yu, B., Wainwright, M.J., Ravikumar, P.:A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Adv. Neural Inf. Process. Syst. 1348-1356(2009)
[28] Bahmani, S., Boufounos, P., Raj, B.:Greedy sparsity-constrained optimization. J. Mach. Learn. Res. 14, 807-841(2013)
[29] Yuan, X., Li, P., Zhang, T.:Gradient hard thresholding pursuit. J. Mach. Learn. Res. 18, 1-43(2018)
[30] Bertsekas, D.P.:Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1990)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016