Tractable approximations to robust conic optimization problems. (English) Zbl 1134.90026
Summary: In earlier proposals, the robust counterpart of conic optimization problems exhibits a lateral increase in complexity, i.e., robust linear programming problems (LPs) become second order cone problems (SOCPs), robust SOCPs become semidefinite programming problems (SDPs), and robust SDPs become NP-hard. We propose a relaxed robust counterpart for general conic optimization problems that (a) preserves the computational tractability of the nominal problem; specifically the robust conic optimization problem retains its original structure, i.e., robust LPs remain LPs, robust SOCPs remain SOCPs and robust SDPs remain SDPs, and (b) allows us to provide a guarantee on the probability that the robust solution is feasible when the uncertain coefficients obey independent and identically distributed normal distributions.
References:
| [1] | Ben-Tal, Math. Oper. Res., 23, 769 (1998) · Zbl 0977.90052 |
| [2] | Ben-Tal, A., Nemirovski, A.: On the quality of SDP approximations of uncertain SDP programs, Research Report #4/98 Optimization Laboratory, Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Israel (1998) |
| [3] | Ben-Tal, Oper. Res. Let., 25, 1 (1999) · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4 |
| [4] | Ben-Tal, Progr., 88, 411 (2000) · Zbl 0964.90025 · doi:10.1007/PL00011380 |
| [5] | Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPR-SIAM Series on Optimization, SIAM, Philadelphia 2001 · Zbl 0986.90032 |
| [6] | Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust semidefinite programming. In: Saigal, R., Vandenberghe, L., Wolkowicz, H., (eds.), Semidefinite programming and applications, Kluwer Academic Publishers, (2000) · Zbl 1221.90001 |
| [7] | Bertsimas, D., Brown, D.: Constrainted stochastic LQC: A tractable approach. submitted for publication, 2004 · Zbl 1366.93699 |
| [8] | Bertsimas, Operations Research Letters,, 32, 510 (2003) · Zbl 1054.90046 · doi:10.1016/j.orl.2003.12.007 |
| [9] | Bertsimas, Oper. Res., 52, 35 (1) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [10] | Bertsimas, Math. Progr., 98, 49 (2003) · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4 |
| [11] | Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York, 1997 · Zbl 0892.90142 |
| [12] | El-Ghaoui, SIAM J. Matrix Anal. Appl., 18, 1035 (1997) · Zbl 0891.65039 · doi:10.1137/S0895479896298130 |
| [13] | El-Ghaoui, SIAM J. Optim., 9, 33 (1998) · Zbl 0960.93007 · doi:10.1137/S1052623496305717 |
| [14] | Güler, Math. Progr., 81, 55 (1998) · Zbl 0919.90124 · doi:10.1007/BF01584844 |
| [15] | Nemirovski, A.: On tractable approximations of ramdomly perturbed convex constraints. In: Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, Hawaii, USA, December, pp. 2419-2422, 2003 |
| [16] | Nemirovski, A.: Regular Banach spaces and large deviations of random sums. http://iew3.technion.ac.il/Home/Users/Nemirovski.html#part4 2004 |
| [17] | Renegar, J.: A mathematical view of interior-point methods in convex optimization. MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001 · Zbl 0986.90075 |
| [18] | Soyster, Oper. Res., 21, 1154 (1973) · Zbl 0266.90046 · doi:10.1287/opre.21.5.1154 |
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.
