Abstract.
In this paper we study robust convex quadratically constrained programs, a subset of the class of robust convex programs introduced by Ben-Tal and Nemirovski [4]. In contrast to [4], where it is shown that such robust problems can be formulated as semidefinite programs, our focus in this paper is to identify uncertainty sets that allow this class of problems to be formulated as second-order cone programs (SOCP). We propose three classes of uncertainty sets for which the robust problem can be reformulated as an explicit SOCP and present examples where these classes of uncertainty sets are natural.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13–51 (1995)
Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Prog. 95(1), 3–51 (2003)
Ben-Tal, A., Nemirovski, A.: Robust truss topology design via semidefinite programming. SIAM J. Optim. 7(4), 991–1016 (1997)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1), 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. SIAM, Philadelphia, PA, 2001
Boyd, S., El~Ghaoui, L., Feron, E., Balakrishnan, V.: Linear matrix inequalities in system and control theory. SIAM, Philadelphia, PA, 1994
Burges, C.J.C.: A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery. 2, 121–167 (1998)
Calafiore, G., El~Ghaoui, L.: Minimum variance estimation with uncertain statistical model. In: Proc. of 40th Conf. Dec. and Cont., 2001
Chopra, V.K., Ziemba, W.T.: The effect of errors in means, variances and covariances on optimal portfolio choice. J. Portfolio Manag., Winter, 1993, pp. 6–11
El~Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18(4), 1035–1064 (1997)
El~Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1), 33–52 (1998)
Goldfarb, D., Iyengar, G.: Robust portfolio selection problems. Math. Oper. Res. 28(1), (2003)
Golub, G.H., Van~Loan, C.: Matrix Computations. John Hopkins Press, 3rd edition, 1996
Huber, P.J.: Robust Statistics. John Wiley & Sons, 1981
Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs and bounds on risk. Submitted to Operations Research, June 2000
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1-3), 193–228 (1998)
Mangasarian, O.L., Musicant, D.R.: Robust linear and support vector regression. IEEE Trans. PAMI, 22, 9 (2000)
Markowitz, H.M.: Portfolio selection. J. Finance 7, 77–91 (1952)
Markowitz, H.M.: Portfolio Selection. Wiley, New York, 1959
Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM, Philadelphia, 1993
Pal, D., Iyengar, G.N., Cioffi, J.M.: A new method for channel shortening with applications to discrete multi-tone – part i : Theory. Submitted to IEEE Transactions on Communications
Pal, D., Iyengar, G.N., Cioffi, J.M.: A new method of channel shortening with applications to discrete multi-tone (dmt) systems. In: Proceeding of the IEEE International Conference on Communications, 2, 763–768 (1998)
Proakis, J.G.: Digital Communication. McGraw-Hill, 4th edition, 2000
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Reveiw 38, 49–95 (1996)
Vandenberghe, L., Boyd, S., Nouralishahi, M.: Robust linear programming and optimal control. In: Proceedings of the 15th IFAC World Congress on Automatic Control, 2002
Vapnik, V.: Statistical learning theory. John Wiley and Sons, Inc., New York, 1998
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by DOE grant GE-FG01-92ER-25126, NSF grants DMS-94-14438, CDA-97-26385, DMS-01-04282 and ONR grant N000140310514.
Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.
Rights and permissions
About this article
Cite this article
Goldfarb, D., Iyengar, G. Robust convex quadratically constrained programs. Math. Program., Ser. B 97, 495–515 (2003). https://doi.org/10.1007/s10107-003-0425-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0425-3