×

A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion. (English) Zbl 1479.90152

Summary: A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. The convergence of the method is established. A prototype implementation is discussed and encouraging preliminary computational results are reported for solving the SDP-reformulation of matrix-completion problems.

MSC:

90C22 Semidefinite programming
90C51 Interior-point methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andersen, M., Dahl, J., Liu, Z., Vandenberghe, L.: Interior-Point Methods for Large-scale Cone Programming, pp. 55-83. MIT Press (2011)
[2] Anjos, M., Lasserre, J.: Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operational Research and Management Science (2012) · Zbl 1235.90002
[3] Barzilai, J.; Borwein, J., Two point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[4] Bellavia, S.; Gondzio, J.; Porcelli, M., An inexact dual logarithmic barrier method for solving sparse semidefinite programs, Math. Program., 178, 109-143 (2019) · Zbl 1431.90108 · doi:10.1007/s10107-018-1281-5
[5] Benson, SJ; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim., 10, 443-461 (2000) · Zbl 0997.90059 · doi:10.1137/S1052623497328008
[6] Boumal, N.; Voroninski, V.; Bandeira, A., The non-convex Burer-Monteiro approach works on smooth semidefinite programs, Adv. Neural Inf. Process. Syst., 29, 2757-2765 (2016)
[7] Boumal, N., Voroninski, V., Bandeira, A.S.: Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs (2018). arXiv preprint arXiv:1804.02008 · Zbl 1445.90074
[8] Burer, S.; Monteiro, RDC, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 329-357 (2003) · Zbl 1030.90077 · doi:10.1007/s10107-002-0352-8
[9] Burer, S.; Monteiro, RDC, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103, 427-444 (2005) · Zbl 1099.90040 · doi:10.1007/s10107-004-0564-1
[10] Burkardt, J.: Cities—City Distance Datasets. http://people.sc.fsu.edu/ burkardt/datasets/cities/cities.html
[11] Cai, J-F; Candès, EJ; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[12] Candes, EJ; Plan, Y., Matrix completion with noise, Proc. IEEE, 98, 925-936 (2010) · doi:10.1109/JPROC.2009.2035722
[13] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[14] Chen, C.; He, B.; Yuan, X., Matrix completion via an alternating direction method, IMA J. Numer. Anal., 32, 227-245 (2012) · Zbl 1236.65043 · doi:10.1093/imanum/drq039
[15] De Klerk, E., Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (2006), Berlin: Springer, Berlin · Zbl 0991.90098
[16] de Klerk, E.; Peng, J.; Roos, C.; Terlaky, T., A scaled Gauss-Newton primal-dual search direction for semidefinite optimization, SIAM J. Optim., 11, 870-888 (2001) · Zbl 1001.65060 · doi:10.1137/S1052623499352632
[17] di Serafino, D., Ruggiero, V., Toraldo, G., Zanni, L.: On the Steplength Selection in Gradient Methods for Unconstrained Optimization, Applied Mathematics and Computation, vol. 318, pp. 176 - 195. Recent Trends in Numerical Computations: Theory and Algorithms (2018) · Zbl 1426.65082
[18] Fackler, P.L.: Notes on Matrix Calculus. Privately Published (2005)
[19] Fazel, M., Hindi, H., Boyd, S.P., A rank minimization heuristic with application to minimum order system approximation. In: American Control Conference: Proceedings of the 2001, vol. 6, pp. 4734-4739 (2001)
[20] Fujisawa, K.; Kojima, M.; Nakata, K., Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Math. Program., 79, 235-253 (1997) · Zbl 0887.90156
[21] Gillberg, J., Hansson, A.: Polynomial complexity for a Nesterov-Todd potential reduction method with inexact search directions. In: Proceedings of the 42nd IEEE Conference on Decision and Control, vol. 3, pp. 3824-3829. IEEE (2003)
[22] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[23] Grapiglia, GN; Sachs, EW, On the worst-case evaluation complexity of non-monotone line search algorithms, Comput. Optim. Appl., 68, 555-577 (2017) · Zbl 1388.90111 · doi:10.1007/s10589-017-9928-3
[24] Güler, O.; Ye, Y., Convergence behavior of interior-point algorithms, Math. Program., 60, 215-228 (1993) · Zbl 0803.90087 · doi:10.1007/BF01580610
[25] Hestenes, MR, Pseudoinversus and conjugate gradients, Commun. ACM, 18, 40-43 (1975) · Zbl 0304.65029 · doi:10.1145/360569.360658
[26] Huang, S.; Wolkowicz, H., Low-rank matrix completion using nuclear norm minimization and facial reduction, J. Glob. Optim., 72, 5-26 (2018) · Zbl 1475.65036 · doi:10.1007/s10898-017-0590-1
[27] Ji, H., O’Saben, E., Boudion, A., Li, Y.: March madness prediction: a matrix completion approach. In: Proceedings of Modeling, Simulation, and Visualization Student Capstone Conference, pp. 41-48 (2015)
[28] Keshavan, R-H; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Trans. Inf. Theory, 56, 2980-2998 (2010) · Zbl 1366.62111 · doi:10.1109/TIT.2010.2046205
[29] Keshavan, R.-H., Oh, S.: Optspace: a gradient descent algorithm on the Grassmann manifold for matrix completion (2009). arXiv preprint arXiv:0910.5260
[30] Kocvara, M.; Stingl, M., On the solution of large-scale SDP problems by the modified barrier method using iterative solvers, Math. Program., 109, 413-444 (2007) · Zbl 1177.90312 · doi:10.1007/s10107-006-0029-9
[31] Koh, K.; Kim, S-J; Boyd, S., An interior-point method for large-scale \(\ell 1\)-regularized logistic regression, J. Mach. Learn. Res., 8, 1514-1555 (2007) · Zbl 1222.62092
[32] Kruk, S.; Muramatsu, M.; Rendl, F.; Vanderbei, RJ; Wolkowicz, H., The Gauss-Newton direction in semidefinite programming, Optim. Methods Softw., 15, 1-28 (2001) · Zbl 1017.90076 · doi:10.1080/10556780108805808
[33] Lee, K.; Bresler, Y., Admira: atomic decomposition for minimum rank approximation, IEEE Trans. Inf. Theory, 56, 4402-4416 (2010) · Zbl 1366.94112 · doi:10.1109/TIT.2010.2054251
[34] Lemon, A.; So, AM-C; Ye, Y., Low-rank semidefinite programming: theory and applications, foundations and trends®, Optimization, 2, 1-156 (2016)
[35] Lin, Z., Chen, M., Ma, Y.: The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices (2010). arXiv preprint arXiv:1009.5055
[36] Liu, Z.; Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 1235-1256 (2009) · Zbl 1201.90151 · doi:10.1137/090755436
[37] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128, 321-353 (2011) · Zbl 1221.65146 · doi:10.1007/s10107-009-0306-5
[38] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[39] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[40] Todd, MJ, Semidefinite optimization, Acta Numer., 2001, 10, 515-560 (2001) · Zbl 1105.65334 · doi:10.1017/S0962492901000071
[41] Toh, K-C; Kojima, M., Solving some large scale semidefinite programs via the conjugate residual method, SIAM J. Optim., 12, 669-691 (2002) · Zbl 1008.90043 · doi:10.1137/S1052623400376378
[42] Toh, K-C; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6, 15 (2010) · Zbl 1205.90218
[43] Vandenberghe, L.; Andersen, MS, Chordal graphs and semidefinite optimization, Found. Trends Optim., 1, 241-433 (2015) · doi:10.1561/2400000006
[44] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[45] Xu, Y.; Yin, W.; Wen, Z.; Zhang, Y., An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China, 7, 365-384 (2012) · Zbl 1323.65044 · doi:10.1007/s11464-012-0194-5
[46] Zhang, R. Y. , Lavaei, J.: Modified interior-point method for large-and-sparse low-rank semidefinite programs. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 5640-5647. IEEE (2017)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.