Deriving robust counterparts of nonlinear uncertain inequalities. (English) Zbl 1308.65089
Summary: In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It turns out that to do so one has to calculate the support function of the uncertainty set and the concave conjugate of the nonlinear constraint function. Conveniently, these two computations are completely independent. This approach has several advantages. First, it provides an easy structured way to construct the robust counterpart both for linear and nonlinear inequalities. Second, it shows that for new classes of uncertainty regions and for new classes of nonlinear optimization problems tractable counterparts can be derived. We also study some cases where the inequality is nonconcave in the uncertain parameters.
Keywords:
Fenchel duality; robust counterpart; nonlinear inequality; robust optimization; support functions; nonlinear optimizationReferences:
| [1] | AIMMS: Paragon Decision Technology. http://www.aimms.com/operations-research/mathematical-programming/robust-optimization (2012) · Zbl 0048.11301 |
| [2] | Anderson, T.W., Darling, D.A.: Asymptotic theory of certain goodness-of-fit criteria based on stochastic processes. Ann. Math. Stat. 23(2), 193-212 (1952) · Zbl 0048.11301 · doi:10.1214/aoms/1177729437 |
| [3] | Averbakh, I., Zhao, Y.-B.: Explicit reformulations for robust optimization problems with general uncertainty sets. SIAM J. Optim. 18(4), 1436-1466 (2007) · Zbl 1279.90158 · doi:10.1137/060650003 |
| [4] | Ben-Tal, A., Ben-Israel, A., Teboulle, M.: Certainty equivalents and information measures: duality and extremal principles. J. Math. Anal. Appl. 157, 211-236 (1991) · Zbl 0736.94004 · doi:10.1016/0022-247X(91)90145-P |
| [5] | Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics (2009) · Zbl 1221.90001 |
| [6] | Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization—Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization (2001) · Zbl 0986.90032 |
| [7] | Ben-Tal, A., den Hertog, D.: Immunizing conic quadratic optimization problems against implementation errors. CentER Discussion Paper 2011-060, Tilburg University, 2011 (to appear in Mathematical Programming) |
| [8] | Ben-Tal, A., den Hertog, D., De Waegenaere, A.M.B., Melenberg, B., Rennen, G.: Robust solutions of optimization problems affected by uncertain probabilities. Manag. Sci. 59(2), 341-357 (2013) · doi:10.1287/mnsc.1120.1641 |
| [9] | Ben-Tal, A., den Hertog, D., Laurent, M.: Hidden Convexity in Partially Separable Optimization. CentER Discussion Paper 2011-070, Tilburg University (2011) · Zbl 1279.90158 |
| [10] | Bertsimas, D., Brown, D., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464-501 (2011) · Zbl 1233.90259 · doi:10.1137/080734510 |
| [11] | Bertsimas, D., Pachamanova, D., Sim, M.: Robust linear optimization under general norms. Oper. Res. Lett. 32, 510-516 (2004) · Zbl 1054.90046 · doi:10.1016/j.orl.2003.12.007 |
| [12] | den Hertog, D.: Interior Point Approach to Linear, Quadratic and Convex Programming. Kluwer, Dordrecht (1994) · Zbl 0808.90107 · doi:10.1007/978-94-011-1134-8 |
| [13] | Goh, J., Sim, M.: Robust optimization made easy with ROME. Oper. Res. 59(4), 973-985 (2011) · Zbl 1235.90107 · doi:10.1287/opre.1110.0944 |
| [14] | Golub, G.H., van Loan, C.F.: Matrix Computations, 2nd edn. Johns Hopkins University Press, London (1989) · Zbl 0733.65016 |
| [15] | Gushchin, A.A.: On an extension of the notion of \[f\] f-divergence. Theory Probab. Its Appl. 52(3), 439-455 (2008) · Zbl 1206.94015 · doi:10.1137/S0040585X97983134 |
| [16] | Löfberg, J.: Automatic robust convex programming. Optim. Methods Softw. 27(1), 115-129 (2012) · Zbl 1242.90289 · doi:10.1080/10556788.2010.517532 |
| [17] | Nemirovski, A.: Lectures on Robust Convex Optimization. Lecture 2 of Lecture Notes. http://www2.isye.gatech.edu/nemirovs/Lect2 (2009) |
| [18] | Nesterov, Y.E., Nemirovski, A.: Interior Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, Philadelphia (1993) |
| [19] | Rockafellar, R.T.: Convex Analysis. Princeton Press, Princeton (1970) · Zbl 0193.18401 |
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.
