(340d) Optimal Robust Approximation for Chance Constrained Optimization Problem

For optimization under uncertainty, the chance/probabilistic constraint enforces a probabilistic guarantee on constraint satisfaction and provides a compromise towards the uncertainty comparing to the worst-case scenario problem. Its solution is in general very hard because of the difficulties in formulating explicit deterministic counterpart (even for very simple distributions), the difficulties in checking the feasibility of the probabilistic constraint and the nonconvexity of the feasible region. Chance constrained optimization problem is often solved through safe (conservative) and computationally tractable approximations [1].

Except sampling based approximation [2], uncertainty set induced robust optimization is one of the most popular analytical approximations for chance constraint. In this type of method, the uncertain constraint is enforced to be satisfied for any uncertainty realization within a predefined set [3]. The size of the uncertainty set is determined using a priori probability bounds [4]. In our previous work, we demonstrate that the solution of a priori bounds based robust approximation can be conservative and the quality of robust optimization approximation can be improved through the usage of a posteriori probability bounds [5].

In this work, for the first time in the literature, we address the question of what is the optimal (safe and least conservative) robust approximation for chance constrained problem. The objective is to find out the best possible solution that robust approximation can achieve and to propose an effective algorithm to locate that best solution. Specifically, in this work we first study the relationship between uncertainty set’s size and the probability of constraint satisfaction, and point out the non-monotonicity relationship between them. Furthermore, to find the optimal approximation that satisfies the desired probability while maximizing the objective function at the same time, we propose a two-step algorithm by first identifying the maximum possible probability that can be reached by robust optimization, and then identifying the best set size that lead to the desired probability. Effectiveness of the proposed algorithm is demonstrated through numerical examples and applications in process operations.

References:
[1] A. Nemirovski, A. Shapiro. Convex approximations of chance constrained programs. SIAM J. Optim. 2006, 17(4), 969
[2] S. Ahmed and A. Shapiro. "Solving chance-constrained stochastic programs via sampling and integer programming," in Tutorials in Operations Research, Z.-L. Chen and S. Raghavan (eds.), INFORMS, 2008
[3] Z. Li, R. Ding, C.A. Floudas. A comparative theoretical and computational study on robust counterpart optimization: I. Robust linear optimization and robust mixed integer linear optimization. Industrial & Engineering Chemistry Research, 2011, 50, 10567-10603.
[4] Z. Li, Q. Tang, C.A. Floudas. A comparative theoretical and computational study on robust counterpart optimization: II. Probabilistic guarantees on constraint satisfaction. Industrial & Engineering Chemistry Research. 2012, 51, 6769-6788.
[5] Z. Li, C.A. Floudas. A Comparative Theoretical and Computational Study on Robust Counterpart Optimization: III. A Novel Framework of Improving the Robust Solution. In prepration. 2013