On the simplicity and conditioning of low rank semidefinite programs. (English) Zbl 1479.90154


90C22 Semidefinite programming
90C06 Large-scale problems in mathematical programming
49M05 Numerical methods based on necessary conditions
Full Text: DOI arXiv


[1] University of Florida Sparse Matrix Collection: Gset Group, https://www.cise.ufl.edu/research/sparse/matrices/Gset/index.html, 2020.
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2009. · Zbl 1147.65043
[3] F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, Complementarity and nondegeneracy in semidefinite programming, Math. Program., 77 (1997), pp. 111-128. · Zbl 0890.90141
[4] F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Optim., 8 (1998), pp. 746-768. · Zbl 0911.65047
[5] A. S. Bandeira, Random Laplacian matrices and convex relaxations, Found. Comput. Math., 18 (2018), pp. 345-379. · Zbl 1386.15065
[6] A. S. Bandeira, N. Boumal, and V. Voroninski, On the low-rank approach for semidefinite programs arising in synchronization and community detection, in Conference on Learning Theory, 2016, pp. 361-382.
[7] A. I. Barvinok, Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13 (1995), pp. 189-202. · Zbl 0829.05025
[8] D. P. Bertsekas, Convex Optimization Theory, Athena Scientific, Belmont, MA, 2009. · Zbl 1242.90001
[9] N. Boumal, P.-A. Absil, and C. Cartis, Global rates of convergence for nonconvex optimization on manifolds, IMA J. Numer. Anal., 39 (2018), pp. 1-33. · Zbl 1483.65092
[10] N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, preprint, arXiv:1804.02008, 2018. · Zbl 1445.90074
[11] S. Burer and R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329-357. · Zbl 1030.90077
[12] E. Candes and T. Tao, The power of matrix completion: Near-optimal convex relaxation, IEEE Trans. Inform. Theory, 56 (2010), pp. 2053-2080. · Zbl 1366.15021
[13] E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717. · Zbl 1219.90124
[14] E. J. Candes, T. Strohmer, and V. Voroninski, Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66 (2013), pp. 1241-1274. · Zbl 1335.94013
[15] A. Chai, M. Moscoso, and G. Papanicolaou, Array imaging using intensity-only measurements, Inverse Problems, 27 (2010), 015005. · Zbl 1207.78022
[16] Z. X. Chan and D. Sun, Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming, SIAM J. Optim., 19 (2008), pp. 370-396. · Zbl 1190.90116
[17] Y. Chen, Incoherence-optimal matrix completion, IEEE Trans. Inform. Theory, 61 (2015), pp. 2909-2923. · Zbl 1359.15022
[18] M. Cucuringu, Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization, IEEE Trans. Network Sci. Eng., 3 (2016), pp. 58-79.
[19] M. Cucuringu, Y. Lipman, and A. Singer, Sensor network localization by eigenvector synchronization over the Euclidean group, ACM Trans. Sensor Netw., 8 (2012), pp. 1-42.
[20] L. Ding and Y. Chen, The Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis, preprint, arXiv:1803.07554, 2018.
[21] L. Ding and M. Udell, A Strict Complementarity Approach to Error Bound and Sensitivity of Solution of Conic Programs, preprint, arXiv:2012.00183, 2020.
[22] L. Ding, A. Yurtsever, V. Cevher, J. A. Tropp, and M. Udell, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, preprint, arXiv:1902.03373, 2019.
[23] D. Drusvyatskiy, A. D. Ioffe, and A. S. Lewis, Generic minimizing behavior in semialgebraic optimization, SIAM J. Optim., 26 (2016), pp. 513-534. · Zbl 1334.49057
[24] D. Drusvyatskiy and A. S. Lewis, Generic nondegeneracy in convex optimization, Proc. Amer. Math. Soc., (2011), pp. 2519-2527. · Zbl 1220.49011
[25] D. Drusvyatskiy and A. S. Lewis, Error bounds, quadratic growth, and linear convergence of proximal methods, Math. Oper. Res., 43 (2018), pp. 919-948. · Zbl 1440.90046
[26] M. Fazel, Matrix Rank Minimization with Applications, Ph.D. dissertation, Stanford University, Stanford, CA, 2002.
[27] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[28] A. J. Goldman and A. W. Tucker, Theory of linear programming, Linear Inequal. Relat. Syst., 38 (1956), pp. 53-97. · Zbl 0072.37601
[29] D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57 (2011), pp. 1548-1566. · Zbl 1366.94103
[30] M. Halická, E. de Klerk, and C. Roos, On the convergence of the central path in semidefinite optimization, SIAM J. Optim., 12 (2002), pp. 1090-1099. · Zbl 1035.90100
[31] S. Homer and M. Peinado, Design and performance of parallel and distributed approximation algorithms for maxcut, J. Parallel Distrib. Comput., 46 (1997), pp. 48-61.
[32] P. R. Johnstone and P. Moulin, Faster Subgradient Methods for Functions with Holderian Growth, preprint, arXiv:1704.00196, 2017. · Zbl 1461.65161
[33] X. Li, Y. Chen, and J. Xu, Convex Relaxation Methods for Community Detection, preprint, arXiv:1810.00315, 2018.
[34] Z.-Q. Luo, J. F. Sturm, and S. Zhang, Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming, SIAM J. Optim., 8 (1998), pp. 59-81. · Zbl 0910.90229
[35] A. Mosek, The Mosek Optimization Software, http://www.mosek.com, 2010.
[36] M. V. Nayakkankuppam and M. L. Overton, Conditioning of semidefinite programs, Math. Program., 85 (1999), pp. 525-540. · Zbl 0973.90056
[37] Y. Nesterov, Lectures on Convex Optimization, Vol. 137, Springer, New York, 2018. · Zbl 1427.90003
[38] G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23 (1998), pp. 339-358. · Zbl 0977.90051
[39] B. Recht, A simpler approach to matrix completion, J. Mach. Learn. Res., 12 (2011), pp. 3413-3430. · Zbl 1280.68141
[40] S. M. Robinson, Strongly regular generalized equations, Math. Oper. Res., 5 (1980), pp. 43-62. · Zbl 0437.90094
[41] S. M. Robinson, Constraint nondegeneracy in variational analysis, Math. Oper. Res., 28 (2003), pp. 201-232. · Zbl 1082.90116
[42] N. Srebro and A. Shraibman, Rank, trace-norm and max-norm, in International Conference on Computational Learning Theory, Springer, New York, 2005, pp. 545-560. · Zbl 1137.68563
[43] J. F. Sturm, Error bounds for linear matrix inequalities, SIAM J. Optim., 10 (2000), pp. 1228-1248. · Zbl 0999.90027
[44] K.-C. Toh, M. J. Todd, and R. H. Tütüncü, Sdpt \(3\)—A MATLAB software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11 (1999), pp. 545-581. · Zbl 0997.90060
[45] M. Udell and A. Townsend, Why are big data matrices approximately low rank?, SIAM J. Math. Data Sci., 1 (2019), pp. 144-160.
[46] I. Waldspurger, A. d’Aspremont, and S. Mallat, Phase recovery, maxcut and complex semidefinite programming, Math. Program., 149 (2015), pp. 47-81. · Zbl 1329.94018
[47] I. Waldspurger and A. Waters, Rank Optimality for the Burer-Monteiro Factorization, preprint, arXiv:1812.03046, 2018. · Zbl 1451.90114
[48] Z. Zhou and A. M.-C. So, A unified approach to error bounds for structured convex optimization problems, Math. Program., 165 (2017), pp. 689-728. · Zbl 1380.65109
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.