×

Robust linear optimization under general norms. (English) Zbl 1054.90046

Summary: We explicitly characterize the robust counterpart of a linear programming problem with uncertainty set described by an arbitrary norm. Our approach encompasses several approaches from the literature and provides guarantees for constraint violation under probabilistic models that allow arbitrary dependencies in the distribution of the uncertain coefficients.

MSC:

90C05 Linear programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math. Oper. Res., 23, 4, 769-805 (1998) · Zbl 0977.90052
[2] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Oper. Res. Lett., 25, 1, 1-13 (1999) · Zbl 0941.90053
[3] Ben-Tal, A.; Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data, Math. Program. A, 88, 411-424 (2000) · Zbl 0964.90025
[4] Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order Cone, Math. Oper. Res., 26, 2, 193-228 (2001) · Zbl 1082.90133
[5] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPR-SIAM Series on Optimization, SIAM, Philadelphia, 2001.; A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPR-SIAM Series on Optimization, SIAM, Philadelphia, 2001. · Zbl 0986.90032
[6] D. Bertsimas, I. Popescu, Optimal inequalities in probability theory: a convex optimization approach, in SIAM J. Optim. 2004, to appear.; D. Bertsimas, I. Popescu, Optimal inequalities in probability theory: a convex optimization approach, in SIAM J. Optim. 2004, to appear. · Zbl 1077.60020
[7] Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 1, 35-53 (2004) · Zbl 1165.90565
[8] Falk, J. E., Exact solutions of inexact linear programs, Oper. Res., 24, 783-787 (1976) · Zbl 0335.90035
[9] El Ghaoui, L.; Lebret, H., Robust solutions to least-squares problems with uncertain data, SIAM J Matrix Anal. Appl., 18, 4, 1035-1064 (1997) · Zbl 0891.65039
[10] El Ghaoui, L.; Oustry, F.; Lebret, H., Robust solutions to uncertain semidefinite programs, SIAM J. Optim., 9, 1, 33-52 (1998) · Zbl 0960.93007
[11] Lax, P. D., Linear Algebra (1997), Wiley: Wiley New York · Zbl 0146.13701
[12] Soyster, A. L., Convex programming with set-inclusive constraints and applications to inexact linear programming, Oper. Res, 21, 1154-1157 (1973) · 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. 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.