Interior-Point Abstracts: On the quality of semidefinite approximations of uncertain semidefinite programs affected by box uncertainty

On the quality of semidefinite approximations of uncertain semidefinite programs affected by box uncertainty

Aharon Ben-Tal and Arkadi Nemirovski

Let P(z) = A_0 + z_1 A_1 + ... + z_L A_L be an affine mapping taking values in the space of m x m real symmetric matrices such that A_0 is positive semidefinite. Consider the following question: what is the largest R such that the set P(\{z: \|z\|_\infty \leq R\}) is contained in the positive semidefinite cone? In general, it is NP-hard to compute a ``tight enough'' approximation of R. One can, however, easily build a simple semidefinite program such that its optimal value r is a lower bound on R. We demonstrate that the ratio R/r does not exceed {\pi\sqrt{k}\over 2}, where k is the maximum of the ranks of A_1, A_2,...,A_L. We present 3 applications of the result: we demonstrate that one can build efficiently lower bounds, exact within the factor {\pi\over 2}, for the following two quantities: (1) the largest R such that all instances of an interval symmetric matrix \{A=A^T: |A_{ij}-A^*_{ij}| \leq R D_{ij} \forall i,j\} are positive semidefinite; (2) the largest R such that all instances of an interval square matrix \{A: |A_{ij}-A^*_{ij} \leq R D_{ij} \forall i,j\} admit a common quadratic Lyapunov stability certificate. Besides this, we present an alternative proof (which does not use the Goemans-Williamson construction) of the fact, established by Yu. Nesterov, that the standard semidefinite upper bound on the maximum of a positive semidefinite quadratic form over the unit cube is at most {\pi\over 2} times larger than the true value of the maximum.

Research report #2/00, April 2000, MINERVA Optimization Center, Technion - Israel Institute of Technology, Technion City, Haifa 32000, Israel

Contact: [email protected]

See home page for Technion Faculty of Industrial Engineering and Management