×

zbMATH — the first resource for mathematics

Solving rank-constrained semidefinite programs in exact arithmetic. (English) Zbl 1380.90212
Summary: We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix, or the dimension of the affine section, is fixed, the algorithm is polynomial time. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We implement it in Maple and discuss practical experiments.

MSC:
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anjos, M. F.; Lasserre, J.-B., Handbook on semidefinite, conic and polynomial optimization, International Series in Operations Research & Management Science, vol. 166, (2012), Springer US · Zbl 1235.90002
[2] Ben-Tal, A.; Nemirovski, A., Lectures on modern convex optimization: analysis, algorithms, and engineering applications, vol. 2, (2001), Siam · Zbl 0986.90032
[3] Blekherman, G.; Plaumann, D.; Sinn, R.; Vinzant, C., Low-rank sum-of-squares representations on varieties of minimal degree, (2016), arXiv preprint
[4] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear matrix inequalities in system and control theory, vol. 15, (1994), SIAM · Zbl 0816.93004
[5] Chua, L.; Plaumann, D.; Sinn, R.; Vinzant, C., Gram spectrahedra, (2016), arXiv preprint · Zbl 1390.14176
[6] Cox, D.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra, (2007), Springer · Zbl 1118.13001
[7] Eisenbud, D., Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics, vol. 150, (1995), Springer-Verlag · Zbl 0819.13001
[8] Faugère, J.; Safey El Din, M.; Spaenlehauer, P., Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology, (ISSAC’10, (2010), ACM), 134-141 · Zbl 1321.68529
[9] Faugère, J.-C., Fgb: a library for computing Gröbner bases, (Mathematical Software - ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010, Proceedings, (2010), Springer Berlin Heidelberg Berlin, Heidelberg), 84-87 · Zbl 1294.68156
[10] Faugère, J.-C.; Mou, C., Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, (2011), ACM), 115-122 · Zbl 1323.68596
[11] Goemans, M.; Williamson, D., Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145, (1995) · Zbl 0885.68088
[12] Greuet, A.; Safey El Din, M., Probabilistic algorithm for the global optimization of a polynomial over a real algebraic set, SIAM J. Optim., 24, 3, 1313-1343, (2014) · Zbl 1327.90232
[13] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer · Zbl 0634.05001
[14] Henrion, D.; Naldi, S.; Safey El Din, M., Real root finding for determinants of linear matrices, J. Symb. Comput., 74, 205-238, (2015) · Zbl 1329.65090
[15] Henrion, D.; Naldi, S.; Safey El Din, M., Real root finding for low rank linear matrices, (2015), LAAS-CNRS Research Report 15731 · Zbl 1345.65024
[16] Henrion, D.; Naldi, S.; Safey El Din, M., Real root finding for rank defects in linear Hankel matrices, (Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation, Bath (UK), (2015)), 221-228 · Zbl 1345.65024
[17] Henrion, D.; Naldi, S.; Safey El Din, M., Exact algorithms for linear matrix inequalities, SIAM J. Optim., 26, 4, 2512-2539, (2016) · Zbl 1356.90102
[18] Henrion, D.; Naldi, S.; Safey El Din, M., Spectra: a Maple library for solving linear matrix inequalities in exact arithmetic, Optim. Methods Softw, (2016), In press
[19] Jeronimo, G.; Matera, G.; Solernó, P.; Waissbein, A., Deformation techniques for sparse systems, Found. Comput. Math., 9, 1, 1-50, (2009) · Zbl 1167.14039
[20] Khachiyan, L.; Porkolab, L., On the complexity of semidefinite programs, J. Glob. Optim., 10, 4, 351-365, (1997) · Zbl 0881.90127
[21] Lasserre, J.-B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817, (2001) · Zbl 1010.90061
[22] Laurent, M.; Nagy, M.; Varvitsiotis, A., Complexity of the positive semidefinite matrix completion problem with a rank constraint, (Bezdek, K.; Deza, A.; Ye, Y., Discrete Geometry and Optimization, Fields Institute Communications, vol. 69, (2013)), 105-120 · Zbl 1272.68140
[23] Naldi, S., Solving rank-constrained semidefinite programs in exact arithmetic, (Proceedings of the 41th International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, (2016)), 357-364 · Zbl 1360.90190
[24] Nesterov, Y.; Nemirovsky, A., Interior-point polynomial algorithms in convex programming, Studies in Applied Mathematics, vol. 13, (1994), SIAM Philadelphia · Zbl 0824.90112
[25] Nie, J., Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program., Ser. A, 146, 97-121, (2014) · Zbl 1300.65041
[26] Nie, J.; Ranestad, K.; Sturmfels, B., The algebraic degree of semidefinite programming, Math. Program., 122, 2, 379-405, (2010) · Zbl 1184.90119
[27] Orsi, R.; Helmke, U.; Moore, J., A Newton-like method for solving rank constrained linear matrix inequalities, Automatica, 42, 11, 1875-1882, (2006) · Zbl 1222.90032
[28] Pan, V.; Tsigaridas, E., Nearly optimal refinement of real roots of a univariate polynomial, J. Symb. Comput., 74, 181-204, (2015) · Zbl 1329.65096
[29] Parrilo, P., Semidefinite programming relaxations for semialgebraic problems, Math. Program., Ser. B, 96, 2, 293-320, (2003) · Zbl 1043.14018
[30] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461, (1999) · Zbl 0932.12008
[31] Safey El Din, M.; Schost, E., A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets, J. ACM, 63, 48, (2017) · Zbl 1426.68311
[32] Shafarevich, I., Basic algebraic geometry 1, (1977), Springer Verlag · Zbl 0362.14001
[33] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 1, 49-95, (1996) · Zbl 0845.65023
[34] Woermann, T.; Powers, V., An algorithm for sums of squares of real polynomials, J. Pure Appl. Algebra, 127, 99-104, (1998) · Zbl 0936.11023
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.