Abstract
We show that the feasibility of a system of m linear inequalities over the cone of symmetric positive semidefinite matrices of order n can be tested in mn\(mn^{o(\min \{ m,n^2 \} )} \) arithmetic operations with \(ln^{o(\min \{ m,n^2 \} )} \)-bit numbers, where l is the maximum binary size of the input coefficients. We also show that any feasible system of dimension (m,n) has a solution X such that log||X|| ≤ \(ln^{o(\min \{ m,n^2 \} )} \).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adler, I. and Shamir, R. (1990), A Randomized Scheme for Speeding Up Algorithms for Linear and Convex Quadratic Programming Problems with a High Constraints-to-Variables Ratio, Math. Programming 61 (1993), 39–52.
Chazelle, B. and Matousek, J. (1993), On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension, Proc. of the 4th ACM-SIAM Symp. on Discrete Algorithms, 281–290.
Clarkson, K.L. (1995), Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small, J. of ACM 42 (1995), 488–499.
Grötschel, M., Lovász, L. and Schrijver, A. (1988), Geometric Algorithms and Combinatorial Optimization, Springer, Berlin.
Mignotte, M. (1982), Some Useful Bounds, in Buchberger, B., Collins, G.E., and Loos, R. (eds.) in cooperation with Albrecht, R., Computer Algebra, Symbolic and Algebraic Computation (Second Edition), Springer, Wien.
Ramana, M.V. (1993) An AlgorithmicAnalysis of Multiquadratic and Semidefinite Programming Problems, Ph.D. Thesis, The Johns Hopkins University, Baltimore.
Ramana, M.V. (1995) An Exact Duality Theory for Semidefinite Programming and its Complexity Implications, DIMACS Technical Report 95-02.
Renegar, J. (1992a) On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae, SIAM J. on Computing 21 (1992), 1008–1025.
Renegar, J. (1992b) On the Computational Complexity and Geometry of the First Order Theory of the Reals. Part I: Introduction; Preliminaries; the Geometry of Semi-Algebraic Sets; the Decision Problem for the Existential Theory of the Reals, J. of Symbolic Computation 13 (1992), 255–299.
Rockafellar, T.R., Convex Analysis, Princeton University Press, NJ, 1970.
Schrijver, A. (1986) Theory of Linear and Integer Programming, Wiley, New York.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Porkolab, L., Khachiyan, L. On the Complexity of Semidefinite Programs. Journal of Global Optimization 10, 351–365 (1997). https://doi.org/10.1023/A:1008203903341
Issue Date:
DOI: https://doi.org/10.1023/A:1008203903341