×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
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. · Zbl 0986.90032
[6] 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 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. 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.