×

zbMATH — the first resource for mathematics

Scalable semidefinite programming. (English) Zbl 07368784
MSC:
90C22 Semidefinite programming
65K05 Numerical mathematical programming methods
65F99 Numerical linear algebra
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P.-A. Absil, C. Baker, and K. Gallivan, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7 (2007), pp. 303-330. · Zbl 1129.65045
[2] A. Y. Alfakih, A. Khandani, and H. Wolkowicz, Solving Euclidean distance matrix completion problems via semidefinite programming, Comput. Optim. Appl., 12 (1999), pp. 13-30. · Zbl 1040.90537
[3] F. Alizadeh, Combinatorial Optimization with Interior Point Methods and Semi-Definite Matrices, Ph.D. thesis, University of Minnesota, 1991.
[4] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995), pp. 13-51. · Zbl 0833.90087
[5] 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
[6] 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
[7] Z. Allen-Zhu, Y. T. Lee, and L. Orecchia, Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver, https://arxiv.org/abs/1507.02259, 2015. · Zbl 1411.68180
[8] Z. Allen-Zhu and Y. Li, Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU, https://arxiv.org/abs/1701.01722, 2017.
[9] M. F. Anjos and J. B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012. · Zbl 1235.90002
[10] S. Arora, E. Hazan, and S. Kale, Fast algorithms for approximate semidefinite programming using the multiplicative weights update method, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, 2005, pp. 339-348.
[11] S. Arora and S. Kale, A combinatorial, primal-dual approach to semidefinite programs, J. ACM, 63 (2016), pp. 12:1-12:35. · Zbl 1426.68301
[12] D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Graph partitioning and graph clustering, in 10th DIMACS Implementation Challenge Workshop, 2012, https://www.cise.ufl.edu/research/sparse/matrices/DIMACS10/index.html. · Zbl 1262.05001
[13] M. Baes, M. Bürgisser, and A. Nemirovski, A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems, SIAM J. Optim., 23 (2013), pp. 934-962. · Zbl 1295.90039
[14] R. Balan, B. G. Bodmann, P. G. Casazza, and D. Edidin, Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl., 15 (2009), pp. 488-501. · Zbl 1181.42032
[15] R. Balan, P. Casazza, and D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20 (2006), pp. 345-356. · Zbl 1090.94006
[16] A. Barvinok, A Course in Convexity, AMS, Providence, RI, 2002. · Zbl 1014.52001
[17] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MOS-SIAM Ser. Optim. Z, SIAM, Philadelphia, 2001. · Zbl 0986.90032
[18] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Comput. Sci. Appl. Math., Academic Press, New York, 1982. · Zbl 0572.90067
[19] S. Bhojanapalli, N. Boumal, P. Jain, and P. Netrapalli, Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form, in Proceedings of the 31st Conference on Learning Theory, PMLR 75, 2018, pp. 3243-3270.
[20] N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, Manopt, a MATLAB toolbox for optimization on manifolds, J. Mach. Learn. Res., 15 (2014), pp. 1455-1459. · Zbl 1319.90003
[21] N. Boumal, V. Voroninski, and A. Bandeira, The non-convex Burer-Monteiro approach works on smooth semidefinite programs, in Advances in Neural Information Processing Systems 29, 2016, pp. 2757-2765.
[22] M. Brand, Fast low-rank modifications of the thin singular value decomposition, Linear Algebra Appl., 415 (2006), pp. 20 – 30. · Zbl 1088.65037
[23] J. F. S. Bravo Ferreira, Y. Khoo, and A. Singer, Semidefinite programming approach for the quadratic assignment problem with a sparse graph, Comput. Optim. Appl., 69 (2018), pp. 677-712. · Zbl 1415.90071
[24] 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
[25] S. Burer and R. D. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), pp. 427-444. · Zbl 1099.90040
[26] S. Burer and D. Vandenbussche, Solving lift-and-project relaxations of binary integer programs, SIAM J. Optim., 16 (2006), pp. 726-750. · Zbl 1113.90100
[27] R. E. Burkard, S. E. Karisch, and F. Rendl, QAPLIB-a quadratic assignment problem library, J. Global Optim., 10 (1997), pp. 391-403. · Zbl 0884.90116
[28] E. J. Candès, X. Li, and M. Soltanolkotabi, Phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 39 (2015), pp. 277 – 299. · Zbl 1329.78056
[29] Y. Carmon, J. C. Duchi, S. Aaron, and T. Kevin, A rank-1 sketch for matrix multiplicative weights, in Proceedings of the 32nd Conference on Learning Theory, PMLR 99, 2019, pp. 589-623.
[30] A. Chai, M. Moscoso, and G. Papanicolaou, Array imaging using intensity-only measurements, Inverse Problems, 27 (2010), 015005. · Zbl 1207.78022
[31] D. Cifuentes, Burer-Monteiro Guarantees for General Semidefinite Programs, https://arxiv.org/abs/1904.07147, 2019.
[32] K. L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, ACM Trans. Algorithms, 6 (2010), pp. 63:1-63:30. · Zbl 1300.90026
[33] J. L. Conrad, Marburg Virus Hemorrhagic Fever: Cytoarchitecture and Histopathology, https://pixnio.com/de/wissenschaft/mikroskopische-aufnahmen/hamorrhagisches-fieber-marburg-virus/cytoarchitectural-histopathologischen-erkannt-niere-probe-marburg-patient.
[34] C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming, 62 (1993), pp. 557-574. · Zbl 0797.90107
[35] C. Delorme and S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Math., 111 (1993), pp. 145-156. · Zbl 0786.05057
[36] L. Ding, A. Yurtsever, V. Cevher, J. A. Tropp, and M. Udell, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, https://arxiv.org/abs/1902.03373, 2019. · Zbl 1420.65060
[37] M. Fazel, Matrix Rank Minimization with Applications, Ph.D. thesis, Stanford University, Palo Alto, CA, 2002.
[38] J. R. Fienup, Phase retrieval algorithms: A comparison, Appl. Optics, 21 (1982), pp. 2758-2769.
[39] M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Res. Logist. Quart., 3 (1956), pp. 95-110.
[40] D. Garber and E. Hazan, Approximating semidefinite programs in sublinear time, in Advances in Neural Information Processing Systems 25, 2011. · Zbl 1346.90656
[41] D. Garber and E. Hazan, Sublinear time algorithms for approximate semidefinite programming, Math. Programming, 158 (2016), pp. 329-361. · Zbl 1346.90656
[42] G. Gidel, F. Pedregosa, and S. Lacoste-Julien, Frank-Wolfe splitting via augmented Lagrangian method, in Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, PMLR 84, 2018, pp. 1456-1465.
[43] A. Gittens, Topics in Randomized Numerical Linear Algebra, Ph.D. thesis, California Institute of Technology, Pasadena, 2013. · Zbl 1286.65054
[44] 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
[45] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217-288. · Zbl 1269.65043
[46] E. Hazan, Sparse approximate solutions to semidefinite programs, in LATIN 2008: Theoretical Informatics, 2008, pp. 306-316. · Zbl 1136.90430
[47] 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.
[48] R. Horstmeyer, R. Y. Chen, X. Ou, B. Ames, J. A. Tropp, and C. Yang, Solving ptychography with a convex relaxation, New J. Phys., 17 (2015), 053044.
[49] Q. Huang, Y. Chen, and L. Guibas, Scalable semidefinite relaxation for maximum a posterior estimation, in Proceedings of the 31st International Conference on Machine Learning, PMLR 32, 2014, pp. 64-72.
[50] M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in Proceedings of the 30th International Conference on Machine Learning, PMLR 28, 2013, pp. 427-435.
[51] L. K. Jones, A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training, Ann. Statist., 20 (1992), pp. 608-613. · Zbl 0746.62060
[52] R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, 38 (1987), pp. 325-340. · Zbl 0607.90056
[53] A. P. Kamath and N. K. Karmarkar, A continuous method for computing bounds in integer quadratic optimization problems, J. Global Optim., 2 (1991), pp. 229-241. · Zbl 0762.90058
[54] A. P. Kamath and N. K. Karmarkar, An \(O(nL)\) iteration algorithm for computing bounds in quadratic optimization problems, in Complexity in Numerical Optimization, World Scientific, River Edge, NJ, 1993, pp. 254-268. · Zbl 0968.90502
[55] R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Springer, New York, 1972, pp. 85-103.
[56] K. Krishnan and T. Terlaky, Interior point and semidefinite approaches in combinatorial optimization, in Graph Theory and Combinatorial Optimization, Springer, New York, 2005. · Zbl 1098.90089
[57] J. Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094-1122. · Zbl 0759.65016
[58] H. Kuhn, The Hungarian Method for the assignment problem, Naval Res. Logist. Quart., 2 (1955), pp. 83-97.
[59] B. Kulis, A. C. Surendran, and J. C. Platt, Fast low-rank semidefinite programming for embedding and clustering, in Proceedings of the 11th International Conference on Artificial Intelligence and Statistics, Vol. 2, San Juan, Puerto Rico, 2007, pp. 235-242.
[60] J. Lavaei and S. H. Low, Zero duality gap in optimal power flow problem, IEEE Trans. Power Syst., 27 (2012), pp. 92-107.
[61] Y. T. Lee and S. Padmanabhan, An \(\tilde{O}(m/\varepsilon^3.5)\)-cost algorithm for semidefinite programs with diagonal constraints, in Proceedings of the Conference on Learning Theory, 2020, pp. 3069-3119.
[62] R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, Software Environ. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[63] E. S. Levitin and B. T. Poljak, Minimization methods in the presence of constraints, Ž. Vyčisl. Mat. Mat. Fiz., 6 (1966), pp. 787-823.
[64] H. Li, G. C. Linderman, A. Szlam, K. P. Stanton, Y. Kluger, and M. Tygert, Algorithm 971: An implementation of a randomized algorithm for principal component analysis, ACM Trans. Math. Software, 43 (2017), 28. · Zbl 1391.65085
[65] Y.-F. Liu, X. Liu, and S. Ma, On the nonergodic convergence rate of an inexact augmented lagrangian framework for composite convex programming, Math. Oper. Res., 44 (2019), pp. 632-650. · Zbl 1441.90119
[66] E. M. Loiola, N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, A survey for the quadratic assignment problem, European J. Oper. Res., 176 (2007), pp. 657-690. · Zbl 1103.90058
[67] A. Majumdar, G. Hall, and A. A. Ahmadi, A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications to Machine Learning, Control, and Robotics, http://arXiv.org/abs/1908.05209, 2019.
[68] M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control, 42 (1997), pp. 239-243. · Zbl 0872.93029
[69] L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford Ser. (2), 11 (1960), pp. 50-59. · Zbl 0105.01101
[70] The MOSEK Optimization Toolbox for MATLAB Manual. Version 9.0, Mosek ApS, 2019.
[71] J. Munkres, Algorithms for the assignment and transportation problems, J. SIAM, 5 (1957), pp. 32-38. · Zbl 0083.15302
[72] A. Nemirovski, Prox-method with rate of convergence \(O(1/t)\) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15 (2004), pp. 229-251. · Zbl 1106.90059
[73] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, New York, 2004. · Zbl 1086.90045
[74] Y. Nesterov, Primal-dual subgradient methods for convex problems, Math. Program., 120 (2009), pp. 221-259. · Zbl 1191.90038
[75] Y. Nesterov and A. Nemirovski, Self-Concordant Functions and Polynomial Time Methods in Convex Programming, Central Economic & Mathematic Institute report, USSR Academy of Sciences, 1990.
[76] Y. Nesterov and A. Nemirovski, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, 1994.
[77] B. N. Parlett, The symmetric eigenvalue problem, Classics in Appl. Math. 20, SIAM, Philadelphia, 1998, https://doi.org/10.1137/1.9781611971163. · Zbl 0885.65039
[78] P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, 2000.
[79] 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
[80] R. Peng and K. Tangwongsan, Faster and simpler width-independent parallel algorithms for positive semidefinite programming, in Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2012, pp. 101-108.
[81] T. Pumir, S. Jelassi, and N. Boumal, Smoothed analysis of the low-rank approach for smooth semidefinite programs, in Advances in Neural Information Processing Systems 31, 2018, pp. 2281-2290.
[82] A. Raghunathan, J. Steinhardt, and P. Liang, Semidefinite relaxations for certifying robustness to adversarial examples, in Advances in Neural Information Processing Systems 31, 2018, pp. 10900-10910.
[83] G. Reinelt, TSPLIB, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
[84] D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard, SE-sync: A certifiably correct algorithm for synchronization over the special euclidean group, Int. J. Robot. Res., 38 (2019), pp. 95-125.
[85] M. F. Sahin, A. Eftekhari, A. Alacaoglu, F. Latorre, and V. Cevher, An inexact augmented Lagrangian framework for nonconvex optimization with nonlinear constraints, in Advances in Neural Information Processing Systems 32, 2019, pp. 13965-13977.
[86] S. Sahni and T. Gonzalez, P-complete approximation problems, J. ACM, 23 (1976), pp. 555-565. · Zbl 0348.90152
[87] A. Silveti-Falls, C. Molinari, and J. Fadili, Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization, https://arxiv.org/abs/1901.01287, 2019. · Zbl 1450.65054
[88] M. Souto, J. D. Garcia, and A. Veiga, Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting, https://arxiv.org/abs/1810.05231, 2018.
[89] N. Srebro, Learning with Matrix Factorizations, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, 2004.
[90] J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12 (1999), pp. 625-653. · Zbl 0973.90526
[91] Y. Sun, Y. Guo, J. A. Tropp, and M. Udell, Tensor random projection for low memory dimension reduction, in NeurIPS Workshop on Relational Representation Learning, 2018.
[92] K. A. Toh, M. J. Todd, and R. H. Tütüncü, SDPT3-a Matlab software package for semidefinite programming, optimization methods and software, Optim. Methods Softw., 11 (1999), pp. 545-581. · Zbl 0997.90060
[93] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Fixed-rank approximation of a positive-semidefinite matrix from streaming data, in Advances in Neural Information Processing Systems 30, 2017, pp. 1225-1234. · Zbl 1379.65026
[94] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Practical sketching algorithms for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1454-1485. · Zbl 1379.65026
[95] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Streaming low-rank matrix approximation with an application to scientific simulation, SIAM J. Sci. Comput., 41 (2019), pp. A2430-A2463. · Zbl 1420.65060
[96] K. Tsuda, G. Rätsch, and M. K. Warmuth, Matrix exponentiated gradient updates for on-line learning and Bregman projections, J. Mach. Learn. Res., 6 (2005), pp. 995-1018. · Zbl 1222.68322
[97] I. Waldspurger and A. Waters, Rank optimality for the Burer-Monteiro factorization, https://arxiv.org/abs/1812.03046, 2018. · Zbl 1451.90114
[98] Z. Wen, D. Goldfarb, S. Ma, and K. Scheinberg, Row by Row Methods for Semidefinite Programming, IEOR report, Columbia University, 2009.
[99] Z. Wen, D. Goldfarb, and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), pp. 203-230. · Zbl 1206.90088
[100] L. Yang, D. Sun, and K.-C. Toh, SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Progam. Comput., 7 (2015), pp. 331-366. · Zbl 1321.90085
[101] Y. Ye, GSet Random Graphs, https://www.cise.ufl.edu/research/sparse/matrices/Gset/.
[102] A. Yurtsever, O. Fercoq, and V. Cevher, A conditional-gradient-based augmented Lagrangian framework, in Proceedings of the 36th International Conference on Machine Learning, PMLR 97, 2019, pp. 7272-7281.
[103] A. Yurtsever, O. Fercoq, F. Locatello, and V. Cevher, A conditional gradient framework for composite convex minimization with applications to semidefinite programming, in Proceedings of the 35th International Conference on Machine Learning, PMLR 80, 2018, pp. 5727-5736.
[104] A. Yurtsever, Y.-P. Hsieh, and V. Cevher, Scalable convex methods for phase retrieval, in Proceedings of the 6th International IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2015, pp. 381-384.
[105] A. Yurtsever, Q. Tran Dinh, and V. Cevher, A universal primal-dual convex optimization framework, in Advances in Neural Information Processing Systems 28, 2015, pp. 3150-3158.
[106] A. Yurtsever, M. Udell, J. Tropp, and V. Cevher, Sketchy decisions: Convex low-rank matrix optimization with optimal storage, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR, 54, 2017, pp. 1188-1196.
[107] M. Zaslavskiy, F. Bach, and J. Vert, A path following algorithm for the graph matching problem, IEEE Trans. Pattern Anal. Mach. Intel., 31 (2009), pp. 2227-2242.
[108] Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem, J. Combin. Optim., 2 (1998), pp. 71-109. · Zbl 0904.90145
[109] X.-Y. Zhao, D. Sun, and K.-C. Toh, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20 (2010), pp. 1737-1765. · Zbl 1213.90175
[110] G. Zheng, R. Horstmeyer, and C. Yang, Wide-field, high-resolution Fourier ptychography microscopy, Nat. Photonics, 7 (2013), pp. 739-745.
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.