On the Complexity of Semidefinite Programs.
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^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}).
Introduction
This paper is concerned with the general semidefinite feasibility problem
Given integral n \Theta n symmetric matrices A
whether there exists a real n \Theta n symmetric matrix X such that
where A ffl denotes the standard inner product on the space of real symmetric
matrices and the notation (\Delta) - 0 indicates that (\Delta) is a symmetric positive semidefinite matrix

We also consider the following (polynomially equivalent) problem
Given integral n \Theta n symmetric matrices Q determine whether there are
real numbers x xm such that
The complexity status of problems (F) and (G) is a fundamental open issue in the theory
of semidefinite programming. For the standard bit model of computation, it is known [7]
that either these problems belong to the complexity class NP " coNP , or they are not in
. For the real number model of computation problems (F) and (G) are known
to be in NP " coNP [7], but the question of whether they can be solved in polynomial time
remains open.
We assume throughout the paper, that n - 2, because for the problems are trivial.
The results of this paper are as follows. In Section 3, we obtain upper bounds on the norm
of feasible solutions of (1) and (2). Specifically, we show that:
(i) Any feasible system (1) has a solution in the Euclidean ball
where log l is the maximum bitlength of the input coefficients.
Moreover, the same bound applies to (2): any feasible system (2) has a solution x such
that log
If the solution sets of (1) or (2) are bounded, then the above bounds hold for any solution.
In addition, we give examples of feasible systems (1) and (2) all of whose solutions have
Euclidean norm at least R, where log
In Section 4, we state lower bounds on the discrepancy of infeasible systems (1) and (2):
(ii) If (1) is infeasible, then for any symmetric positive semidefinite matrix X 2 B,
log . The corresponding result for an infeasible
system (2) is that for any x that satisfies the upper bound of (i), the minimum
eigenvalue - n of Q negative and \Gamma log(\Gamma- n
We also give examples of infeasible systems (1) and (2) for which the quantities log max i=1;:::;m
do not exceed \Gammal2 minfm;ng=2 .
We prove the bounds of (i) and (ii) by using some results of Renegar [9] on decision
methods for the first order theory of the reals and an analogue of the fundamental theorem
of linear inequalities for positive semidefinite matrices. These auxiliary results are briefly
reviewed in Section 2.
In Section 5, we discuss the complexity of problems (F) and (G) . Due to (i) and (ii),
solving (F) with the ellipsoid method requires lmn O(minfm;n 2 g) arithmetic operations with
We use the decision method of Renegar [9] along with the derandomized
version [2] of Clarkson's algorithm [3], [1] to improve this result as follows:
(iii) Problem (F) can be solved in mn O(minfm;n 2 g) arithmetic operations over ln O(minfm;n 2 g) -
bit numbers.
In particular, (F) can be solved in strongly polynomial time for any fixed number of variables
or constraints. Note also that for const, the required number of arithmetic operations
grows linearly with m.
In Section 5 we also argue that:
Problem (G) can be solved in O(mn 4 operations over
This extends the earlier result of Ramana [6] that for any fixed m the strict version
problem (G) can be solved in polynomial time.
Note that in the bit model of computation, each arithmetic operation with
bit numbers can be replaced by n O(minfm;n 2 g) operations with l-bit numbers. For this reason,
the bounds on the operations stated in (iii) and (iv) also apply to l-bit numbers.
Finally, in Section 6 we briefly discuss some extensions of (iii) and (iv) to more general
semidefinite optimization problems.
Preliminaries
In this section we introduce some notation and record a few auxiliary propositions, which
are used in Sections 3 and 5.
2.1 Notation
denotes the space of symmetric n \Theta n real matrices. Any matrix in S n can thus be
viewed as a vector in IR 1n(n+1) . For a positive number R, we denote by CR the compact set
is the cone of symmetric positive
semidefinite matrices. - are the (real) eigenvalues of X 2
A formula (in the first-order theory of the reals) is an expression of the form
where:
are the free variables;
ffl each Q is one of the quantifiers 9 or 8;
of the form
where 4 i is one of the "standard relations" ?; !; -; =; 6=, and the g i 's are real
polynomials of degree at most d - 2:
Note that the above formula is in prenex form: all quantifiers in (SF) occur in front.
are called sentences. We say that y 2 IR k is a solution of
(SF) if the sentence obtained by substituting y into (SF) is true.
2.2 Auxiliary Propositions
Proposition 2.1 (Renegar [8]) If a formula (SF ) has only integer coefficients, each of bit
length at most B; then every connected component of the set of its solutions intersects the
ball fy 2 IR k j kyk - Rg; where R satisfies
logR - B(rd) 2 O(!) k
A quantifier elimination method for the first-order theory of the reals constructs for any
input formula (SF) an equivalent quantifier free formula.
Proposition 2.2 (Renegar [9]) There is an algorithm which, given a formula (SF ), finds
an equivalent quantifier free formula of the form
I
where:
1 In this paper, all formulae will be explicitly written using the standard connectives -; and =) :
ffl the degree of h ij (y) - (rd) 2 O(!) Q
is one of the standard relations ?; !; -; =; 6=.
The algorithm requires (rd) 2 O(!) k
operations and (rd) O(k+
evaluations of the input
formula. If the coefficients of the atomic polynomials are integers of bit
length at most B; then the algorithm works with numbers of binary length
This bound also holds for the binary length of the coefficients of the polynomials h ij .
The following special case of the above result deals with the decision problem for the
first-order theory of the reals: determine whether a sentence (SF) is true or false.
Proposition 2.3 (Renegar [9]) There is an algorithm for the decision problem of the first-order
theory of the reals that requires
operations and (rd) O(
evaluations of the input formula. When restricted to sentences
involving only polynomials with integer coefficients of bit length at most B, the procedure
works with numbers of binary length B(rd) 2 O(!) Q
The inequality below is a well-known bound on nonzero roots of univariate polynomials
(see, e.g., [5]).
Proposition 2.4 Let a d be a univariate polynomial
with integer coefficients, and let ff be a nonzero root of p(x). Then jffj
is the height of p(x).
We shall also need the following variant of the Fundamental Theorem of Linear Inequalities
(see, e.g., [11]).
Proposition 2.5 Consider a system of linear inequalities
a T
where a are non-zero vectors, b i 2 IR; let K be a convex set in
Mg is not empty, then there exists a subset
I ' M such that:
(a) jIj - minfm;ng;
Finally, for any R - 0 we have:
To show the first of these identities, observe that
where the last equality follows from the fact that A \Gamma - n (A)I n is a symmetric positive
semidefinite matrix whose minimum eigenvalue is zero. To see the second identity, note that
means
that the minimum on the l.h.s. of (4) is negative and hence it is attained at a matrix X
such that a consequence of (3).
Upper Bounds on Feasible Solutions
Theorem 3.1
(i) Any feasible system (1) has a solution X such that kXk - R, where log
(ii) Moreover, if the feasible set of (1) is bounded, then the above bound holds for any solution
of (1).
Proof: Suppose that system (1) is feasible, and let
(Recall that C is the cone of symmetric positive semidefinite matrices of order
n.) From von Neumann's saddlepoint theorem (see, e.g., [10]) and (3), it follows,
that for any R - 0,
Consider the formula
which can be written in the standard form (SF) as follows:
(R - 0)g:
It is easy to see that for any R 2 IR; the following statements are equivalent:
ffl (1) has a feasible solution
By our original assumption, (1) is feasible, and hence there is a nonnegative R
that satisfies \Phi(R). Next, \Phi(R) is a standard formula (SF) of degree at most
quantifiers. Furthermore, \Phi(R) consists
of polynomial inequalities in m+
Since det(
contains n! products of linear forms in m+1 variables
with integer coefficients of height at most 2 l , each coefficient in \Phi(R) has binary
length at most 1). Now from Proposition 2.1 it follows that
\Phi(R) can be satisfied by a positive number R such that
log
By Proposition 2.5, there is a set I ' M of size at most n(n + 1)=2 such that the
system
is feasible, and any of its solutions solves the original system (1). For this rea-
son, we can obtain a better bound on R by replacing m with minfm;n 2 g. Since
of the theorem follows.
To show part (ii), consider the formula \Phi
R) g: Note that \Phi 0 (R) can be written in prenex form as
(R
It is easy to see that \Phi 0 (R) is satisfied if and only if
Hence, we can apply Proposition 2.1 to \Phi 0 (R) to conclude that, similarly to (5),
log It remains to show that m can be replaced by minfm;n 2 g.
To this end, note that if the solution set of (1) is bounded, then there exists a
system A with at most n(n + 1)=2 inequalities whose
solution set is still bounded. This is because the solution set of (1) is bounded if
and only if the recessive cone of (1) is trivial, i.e.,
is the halfspace fX 2 S n j A i ffl X - 0g.
is equivalent to the emptiness of the intersection of the
. By Helly's theorem (see, e.g.,
[10]) there exists a system of at most 1
whose intersection is still empty. Since any such system must
contain\Omega 1 , the
claim follows.

Remark 3.2 The bounds of Theorems 3.1 apply to any mixed system of strict and/or non-strict
inequalities
where L is a linear subspace in IR n , and the constraint X -L 0 means that X is positive
definite on L. This fact follows from the observation that for any t 2 (0; 1) and any solutions
systems (7) and (1), respectively, the convex combination
satisfies (7).
Theorem 3.3
(i) Any feasible system (2) has a solution x such that log
(ii) Moreover, if the feasible set of (2) is bounded, then the above estimate holds for any
solution of (2).
Proof: We can assume without loss of generality that the input matrices
are linearly independent, and hence m - n(n 1)=2. Suppose that
(2) is feasible and consider the formula
or equivalently,
\Psi(R) is a standard formula with quantifiers in n
variables, respectively, which has
polynomial inequalities of degree at most d = n, whose integer coefficients have
at most Hence \Psi(R) can be satisfied by a
number R such that log which implies part (i) of the
theorem.
To show part (ii), apply the above arguments to the modified formula

Clearly, the bounds of Theorem 3.3 also hold for any strict and/or mixed system (2).
We close this section with examples of ill-posed feasible systems (1) and (2).
Example 3.4 Let n be an even number. Consider n \Theta n symmetric positive semidefinite
matrices X satisfying the system of linear equations:
It is easy to check that this instance of (1) is feasible and log X n;n - l2 n=2 for any of its
solutions. A similar example for problem (2) is given below.
Example 3.5 Given two matrices A 2 S n 1
, denote by
their direct sum. For
and
x
is a feasible instance of (2), any solution of
which satisfies log xm - l2 m .
Lower Bounds on the Discrepancy
l) be the bound of Theorem 3.1, and let
Rg: The discrepancy of (1) is the optimal value of the convex programming problem:
Note that because of the compactness of CR , the minimum in (8) is always attained, and
only if system (1) is feasible.
Remark 4.1 There exist infeasible systems (1) such that inff ' j A
For instance, this is true for the system of linear inequalities X 11 -
is a symmetric positive semidefinite matrix of order 2.
Theorem 4.2 If (1) is infeasible, then \Gamma log '
Although Theorem 4.2 can be proved analogously to Theorem 3.1, it is convenient to postpone
its proof until Section 5.
Now we consider systems (2). Let l) be the bound of Theorem 3.3, and let
Rg be the m-dimensional ball of radius R centered at the origin.
The discrepancy of (2) is the optimal value of the concave program:
Clearly, (2) is feasible if and only if -   - 0:
Theorem 4.3 If (2) is infeasible, then \Gamma log(\Gamma-
The proof of this theorem is also postponed until Section 5. We close this section with
examples of infeasible systems (1) and (2) whose discrepancies are doubly exponentially
small.
Example 4.4 Let n be even, and consider n \Theta n symmetric positive semidefinite matrices
X satisfying the equations:
It is easy to check that this instance of (1) is infeasible and \Gamma log '   - l2
Example 4.5 For
and
is an infeasible instance of (2), and it can be
verified that \Gamma log(\Gamma-
5 Complexity Bounds
By Theorems 3.1 and 4.2, the feasibility of (1) can be determined by computing the optimal
value '   of program (8) to an absolute accuracy of ffl, where This
convex programming problem can be solved in O(n 4 log(2 l nR=ffl)) iterations of the ellipsoid
method (see, e.g., [4]), where each iteration requires O(n 2 (m+n)) arithmetic operations over
log(2 l nR=ffl)-bit numbers. Hence, we obtain an upper bound of lmn O(minfm;n 2 g) operations
with testing the feasibility of (1). This result can be improved
as follows.
Theorem 5.1 The feasibility of (1) can be tested in mn O(minfm;n 2 g) arithmetic operations
over
Proof: We start with a weaker result.
Lemma 5.2 The feasibility of (1) can be tested in (mn) O(minfm;n 2 g) arithmetic
operations over l(mn) O(minfm;n 2 g) -bit numbers.
Proof: The sentence
states that (1) is feasible. Since the characteristic polynomial det(X \Gamma
height 1, from Proposition 2.3 it follows that the
validity of the above sentence can be determined in (mn) O(n 2 ) operations
over
To finish the proof of the lemma, it remains to show that the feasibility
of (1) can also be decided in (mn) O(m) operations with l(mn) O(m) -bit
numbers. Consider the sentence
where \Phi(R) is the formula defined in the proof of Theorem 3.1. This
sentence also states that (1) is feasible. Observe that (11) consists of
polynomial inequalities of degree n in O(m) variables and
has integer coefficients of binary size at most
Since det(
can be evaluated in poly(n; m) operations
(or because all of its coefficients can be computed in n O(m) operations),
the lemma follows from Proposition 2.3.
We continue with the proof of Theorem 5.1. If m is bounded by a polynomial
in n, the theorem follows from Lemma 5.2. We next show that for large m,
determining the feasibility of (1) via Clarkson's algorithm [3] requires an expected
mn O(minfm;n 2 g) operations over ln O(minfm;n 2 g) -bit numbers.
Given a set I '
is the bound of Theorem 3.1 for the entire system (1).
With this notation, we have '  by X(I) the (unique) least
norm solution of the system A
'(I)g be the set of constraints violated by
X(I). A set I is called a basis, if V (J) 6= V (I) for any proper subset J ae I. A
basis J is a basis for I, if J ' I and V for M is called
optimal. In particular, if S is an optimal basis, then
consequently,
From Helly's theorem it follows that D :
Given an optimal basis S, we can apply Lemma 5.2 to A
and determine the feasibility of the original system (1) in n O(minfm;n 2 g) operations
over finds an optimal basis by
performing expected
log m log m) - mpoly(n) violation
tests. Each of these checks whether j 2 V (I) for a sample set I of cardinality
log D) and an index Note that the inclusion can be
written as the sentence
where S I (X; ') is the quantifier
g. Since the positive semidefiniteness of X can be expressed by the formula
follows that V I;j is equivalent to:
I (X;
Each violation test can thus be represented by a sentence in prenex form with
polynomial inequalities of degree
In fact, by using the arguments of Section 4 in [3], one can verify that the above bounds on the number
of violation tests and the size of sample sets are valid for computing an optimal basis for any mapping
that satisfies the following two conditions: (i) V (I) ' M n I and (ii)
any
Note also that the coefficients of these polynomial inequalities are integers of
binary length B - maxfl; log . Now from Proposition 2.3 it
follows that each violation test can be accomplished in n O(minfm;n 2 g) operations
over numbers. But the expected number of violation tests is
bounded by mpoly(n). Hence we conclude that for all n and m, testing the
feasibility of (1) requires expected mn O(minfm;n 2 g) operations over ln O(minfm;n 2 g) -
bit numbers.
Chazelle and Matousek [2] derandomized Clarkson's algorithm for a wide subclass
of LP-type problems, which includes linear programming and the problem of
computing the minimum volume circumscribed ellipsoid for a given m-point set
in IR n . The analysis of their algorithm is based on an additional assumption which
we state here in the following stronger form: there is a constant ~
D such that for
any subset I ' M , all subsets of I violated by some (X; ') can be computed in
D operations. Since computing the above set system can be accomplished
by constructing the arrangement of the hyperplanes A i ffl
(see the argument of [2] for linear programming), we have ~
Dg. The algorithm of [2] computes an optimal basis of (8) by
performing mD O(D) operations and mpoly(D)+D O(D) violation tests with subsets
I of size at most D. Since each violation test can be accomplished
in n O(minfm;n 2 g) operations, we conclude that the derandomized algorithm still
requires mn O(minfm;n 2 g) operations with ln O(minfm;n 2 g) -bit numbers.

Corollary 5.3 The complexity bounds of Theorem 5.1 apply to the problem of computing
an optimal basis of (8).
Theorem 5.4 Given an optimal basis S of (8), in n O(minfm;n 2 g) operations over ln O(minfm;n 2 g) -
bit numbers we can compute a univariate semialgebraic representation of '   , i.e., a system
of univariate polynomial inequalities with integer coefficients such that '   is the only real
solution of the system. In particular, '   is a root of a nontrivial polynomial h(') 2 ZZ[']
such that log
Proof: Assume w.l.o.g. that the given basis S coincides with M . In particular,
1)=2. From von Neumann's saddlepoint theorem and (4), it follows
that for R - 0
Consider the formula
where R the bound of Theorem 3.1. This formula states that ' - '   , and it can
be written as follows:
Now the formula
in the
sense that '   is the only real solution of     ('). By consecutively applying Proposition
2.2 to  (') and     ('), the latter formula can be transformed into a quantifier
operations
with maxfl; log Rg(mn) O(m) - ln O(minfm;n 2 g) -bit numbers.      (') is composed of
univariate polynomial relations h(')40, where 4 2 f -; !; =; 6=; ?; - g: Since
'   is the only real solution of      ('), this formula can be transformed into an
equivalent system of polynomial inequalities, which must contain a polynomial h
such that h('
Remark 5.5 Under the assumption of Theorem 5.4, '   can be approximated to an accuracy
operations (see Theorem 1.2 in
[8]). Note that unlike the upper bound on the operations stated in Theorem 5.1, this bound
depends on l.
Remark 5.6 The minimal polynomial of an algebraic number ff is the primitive irreducible
polynomial p(x) 2 ZZ[x] such that and the leading coefficient of p(x) is positive.
The height of ff is the height of its minimal polynomial. Theorem 5.4 and the well-known
inequality of Mignotte (see [5], p. 261) show that log height('
Theorem 5.4 immediately implies Theorem 4.2, whose proof was postponed in Section 4.
Proof of Theorem 4.2. Suppose that system (1) is infeasible. Then '   ? 0 and by
Theorem 5.4, the positive algebraic number '   is a root of a nontrivial polynomial h(x) 2
ZZ[x] with integer coefficients of bit length ln O(minfm;n 2 g) . Since Proposition 2.4 implies that
height(h)), the theorem follows.

The following result deals with the complexity of testing the feasibility of (2).
Theorem 5.7 The feasibility of (2) can be determined in O(mn 4 operations
over l is the maximum bit length of the entries of
1)=2, we can find a linearly independent subsystem of
operations. We can thus assume that m - n(n+1)=2.
The feasibility of (2) can be stated as the sentence
By Proposition 2.3, the validity of the above sentence can be decided in n O(m)
arithmetic operations with ln O(m) -bit numbers.
It is easy to see that the discrepancy -   of (2) satisfies h(-   with a nontrivial polynomial
ZZ[x] such that log This result and Proposition 2.4
imply Theorem 4.3.
6 Concluding Remarks
Theorem 5.1 can be extended to the optimization version of problem
where D is a given n \Theta n integral symmetric matrix. Specifically, in addition to testing
the feasibility of (14); each of the following problems can also be solved in mn O(minfm;n 2 g)
operations over ln O(minfm;n 2 g) -bit numbers:
Boundedness. Determine whether the objective function is bounded from below on the
set of feasible solutions.
Infimum. Find a univariate semialgebraic representation for the finite infimum ff   .
Attainment. Determine whether the infimum is attained, that is, whether (14) has an
optimal solution.
Least Norm Optimal Solution. Find a univariate semialgebraic representation for each
component of the least norm optimal solution of (14).
Remark 6.1 The boundedness problem readily reduces to the feasibility problem. Although
the attainment problem can also be reduced to the feasibility problem via the duality result
of [7], the latter reduction polynomially increases both n and m and cannot be used in fixed
dimension.
Finally, for the optimization version of (G) with a given integral m-vector d:
the above four problems can be solved in O(mn 4 )+n O(minfm;n 2 g) operations over ln O(minfm;n 2 g) -
bit numbers.
We plan to address these and some other extensions of Theorems 5.1 and 5.7 in a subsequent
paper.



--R

A Randomized Scheme for Speeding Up Algorithms for Linear and Convex Programming Problems with High Constraints-to-Variables Ratio
On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small
Geometric Algorithms and Combinatorial Optimization
Bounds, in Buchberger
An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems
An Exact Duality Theory for Semidefinite Programming and its Complexity Implications
On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
On the Computational Complexity and Geometry of the First Order Theory of the Reals.
Convex Analysis
Theory of Linear and Integer Programming
--TR

--CTR
Xun Li , Xun Yu Zhou , Mustapha Ait Rami, Indefinite Stochastic Linear Quadratic Control with Markovian Jumps in Infinite Time Horizon, Journal of Global Optimization, v.27 n.2-3, p.149-175, November
complexity;bounds on solutions;semidefinite programming