×

Optimality conditions for rank-constrained matrix optimization. (English) Zbl 1438.90272

Summary: 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.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming

Software:

MSCRA_rankmin
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Le, HY, A variational approach of the rank function, J. Span. Soc. Stat. Oper. Res., 7, 207-240, (2013) · Zbl 1269.49019
[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, BK, Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234, (1995) · Zbl 0827.68054
[5] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[6] Chen, YQ; Xiu, NH; Peng, DT, Global solutions of non-Lipschitz \(S_2\)-\(S_p\) minimization over the positive semidefinite cone, Optim. Lett., 8, 2053-2064, (2014) · Zbl 1326.90063
[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, ZS; Zhang, Y.; Li, XR, Penalty decomposition methods for rank minimization, Optim. Methods Softw., 30, 531-558, (2015) · Zbl 1323.65070
[10] Delgado, RA; Aguero, JC; Goodwin, GC, A rank-constrained optimization approach: application to factor analysis, IFAC Proc. Vol., 47, 10373-10378, (2014)
[11] Wen, ZW; Yin, WT; Zhang, Y., Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4, 333-361, (2012) · Zbl 1271.65083
[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/323 945500 (2018)
[14] Cason, TP; Absil, PA; Dooren, P., Iterative methods for low rank approximation of graph similarity matrices, Linear Algebra Appl., 438, 1863-1882, (2013) · Zbl 1264.65060
[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, 622-646, (2015) · Zbl 1355.65079
[16] Zhou, G.F.: Rank-Constrained Optimization: A Riemannian Manifold Approach. PhD thesis, Florida State University (2015)
[17] Zhou, GF; Huang, W.; Gallivan, KA; Dooren, PV; Absil, PA, A Riemannian rank-adaptive method for low-rank optimization, Neurocomputing, 192, 72-80, (2016)
[18] Luke, DR, Prox-regularity of rank constraint sets and implications for algorithms, J. Math. Imaging Vis., 47, 231-238, (2013) · Zbl 1311.90142
[19] Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, New York (2013) · Zbl 1267.15001
[20] Hiriart-Urruty, JB; Le, HY, From Eckart and Young approximation to Moreau envelopes and vice versa, Rairo Recherche Operationnelle, 47, 299-310, (2013) · Zbl 1326.15032
[21] Helmke, U.; Shayman, MA, Critical points of matrix least squares distance functions, Linear Algebra Appl., 215, 1-19, (1995) · Zbl 0816.15026
[22] Rockafellar, R.T., Wets, R.J.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[23] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I: Basic Theory, II: Applications. Springer, Berlin (2006) · Zbl 1100.49002
[24] Guttman, L., Enlargement methods for computing the inverse matrix, Ann. Math. Stat., 17, 336-343, (1946) · Zbl 0061.27203
[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) · Zbl 1295.90051
[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) · Zbl 1331.62350
[28] Bahmani, S.; Boufounos, P.; Raj, B., Greedy sparsity-constrained optimization, J. Mach. Learn. Res., 14, 807-841, (2013) · Zbl 1320.90046
[29] Yuan, X.; Li, P.; Zhang, T., Gradient hard thresholding pursuit, J. Mach. Learn. Res., 18, 1-43, (2018) · Zbl 1471.90114
[30] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.