×

zbMATH — the first resource for mathematics

Selected topics in robust convex optimization. (English) Zbl 1135.90046
Summary: Robust optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but- bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional chance constrained settings of problems with stochastic data, and (4) a novel generic application of the RO methodology in robust linear control.

MSC:
90C34 Semi-infinite programming
90C05 Linear programming
90C20 Quadratic programming
90C22 Semidefinite programming
90C15 Stochastic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adida E. and Perakis G. (2006). A robust optimization approach to dynamic pricing and inventory control with no backorders. Math. Program. 107: 97–129 · Zbl 1134.90002
[2] Atamturk, A., Zhang, M.: Two-stage robust network flow and design under demand uncertainty. Research Report BCOL.04.03, IEOR, University of California-Berkeley. December 2004
[3] Atamturk, A.: Strong formulations of robust mixed 0-1 programming. Research Report BCOL.03.04, IEOR, University of California-Berkeley. December 2003. Revised February 2005
[4] Beck A., Ben-Tal A. and Eldar Y. (2006). Robust mean-squared error estimation of multiple signals in linear systems affected by model and noise uncertainties. Math. Program. 107: 155–187 · Zbl 1135.93031
[5] Ben-Tal A. and Nemirovski A. (1997). Stable truss topology design via semidefinite programming. SIAM J. Optim. 7: 991–1016 · Zbl 0899.90133
[6] Ben-Tal A. and Nemirovski A. (1998). Robust convex optimization. Math. Oper. Res. 23: 769–805 · Zbl 0977.90052
[7] Ben-Tal A. and Nemirovski A. (1999). Robust solutions to uncertain linear programs. OR Lett. 25: 1–13 · Zbl 0941.90053
[8] Ben-Tal A. and Nemirovski A. (2000). Structural design via semidefinite programming. In: Saigal, R., Wolkowitcz, H. and Vandenberghe, L. (eds) Handbook on Semidefinite Programming., pp. Kluwer, Dordrecht · Zbl 0957.90529
[9] Ben-Tal A. and Nemirovski A. (2000). Robust solutions of Linear Programming problems contaminated with uncertain data. Math. Program. 88: 411–424 · Zbl 0964.90025
[10] Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust semidefinite programming. In: Saigal, R., Vandenberghe, L., Wolkowicz, H (eds.) Semidefinite Programming and Applications. Kluwer Dordrecht (2000) · Zbl 0964.90025
[11] Ben-Tal, A., Margalit, T., Nemirovski, A.: Robust Modeling of Multi-Stage Portfolio Problems. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S.(eds.) High Performance Optimization, Dordrecht Kluwer pp. 303–328 (2000) · Zbl 1016.91055
[12] Ben-Tal A. and Nemirovski A. (2001). Lectures on Modern Convex Optimization. SIAM, Philadelphia · Zbl 0986.90032
[13] Ben-Tal A. and Nemirovski A. (2002). Robust optimization–methodology and applications. Math. Program. Ser. B 92: 453–480 · Zbl 1007.90047
[14] Ben-Tal A. and Nemirovski A. (2002). On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J. Optim. 12: 811–833 · Zbl 1008.90034
[15] Ben-Tal A., Nemirovski A. and Roos C. (2002). Robust solutions of uncertain quadratic and conic-quadratic problems. SIAM J. Optim. 13: 535–560 · Zbl 1026.90065
[16] Ben-Tal A., Nemirovski A. and Roos C. (2003). Extended Matrix Cube Theorems with applications to {\(\mu\)}-Theory in Control. Math. Oper. Res. 28: 497–523 · Zbl 1082.90083
[17] Ben-Tal A., Goryashko A., Guslitzer E. and Nemirovski A. (2004). Adjustable robust solutions of uncertain linear programs. Math. Program. 99: 351–376 · Zbl 1089.90037
[18] Ben-Tal A., Golany B., Nemirovski A. and Vial J.-Ph. (2005). Supplier-retailer flexible commitments contracts: a robust optimization approach. Manuf. Serv. Oper. Manage. 7(3): 248–273
[19] Ben-Tal, A., Boyd, S., Nemirovski, A.: Extending the scope of robust optimization: comprehensive robust counterparts of uncertain problems. Math. Program. Ser. B, Special issue on Robust Optimization. (2006) (to appear) E-print: http://www.optimization-online.org/DB_HTML/2005/05/1136.html · Zbl 1134.90042
[20] Ben-Tal, A., Boyd, S., Nemirovski, A.: Control of uncertainty-affected discrete time linear systems via convex programming. SIAM J. Control Optim. (submitted); E-print: http://www.optimization-online.org/DB_HTML/2005/10/1232.html · Zbl 1134.90042
[21] Bertsimas, D., Sim, M.: Robust discrete optimization under ellipsoidal uncertainty sets. Technical Report, MIT, April 2004
[22] Bertsimas D. and Sim M. (2003). Robust discrete optimization and network flows. Math. Program. Ser. B, 98: 49–71 · Zbl 1082.90067
[23] Bertsimas D. and Sim M. (2004). The price of robustness. Oper. Res. 52(1): 35–53 · Zbl 1165.90565
[24] Bertsimas D., Pachamanova D. and Sim M. (2004). Robust linear optimization under general norms. Oper. R. Lett. 32(6): 510–516 · Zbl 1054.90046
[25] Bertsimas D. and Thiele A. (2006). Robust optimization approach to inventory theory. Oper. Res. 54: 150–168 · Zbl 1167.90314
[26] Bertsimas D. and Sim M. (2006). Tractable approximations to robust conic optimization problems. Math. Program. 107: 5–36 · Zbl 1134.90026
[27] Bhattachrrya S., Grate L., Mian S., El Ghaoui L. and Jordan M. (2004). Robust sparse hyperplane classifiers: application to uncertain molecular profiling data. J. Comput. Bio. 11(6): 1073–1089
[28] Boyd S., El Ghaoui L., Feron E. and Balakrishnan V. (1994). Linear matrix inequalities in system and control theory. SIAM, Philadelphia · Zbl 0816.93004
[29] Calafiore, G., El Ghaoui, L.: Worst-case maximum likelihood estimation in the linear model. Automatica 37(4) (2001) · Zbl 0983.93070
[30] Charnes A., Cooper W.W. and Symonds G.H. (1958). Cost horizons and certainty equivalents: an to stochastic programming of heating oil. Manage. Sci. 4: 235–263
[31] Dan Barb F., Ben-Tal A. and Nemirovski A. (2003). Robust dissipativity of interval uncertain system. SIAM J. Control Optim. 41: 1661–1695 · Zbl 1049.93020
[32] Diehl M., Bock H.-G. and Kostina E. (2006). An approximation technique for robust nonlinear optimization. Math. Program. 107: 213–230 · Zbl 1134.90039
[33] Eldar Y., Ben-Tal A. and Nemirovski A. (2005). Robust mean-squared error estimation in the presence of model uncertainties. IEEE Trans. Signal Process. 53: 168–181 · Zbl 1370.93255
[34] El-Ghaoui L. and Lebret H. (1997). Robust solutions to least-square problems with uncertain data matrices. SIAM J. Matrix Anal. Appl. 18: 1035–1064 · Zbl 0891.65039
[35] El-Ghaoui L., Oustry F. and Lebret H. (1998). Robust solutions to uncertain semidefinite programs.. SIAM J. Optim. 9: 33–52 · Zbl 0960.93007
[36] El Ghaoui L., Oks M. and Oustry F. (2003). Worst-case value-at-risk and robust portfolio optimization: a conic programming approach. Oper. Res. 51(4): 543–556 · Zbl 1165.91397
[37] El Ghaoui, L.: Inversion error, condition number, and approximate inverses of uncertain matrices. Linear Algebra Appl. 343–344, 171–193 (2002) · Zbl 0997.65049
[38] El Ghaoui L. and Calafiore G. (2001). Robust filtering for discrete-time systems with bounded noise and parametric uncertainty. IEEE Trans. Automat. Control 46: 1084–1089 · Zbl 1008.93065
[39] Goldfarb D. and Iyengar G. (2003). Robust portfolio selection problems. Math. Oper. Res. 28(1): 1–37 · Zbl 1082.90082
[40] Goldfarb D. and Iyengar G. (2003). Robust quadratically constrained programs. Math. Program. Ser. B 97(3): 495–515 · Zbl 1106.90365
[41] Goulart, P.J., Kerrigan, E.C., Maciejowski, J.M.: Optimization over state feedback policies for robust control with constraints. Technical Report CUED/F-INFENG/TR.494, Cambridge University Engineering Department, March 2005. E-print: http://www-control.eng.cam.ac.uk/, Automatica (to appear) · Zbl 1102.93017
[42] Guslitser, E.: Uncertatinty-immunized solutions in linear programming. Master Thesis, Technion, Israeli Institute of Technology, IE&M faculty (2002). E-print: http://iew3.technion.ac.il/Labs/Opt/index.php?4
[43] Iyengar G. (2005). Robust dynamic programming. Math. Oper. Res. 30(2): 1–21 · Zbl 1082.90123
[44] Iyengar G. and Erdogan E. (2006). Ambiguous chance constrained problems and robust optimization. Math. Program. 107: 17–31
[45] Kočvara M., Zowe J. and Nemirovski A. (2000). Cascading–an approach to robust material optimization. Comput. Struct. 76: 431–442
[46] Kostyukova O. and Kostina E. (2006). Robust optimal feedback for terminal linear-quadratic control problems under disturbances. Math. Program. 107: 131–153 · Zbl 1089.49035
[47] Lanckriet G.R.G., El Ghaoui L., Bhattacharyya C. and Jordan M. (2002). A robust minimax approach to classification. J. Mach. Learn. Res. 3: 555–582 · Zbl 1084.68657
[48] Lasserre J.B. (2006). Robust global optimization with polynomials. Math. Program. 107: 275–293 · Zbl 1134.90031
[49] Miller L.B. and Wagner H. (1965). Chance-constrained programming with joint constraints. Oper. Res. 13: 930–945 · Zbl 0132.40102
[50] Nemirovski, A.: Regular Banach spaces and large deviations of random sums. Paper in progress, E-print: http://www2.isye.gatech.edu/\(\sim\)nemirovs/
[51] Nemirovski A. and Shapiro A. (2006). Convex approximations of chance constrained programs. SIAM J. Optim. 17: 969–996 · Zbl 1126.90056
[52] Genin Y., Hachez Y., Nesterov Yu. and Van Dooren P. (2003). Optimization problems over positive pseudopolynomial matrices.. SIAM J. Matrix Anal. Appl. 25: 57–79 · Zbl 1055.90058
[53] Nilim, A., El Ghaoui, L., Duong, Vu.: Algorithms for multi-aircraft re-routing under uncertainties. In: Actes de la Deuxieme Conference Internationale Associant Chercheurs Vietnamiens et Francophones en Informatique, Hanoï Vietnam, 2-5 Février 2004 (RIVF 2004)
[54] Nilim A. and El Ghaoui L. (2005). Robust control of Markov decision processes with uncertain transition matrices. Oper. Res. 53: 780–798 · Zbl 1165.90674
[55] Perakis G. and Sood A. (2006). Competitive multi-period pricing for perishable products: a robust optimization approach. Math. Program. 107: 295–335 · Zbl 1134.91339
[56] Pinter J. (1989). Deterministic approximations of probability inequalities.. ZOR - Methods Models Oper. Res. Ser. Theory 33: 219–239 · Zbl 0672.60032
[57] Prékopa, A.: On probabilistic constrained programming. In: Proceedings of the Princeton Symposium on Mathematical Programming, pp. 113–138. Princeton University Press, Princeton (1970)
[58] Prékopa A. (1995). Stochastic Programming. Kluwer, Dordrecht · Zbl 0863.90116
[59] Prékopa, A., Vizvari, B., Badics, T.: Programming under probabilistic constraint with discrete random variables. In: Grandinetti, L. et al. (eds.) New Trends in Mathematical Programming, pp 235–257 Kluwer, Dordrecht (1997)
[60] Prékopa, A.: Probabilistic programming. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbook in OR & MS, Vol. 10, North-Holland Publishing Company, Amsterdam (2003) · Zbl 0679.90046
[61] Scherer C.W. and Hol C.W.J. (2006). Matrix sum-of-squares relaxations for robust semi-definite programs. Math. Program. 107: 189–211 · Zbl 1134.90033
[62] Soyster A.L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21: 1154–1157 · Zbl 0266.90046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.