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 criterionf which belongs to a ball B∞(f, ε) of small radius ε > 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 B∞(f, ε) and the user who minimizes over the original decision variables). A mathematical rationale behind this "autonomous" behavior is described.
In fact REF , an SDP solver performs "robust optimization" in the following sense: instead of solving the original optimization problem with nominal criterion f , the solver considers a perturbed criterion which lies in a ball of small radius ε and center f .
In SDP relaxations, inaccurate solvers do robust optimization
arXiv: Optimization and Control
Mathematics Computer Science