×

When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent? (English) Zbl 1401.90224

Summary: Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems.

MSC:

90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
90C47 Minimax problems in mathematical programming
49K35 Optimality conditions for minimax problems

References:

[1] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, Hoboken (2013) · Zbl 1140.90040
[2] Ben-Tal, A; Hertog, D; Vial, J-P, Deriving robust counterparts of nonlinear uncertain inequalities, Math. Program., 149, 265-299, (2015) · Zbl 1308.65089 · doi:10.1007/s10107-014-0750-8
[3] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009) · Zbl 1221.90001 · doi:10.1515/9781400831050
[4] Ben-Tal, A; Goryashko, A; Guslitzer, E; Nemirovski, A, Adjustable robust solutions of uncertain linear programs, Math. Program., 99, 351-376, (2004) · Zbl 1089.90037 · doi:10.1007/s10107-003-0454-y
[5] Ben-Tal, A; Nemirovski, A, Robust convex optimization, Math. Oper. Res., 23, 769-805, (1998) · Zbl 0977.90052 · doi:10.1287/moor.23.4.769
[6] Ben-Tal, A; Nemirovski, A, Robust solutions of uncertain linear programs, Oper. Res. Lett., 25, 1-13, (1999) · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4
[7] Bertsimas, D; Bidkhori, H, On the performance of affine policies for two-stage adaptive optimization: a geometric perspective, Math. Program., 153, 577-594, (2015) · Zbl 1341.90094 · doi:10.1007/s10107-014-0818-5
[8] Bertsimas, D; Goyal, V, On the power and limitations of affine policies in two-stage adaptive optimization, Math. Program., 134, 491-531, (2012) · Zbl 1267.90083 · doi:10.1007/s10107-011-0444-4
[9] Bertsimas, D; Goyal, V, On the approximability of adjustable robust convex optimization under uncertainty, Math. Methods Oper. Res., 77, 323-343, (2013) · Zbl 1285.90021 · doi:10.1007/s00186-012-0405-6
[10] Bertsimas, D; Goyal, V; Brian, YL, A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization, Math. Program., 150, 281-319, (2015) · Zbl 1309.90121 · doi:10.1007/s10107-014-0768-y
[11] Bertsimas, D; Iancu, DA; Parrilo, PA, Optimality of affine policies in multistage robust optimization, Math. Oper. Res., 35, 363-394, (2010) · Zbl 1218.90216 · doi:10.1287/moor.1100.0444
[12] Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513, pp. 439-453. Springer, Berlin (2007) · Zbl 1136.90451
[13] Gorissen, B.L., den Hertog D: Robust nonlinear optimization via the dual, Optimization Online (2015) · Zbl 1285.90021
[14] Gorissen, BL; Yanıkoğlu, İ; Hertog, D, A practical guide to robust optimization, Omega, 53, 124-137, (2015) · doi:10.1016/j.omega.2014.12.006
[15] Gülpınar, N; Rustem, B, Worst-case robust decisions for multi-period mean-variance portfolio optimization, Eur. J. Oper. Res., 183, 981-1000, (2007) · Zbl 1138.91446 · doi:10.1016/j.ejor.2006.02.046
[16] Iancu, DA; Sharma, M; Sviridenko, M, Supermodularity and affine policies in dynamic robust optimization, Oper. Res., 61, 941-956, (2013) · Zbl 1291.90303 · doi:10.1287/opre.2013.1172
[17] Iancu, DA; Trichakis, N, Pareto efficiency in robust optimization, Manag. Sci., 60, 130-147, (2013) · doi:10.1287/mnsc.2013.1753
[18] Iyengar, GN, Robust dynamic programming, Math. Oper. Res., 30, 257-280, (2005) · Zbl 1082.90123 · doi:10.1287/moor.1040.0129
[19] Melamed, M; Ben-Tal, A; Golany, B, On the average performance of the adjustable RO and its use as an offline tool for multi-period production planning under uncertainty, Comput. Manag. Sci., 13, 293-315, (2016) · Zbl 1397.90314 · doi:10.1007/s10287-016-0250-9
[20] Takeda, A; Taguchi, S; Tütüncü, RH, Adjustable robust optimization models for a nonlinear two-period system, J. Optim. Theory Appl., 136, 275-295, (2008) · Zbl 1146.90075 · doi:10.1007/s10957-007-9288-8
[21] Wiesemann, W; Kuhn, D; Rustem, B, Robust Markov decision processes, Math Oper. Res., 38, 153-183, (2013) · Zbl 1291.90295 · doi:10.1287/moor.1120.0566
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.