428779 Robust Optimization Under Correlated Uncertainty within a Single Constraint and Across Multiple Constraints

Wednesday, November 11, 2015: 5:21 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
Yuan Yuan, Zukui Li and Biao Huang, Department of Chemical and Materials Engineering, University of Alberta, Edmonton, AB, Canada

In deterministic optimization problems, it is assumed that all the model parameters are known and take certain nominal values. However, many realistic parameters are uncertain and subject to random distributions. Assuming deterministic or nominal values for those uncertain parameters will lead to decisions that are infeasible or suboptimal for practical implementation. Thus, it is important to incorporate parameter uncertainty into the optimization problem. Various approaches such as robust optimization, stochastic programming with recourse and chance constraint have been proposed in the past to address uncertainty in optimization problems. Among them, robust optimization deals with the parameter uncertainty by introducing an uncertainty set which covers part or the whole region of the uncertainty space. The target is to select the best solution that is feasible for any realizations of the uncertain parameters in the uncertainty set [1].

The uncertainty set induced robust optimization framework has been extensively studied in literature and applied to various decision making problems. However, existing robust optimization methods generally assume that the uncertainties in the parameters are independent [2-4]. In practice, the uncertainties may be correlated with each other. For instance, the price and demand of crude oil are correlated. As a result, the traditional robust optimization methods that ignore the correlation may lead to a solution that is too conservative. In this work, we present novel results on robust optimization under correlated uncertainties that is either within a single constraint or across multiple constraints.

First, we propose the robust optimization framework for correlated uncertainty within a single constraint. Robust counterpart optimization formulations are derived for five different types of uncertain set. Specifically, box, polyhedral and ellipsoidal type of uncertainty set induced robust optimization formulations are derived for unbounded and correlated uncertainties within a constraint, and “interval+polyhedral” and “interval+ellipsoidal” set induced robust optimization formulations are derived for bounded uncertainties and correlated uncertainties within a constraint.

Second, we study the robust optimization method for correlated uncertainty in multiple constraints. Robust optimization formulations are derived based on the aforementioned results for correlated uncertainty in a single constraint and the recent work on joint chance constrained optimization [5]. Chance constraint models the uncertainty in an optimization problem by enforcing the probability of constraint satisfaction under parameter uncertainty. As an important application of robust optimization, chance constrained optimization problem can be solved with robust optimization approximation. Since joint chance constraint enforces several constraints to be satisfied simultaneously under uncertainty, it is very complicated and only very few works have been reported in the literature (e.g. [6]). In this work, we derive the robust optimization formulations for joint chance constraint with correlated uncertainty across multiple constraints.

Finally, numerical examples are studied to illustrate the proposed robust optimization framework for correlated uncertainty within a constraint and in multiple constraints. Different cases of the correlations are considered to demonstrate the effectiveness of the proposed robust optimization method under correlated uncertainty.


[1] Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.

[2] Li, Z., Ding, R., & Floudas, C. A. (2011). A comparative theoretical and computational study on robust counterpart optimization: I. Robust linear optimization and robust mixed integer linear optimization. Industrial & engineering chemistry research, 50(18), 10567-10603.

[3] Li, Z., Tang, Q., & Floudas, C. A. (2012). A comparative theoretical and computational study on robust counterpart optimization: II. Probabilistic guarantees on constraint satisfaction. Industrial & engineering chemistry research, 51(19), 6769-6788.

[4] Li, Z., & Floudas, C. A. (2014). A Comparative Theoretical and Computational Study on Robust Counterpart Optimization: III. Improving the Quality of Robust Solutions. Industrial & Engineering Chemistry Research, 53(33), 13112-13124.

[5] Yuan, Y., Li, Z., & Huang, B. (2015). Robust Optimization Approximation for Joint Chance Constrained Optimization Problem. Journal of Global Optimization. Under review.

[6] Chen, W., Sim, M., Sun, J., & Teo, C. P. (2010). From CVaR to uncertainty set: Implications in joint chance-constrained optimization. Operations research, 58(2), 470-485.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization III
See more of this Group/Topical: Computing and Systems Technology Division