Optimality Conditions for Rank-Constrained Matrix Optimization

doi:10.1007/s40305-019-00245-0

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 285-301.doi: 10.1007/s40305-019-00245-0

Special Issue: Continuous Optimization

Previous Articles Next Articles

Optimality Conditions for Rank-Constrained Matrix Optimization

Xin-Rong Li¹, Wen Song², Nai-Hua Xiu¹

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

Received:2018-05-30 Revised:2019-01-11 Online:2019-06-30 Published:2019-06-30
Contact: Xin-Rong Li, Wen Song, Nai-Hua Xiu E-mail:lixinrong0827@163.com;wsong@hrbnu.edu.cn;nhxiu@bjtu.edu.cn
Supported by:
This research was supported by the National Natural Science Foundation of China (Nos. 11431002 and 11371116).

Abstract

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

CLC Number:

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.

TrendMD

References 30

[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)

Optimality Conditions for Rank-Constrained Matrix Optimization

PDF

Knowledge

Abstract

Cite this article

share this article

References 30

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Xue Li· Wen Song. The First-Order Necessary Conditions for Sparsity Constrained Optimization [J]. Journal of the Operations Research Society of China, 2015, 3(4): 521-.
[2]	Li-Li Pan · Nai-Hua Xiu1· Sheng-Long Zhou. On Solutions of Sparsity Constrained Optimization [J]. Journal of the Operations Research Society of China, 2015, 3(4): 421-.
[3]	Hou-Duo Qi. Conditional Quadratic Semidefinite Programming:Examples and Methods [J]. Journal of the Operations Research Society of China, 2014, 2(2): 143-170.