On maximization of quadratic form over intersection of ellipsoids with common center

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 the 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 in order, as far as the dependence on m is concerned, and that a feasible solution 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 Nesterov [4] where bound similar to (*) is established for the case when all A(i) are of rank 1.