## 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

### Software:

 [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 [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 [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 [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 [9] Burer, S.; Monteiro, RDC, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103, 427-444 (2005) · Zbl 1099.90040 [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 [12] Candes, EJ; Plan, Y., Matrix completion with noise, Proc. IEEE, 98, 925-936 (2010) [13] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2009) · Zbl 1219.90124 [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 [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 [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 [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 [24] Güler, O.; Ye, Y., Convergence behavior of interior-point algorithms, Math. Program., 60, 215-228 (1993) · Zbl 0803.90087 [25] Hestenes, MR, Pseudoinversus and conjugate gradients, Commun. ACM, 18, 40-43 (1975) · Zbl 0304.65029 [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 [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 [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 [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) [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 [33] Lee, K.; Bresler, Y., Admira: atomic decomposition for minimum rank approximation, IEEE Trans. Inf. Theory, 56, 4402-4416 (2010) · Zbl 1366.94112 [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 [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 [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 [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 [40] Todd, MJ, Semidefinite optimization, Acta Numer., 2001, 10, 515-560 (2001) · Zbl 1105.65334 [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 [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) [44] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95 (1996) · Zbl 0845.65023 [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 [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)