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


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]