In SDP relaxations, inaccurate solvers do robust optimization

Abstract

We interpret some wrong results (due to numerical inaccuracies) already observed when solving SDP-relaxations for polynomial optimization on a double precision floating point SDP solver. It turns out that this behavior can be explained and justified satisfactorily by a relatively simple paradigm. In such a situation, the SDP solver (and not the user) performs some `robust optimization' without being told to do so. Instead of solving the original optimization problem with nominal criterion $f$, it uses a new criterion $\tilde{f}$ which belongs to a ball ${\mathbf{B}}_{\infty }(f,\epsilon )$ of small radius $\epsilon >0$, centered at the nominal criterion $f$ in the parameter space. In other words the resulting procedure can be viewed as a `$\max -\min$' robust optimization problem with two players (the solver which maximizes on ${\mathbf{B}}_{\infty }(f,\epsilon )$ and the user who minimizes over the original decision variables). A mathematical rationale behind this `autonomous' behavior is described.

17 pages