(282a) Improved a Priori Probabilistic Guarantees for Robust Counterpart Optimization

The parameters of applied mathematical models often have more than one possible value which they can achieve due to limited information or measurement error. The solutions and objective values produced from optimizing models with uncertain parameters can vary greatly based on which values the uncertain parameters realize. One method of handling uncertain parameters is to guarantee feasibility of the constraints for all possible parameter sets contained within deterministically defined parameter spaces, called uncertainty sets; the corresponding optimization model is known as a robust counterpart. If every uncertain parameter has a bounded range of possible values, the so-called “worst-case” robust counterpart can be solved [1], where each constraint's uncertainty set is defined to include all possible parameter sets; the probability that a parameter set would realize values rendering an optimal solution infeasible is zero. Less conservative solutions can also be obtained for models with bounded or unbounded uncertain parameters, where the uncertainty sets can be defined with a corresponding probability of constraint violation greater than zero [2-6]. The quality of an optimal solution of the robust counterpart relies heavily on methods that define uncertainty sets which are guaranteed to satisfy a particular upper bound on the probability of constraint violation; a tighter probabilistic bound would allow the imposition of a smaller uncertainty set with the same guarantee of feasibility and can drastically improve objective values.

We present new a priori bounds on the probability of constraint violation for defining uncertainty sets. The methods apply and are specially tailored to different types of uncertainty sets currently in use [6-9]. Key to the derivation of each bound is a novel theorem on fitting objects of alterable size for geometric tailoring. Situations for which the bounds are applicable include (i) bounded uncertain parameters with unknown probability distributions [6-8,10], (ii) bounded and unbounded uncertain parameters with known probability distributions [10-12], and (iii) bounded, possibly asymmetrically distributed uncertain parameters with limited information on their means, thus enabling usage of parameters matching the latter scenario for the first time. The novel bounds yield smaller uncertainty sets with the same probability of constraint violation when compared with existing methods. These methods can provide greatly improved objective values and also improve the performance of iterative algorithms which rely on a priori and a posteriori bounds to obtain less conservative solutions [13].

References:

1. Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.

2. El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18(4), 1035-1064.

3. El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1), 33-52.

4. Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769-805.

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

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

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

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

9. 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.

10. 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.

11. Paschalidis, I., Kang, S., & Li, K. (2008). Distribution-dependent robust linear optimization with asymmetric uncertainty and application to optimal control. In Proceedings of the 17th World Congress IFAC.

12. Kang, S. C., Brisimi, T. S., & Paschalidis, I. C. (2013). Distribution-dependent robust linear optimization with applications to inventory control. Annals of Operations Research, 1-35.

13. 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.