×

Exact algorithms for semidefinite programs with degenerate feasible set. (English) Zbl 1460.90128

Summary: Given symmetric matrices \(A_0, A_1, \ldots, A_n\) of size \(m\) with rational entries, the set of real vectors \(x = ( x_1, \ldots, x_n)\) such that the matrix \(A_0 + x_1 A_1 + \cdots + x_n A_n\) has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either \(n\) or \(m\) is fixed.

MSC:

90C22 Semidefinite programming
68W30 Symbolic computation and algebraic computation
90C51 Interior-point methods
90C05 Linear programming
90C60 Abstract computational complexity for mathematical programming problems
13P15 Solving polynomial systems; resultants
14P10 Semialgebraic sets and related spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allamigeon, X.; Benchimol, P.; Gaubert, S.; Joswig, M., Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geom., 2, 1, 140-178 (2018) · Zbl 1391.90637
[2] Allamigeon, X.; Gaubert, S.; Skomra, M., Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, J. Symb. Comput., 85, 25-54 (2018) · Zbl 1379.90021
[3] Andersen, E. D.; Andersen, K. D., The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, (High Performance Optimization (2000), Springer), 197-232 · Zbl 1028.90022
[4] Anjos, M. F.; Lasserre, J. B., Introduction to semidefinite, conic and polynomial optimization, (Handbook on Semidefinite, Conic and Polynomial Optimization (2012), Springer), 1-22 · Zbl 1334.90095
[5] Bank, B.; Giusti, M.; Heintz, J.; Safey El Din, M., Intrinsic complexity estimates in polynomial optimization, J. Complex., 30, 4, 430-443 (2014) · Zbl 1302.65296
[6] Basu, S.; Pollack, R.; Roy, M-F., A new algorithm to find a point in every cell defined by a family of polynomials, (Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer-Verlag) · Zbl 0900.68278
[7] Basu, S.; Pollack, R.; Roy, M-F., Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2006), Springer-Verlag
[8] Blekherman, G.; Parrilo, P.; Thomas, R., Semidefinite Optimization and Convex Algebraic Geometry (2012), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA
[9] Bochnak, J.; Coste, M.; Roy, M-F., Real Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 36 (1998), Springer-Verlag · Zbl 0633.14016
[10] Borwein, J.; Wolkowicz, H., Regularizing the abstract convex program, J. Math. Anal. Appl., 83, 2, 495-530 (1981) · Zbl 0467.90076
[11] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory, vol. 15 (1994), Siam · Zbl 0816.93004
[12] Demazure, M., Bifurcations and Catastrophes: Geometry of Solutions to Nonlinear Problems (2013), Springer Science & Business Media
[13] Drusvyatskiy, D.; Wolkowicz, H., The many faces of degeneracy in conic optimization, Found. Trends Optim., 3, 2, 77-170 (2017)
[14] Faugère, J-C., Mathematical software - ICMS 2010, (Third International Congress on Mathematical Software, Proceedings. Third International Congress on Mathematical Software, Proceedings, Kobe, Japan, September 13-17, 2010 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 84-87, Chapter FGb: a Library for Computing Gröbner Bases
[15] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner-free alternative for polynomial system solving, J. Complex., 17, 1, 154-211 (2001) · Zbl 1003.12005
[16] Guo, Q.; Safey El Din, M.; Zhi, L., Computing rational solutions of linear matrix inequalities, (ISSAC’13 (2013)), 197-204 · Zbl 1360.68934
[17] 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
[18] 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
[19] Henrion, D.; Naldi, S.; Safey El Din, M., Exact algorithms for semidefinite programs with degenerate feasible set, (Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC’18) (2018), ACM: ACM New York, NY, USA), 191-198 · Zbl 1467.90031
[20] Henrion, D.; Naldi, S.; Safey El Din, M., SPECTRA-a Maple library for solving linear matrix inequalities in exact arithmetic, Optim. Methods Softw., 34, 1, 62-78 (2019)
[21] Herman, A.; Hong, H.; Tsigaridas, E., Improving root separation bounds, J. Symb. Comput., 84, 25-56 (2018) · Zbl 1415.26005
[22] Joldes, M.; Muller, J-M.; Popescu, V., Implementation and performance evaluation of an extended precision floating-point arithmetic library for high-accuracy semidefinite programming, (ARITH 2017. ARITH 2017, London, UK, July 24-26, 2017 (2017))
[23] Khachiyan, L.; Porkolab, L., On the complexity of semidefinite programs, J. Glob. Optim., 10, 4, 351-365 (1997) · Zbl 0881.90127
[24] Kojima, M.; Shida, M.; Shindoh, S., Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Math. Program., 80, 2, 129-160 (1998) · Zbl 0897.90183
[25] Kronecker, Leopold, Grundzüge einer arithmetischen theorie der algebraischen Grössen, J. Reine Angew. Math., 92, 1-122 (1882) · JFM 14.0038.02
[26] (Lasserre, J-B., Moments, Positive Polynomials and Their Applications. Moments, Positive Polynomials and Their Applications, Optimization Series, vol. 1 (2010), Imperial College Press: Imperial College Press London), xxi+361 pages · Zbl 1211.90007
[27] Naldi, S., Solving rank-constrained semidefinite programs in exact arithmetic, (Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC’16) (2016), ACM: ACM New York, NY, USA), 357-364 · Zbl 1360.90190
[28] Naldi, S., Solving rank-constrained semidefinite programs in exact arithmetic, J. Symb. Comput., 85, 206-223 (2018) · Zbl 1380.90212
[29] Nesterov, Y.; Nemirovsky, A., Interior-Point Polynomial Algorithms in Convex Programming, Studies in Applied Mathematics, vol. 13 (1994), SIAM: SIAM Philadelphia · Zbl 0824.90112
[30] Nie, J.; Ranestad, K.; Sturmfels, B., The algebraic degree of semidefinite programming, Math. Program., 122, 2, 379-405 (2010) · Zbl 1184.90119
[31] Ramana, M., An exact duality theory for semidefinite programming and its complexity implications, Math. Program., 77, 1, 129-162 (1997) · Zbl 0890.90144
[32] Rouillier, F.; Roy, M-F.; Safey El Din, M., Finding at least one point in each connected component of a real algebraic set defined by a single equation, J. Complex., 16, 4, 716-750 (2000) · Zbl 1009.14010
[33] Safey El Din, M., Testing sign conditions on a multivariate polynomial and applications, Math. Comput. Sci., 1, 1, 177-207 (2007) · Zbl 1126.14068
[34] Safey El Din, M.; Schost, É., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (ISSAC’03 (2003), ACM), 224-231 · Zbl 1072.68693
[35] Safey El Din, M.; Schost, E., A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets, J. ACM, 63, 6, Article 48 pp. (2017) · Zbl 1426.68311
[36] Safey El Din, M.; Schost, É., Bit complexity for multi-homogeneous polynomial system solving - application to polynomial minimization, J. Symb. Comput., 87, 176-206 (2018) · Zbl 1391.13056
[37] Safey El Din, M.; Zhi, L., Computing rational points in convex semialgebraic sets and sum of squares decompositions, SIAM J. Optim., 20, 6, 2876-2889 (2010) · Zbl 1279.90127
[38] Scheiderer, C., Sums of squares of polynomials with rational coefficients, J. Eur. Math. Soc., 18, 7, 1495-1513 (2016) · Zbl 1354.14036
[39] Schost, É., Computing parametric geometric resolutions, Appl. Algebra Eng. Commun. Comput., 13, 5, 349-393 (2003) · Zbl 1058.68123
[40] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12, 1-4, 625-653 (1999) · Zbl 0973.90526
[41] Toh, K-C.; Todd, M. J.; Tütüncü, R., SDPT3 - a MATLAB software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11, 1-4, 545-581 (1999) · Zbl 0997.90060
[42] Tunçel, L., Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, vol. 27 (2016), American Mathematical Soc.
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.