We demonstrate that if A(1),..., A(m) are symmetric positive semidefinite n
x n matrices with positive definite sum and A is an arbitrary symmetric n
x n matrix, then the relative accuracy, in terms of the optimal value, of t
he semidefinite relaxation
[GRAPHICS]
of the optimization program
x(T) Ax --> max \ x(T) A(i)x less than or equal to 1, i = 1, ..., m (P)
is not worse than 1 - 1/2 ln(2m(2)). It is shown that this bound is sharp i
n order, as far as the dependence on m is concerned, and that a feasible so
lution x to (P) with
xT Ax greater than or equal to Opt(SDP)/2 ln(2m(2))
can be found efficiently. This somehow improves one of the results of Neste
rov [4] where bound similar to (*) is established for the case when all A(i
) are of rank 1.