Strong duality in robust semi-definite linear programming under data uncertainty

Abstract

This article develops the deterministic approach to duality for semi-definite linear programming problems in the face of data uncertainty. We establish strong duality between the robust counterpart of an uncertain semi-definite linear programming model problem and the optimistic counterpart of its uncertain dual. We prove that strong duality between the deterministic counterparts holds under a characteristic cone condition. We also show that the characteristic cone condition is also necessary for the validity of strong duality for every linear objective function of the original model problem. In addition, we derive that a robust Slater condition alone ensures strong duality for uncertain semi-definite linear programs under spectral norm uncertainty and show, in this case, that the optimistic counterpart is also computationally tractable.

Keywords:

• robust optimization
• semi-definite programming under uncertainty
• strong duality
• linear matrix inequality problems

AMS Subject Classifications::

• 90C22
• 90C25
• 90C46

Acknowledgements

The authors are grateful to the referees for their helpful comments and constructive suggestions which have contributed to the final preparation of this article. Research was partially supported by a grant from the Australian Research Council.

Notes

Note

1. It should be noted that the computational tractability of primal robust SDPs (i.e. robust counterparts) may also be checked independently for these classes. We do not intend to identify cases of robust SDPs where strong duality holds and optimistic counterparts are easily solvable but the robust counterparts are not necessarily tractable.