(419g) Robust Optimization Using Polyhedral Norm and General Asymmetric Uncertainty Set

Robust optimization technique has been applied to handle the uncertainty inherent in many decision making problems. Uncertainty set construction is a key step for applying robust optimization since it affects the conservativeness and computational tractability of the deterministic robust counterpart problem. The choice of uncertainty set is naturally problem-dependent. However, general guidelines for constructing uncertainty set include that it should not lead to overly conservative solution, and computationally tractable deterministic robust counterpart formulations are preferred.

In the past, various types of uncertainty set ranging from simple boxes (Soyster, 1973) to more advanced conic-representable sets have been studied. Ben-Tal and Nemirovski (2000) introduced ellipsoidal type of uncertainty set for robust linear optimization. Bertsimas et al. (2004) introduced norm induced uncertainty set for robust linear optimization. This can lead to various symmetric set under different type of norms. Li et al. (2011) made a comparative study of various symmetric set induced robust optimization models. Yuan et al. (2016) studied robust linear optimization under correlated uncertainty, and demonstrated the advantage of introducing correlation information into the uncertainty set construction. A major motivation behind those different methods is that tractable linear robust counterpart optimization problems are obtained, which brings significant computational advantage.

In the existing studies, uncertainty set has been generally defined as the symmetric type. However, they may not be appropriate or be too conservative if the actual distribution is asymmetric. To capture the asymmetric distribution, Chen et al. (2007) introduced deviation measures to capture distributional asymmetry, however they assumed that the primitive uncertain parameters are independent. In this work, we investigate the robust linear optimization under uncertainty set induced from various type of polyhedral norms, including l-1 norm, l-infinity norm, D-norm, CVaR norm, deltoidal norm and general polyhedral norm. Furthermore, we introduced a novel method for asymmetric uncertainty set construction based on the distributional information or sampling data of uncertain parameters. The proposed method can be applied to general uncertainty distributions, where correlation between primitive uncertain parameters can be easily incorporated into the polyhedral norm induced uncertainty set. We also derived robust formulations under various polyhedral norms, which all lead to linear optimization problems. For all of those norm induced robust counterpart formulations, model complexity is compared to provide practical guidelines for uncertainty set construction. The asymmetric set induced robust optimization model is compared with the classical symmetric set induced robust optimization model. Numerical example and process design example are studied. Results demonstrate that using asymmetric uncertainty sets leads to less conservative robust solution.

Reference:

[1] Soyster, A. L. (1973). Technical note: convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.

[2] Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3), 411-424.

[3] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.

[4] Bertsimas, D., Pachamanova, D., & Sim, M. (2004). Robust linear optimization under general norms. Operations Research Letters, 32(6), 510-516.

[5] 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.

[6] Yuan, Y., Li, Z., & Huang, B. (2016). Robust optimization under correlated uncertainty: Formulations and computational study. Computers & Chemical Engineering, 85, 58-71.

[7] Chen, X., Sim, M., & Sun, P. (2007). A robust optimization perspective on stochastic programming. Operations Research, 55(6), 1058-1071.