Journal of Convex Analysis 20 (2013), No. 2, 377--394
Copyright Heldermann Verlag 2013
Some Robust Convex Programs without a Duality Gap
Vaithilingam Jeyakumar
Dept. of Applied Mathematics, University of New South Wales, Sydney 2052, Australia
v.jeyakumar@unsw.edu.au
Guo Yin Li
Dept. of Applied Mathematics, University of New South Wales, Sydney 2052, Australia
g.li@unsw.edu.au
Jinhua Wang
Dept. of Mathematics, Zhejiang University of Technology, Hangzhou 310032, P. R. China
wjh@zjut.edu.cn
We examine the duality gap between the robust counterpart of a primal uncertain convex optimization problem and the optimistic counterpart of its uncertain Lagrangian dual and identify the classes of uncertain problems which do not have a duality gap. The absence of a duality gap (or equivalently zero duality gap) means that the primal worst value equals the dual best value. We first present a new constraint qualification characterizing zero duality gap for convex programming problems under uncertainty. We then show that the constraint qualification always holds for several important classes of robust convex programming problems. They include convex programs with separable inequality constraints under scenario uncertainty, convex optimization problems over faithfully convex inequality constraints under scenario uncertainty and convex programs with quadratic inequality constraints under spectral norm uncertainty.
Keywords: Robust convex programming, zero duality gap, robust optimization, convex optimization under uncertainty.
MSC: 90C20,90C30,90C26,90C46
[ Fulltext-pdf (173 KB)] for subscribers only.