Duality gap in linear optimization: stability and generic results

Miguel A. Goberna, Andrea Ridolfi. A., Virginia N. Vera de Serio

We present recent stability results on the duality gap function g that measures the difference between the optimal values of the dual problem and of the primal problem in linear programming and in linear semi-infinite programming. In [1] we analyze the behavior of g when the data defining these problems may be perturbed, considering seven different scenarios. In particular we find some stability results by proving that, under mild conditions, either the duality gap of the perturbed problems is zero or $+\infty$ around the given data, or g has an infinite jump at it. We also give conditions guaranteeing that those data providing a finite duality gap are limits of sequences of data providing zero duality gap for sufficiently small perturbations, which is a generic result.

[1] Goberna, M.A., Ridolfi. A., Vera de Serio, V.N., Stability of the duality gap in linear optimization, Set-Valued and Variational Analysis, to appear.