Tractable Approximations of Semi-Infinite Convex Problems and Applications

Professor Arkadi Nemirovski

ABSTRACT

Semi-infinite convex programs arise in numerous applications, including Robust Optimization and Robust Control. In general, semi-infiniteness can make a well-structured convex program computationally intractable, which makes it necessary to look for cases where a generic semi-infinite convex problem of a given structure is computationally tractable or admits a "tight'' tractable approximation. In the talk, we focus on semi-infinite convex problems in the conic form, specifically, on uncertain Linear, Conic Quadratic and Semidefinite programs. We demonstrate that in the Linear Programming case, semi-infiniteness preserves computational tractability, provided that the varying parameters enter the data in an affine fashion and run through a computationally tractable set. In contrast to this, typical semi-infinite Conic Quadratic and Semidefinite programs turn out to be NP-hard; we present a number of results on tight tractable approximations of these NP-hard problems. We discuss some applications, primarily to multi-stage decision-making under uncertainty.