## On Maximization of Quadratic form over Intersection of Ellipsoids
with Common Center

###
Arkadi Nemirovski, Kees Roos, Tam\'as Terlaky

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 quality of the semidefinite relaxation
max_X { Tr(AX), Tr(A_i X) <= 1, i="1..m," X>=0} (SDP)

of the optimization program

x^T A x --> max | x^T A_i x <= 1, i="1..m"

is not worse than 1 / 2ln(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

x^T A x >= Opt(SDP) / 2ln(2m^2) (*)

can be found efficiently. This somehow improves one of the results of
Nesterov (1998) where bound similar to (*) is established for the case
when all *A_i* are of rank 1.

Report No. 98-??, Faculty of Technical Mathematics and
Informatics, Delft University of Technology, P.O. Box 5031, 2600 GA
Delft, The Netherlands.

Contact: t.terlaky@twi.tudelft.nl