Handling Optimization under Uncertainty Problem Using Robust Counterpart Methodology

Authors

  • Diah Chaerani Faculty of Mathematics and Natural Sciences, Department of Mathematik, Universitas Padjadjaran, Jl. Raya Bandung Sumedang KM. 21, Jatinagor Sumedang 45363
  • Cornelis Roos Algorithm Group, Delft University of Technology, Mekelweg 4, 2528 CD Delft

DOI:

https://doi.org/10.9744/jti.15.2.111-118

Keywords:

Optimization, uncertainty, conic, robust counterpart

Abstract

In this paper we discuss the robust counterpart (RC) methodology to handle the optimization under uncertainty problem as proposed by Ben-Tal and Nemirovskii. This optimization methodology incorporates the uncertain data in U a so-called uncertainty set and replaces the uncertain problem by its so-called robust counterpart. We apply the RC approach to uncertain Conic Optimization (CO) problems, with special attention to robust linear optimization (RLO) problem and include a discussion on parametric uncertainty for that case. Some new supported examples are presented to give a clear description of the used of  RC methodology theorem.

References

Andersen, E. D., Roos, C., and Terlaky, T., On Implementing a Primal-dual Interior-point Method for Conic Quadratic Optimization. Mathematical Programming, 95(2, Ser. B), 2003, pp. 249-277.

Atamturk, A., Strong Formulation of Robust Mixed 0-1 Programming. Technical report, BCOL.03.04, University of California, Berkeley, 2003.

Ben-Tal, A., Margalit, T., and Nemirovski, A., Robust Modeling of Multistage Portfolio Problems. In High Performance Optimization of Applied Optimization, 33, 2000, pp. 303–328.

Ben-Tal, A., and Nemirovski, A., Robust Truss Topology Design via Semidefinite Programming. SIAM Journal on Optimization, 7(4), 1997, pp. 991–1016.[CrossRef]

Ben-Tal, A., and Nemirovski, A., Robust Convex Optimization. Mathematics of Operations Research, 23(4), 1998, pp. 769–805.[CrossRef]

Ben-Tal, A., and Nemirovski, A., Robust Solutions of Uncertain Linear Programs. Operations Research Letters, 25(1), 1999, pp. 1–13.[CrossRef]

Ben-Tal, A., and Nemirovski, A., Robust Solutions of Linear Programming Problems Contaminated with Uncertain Data. Mathematical Programming, 88(3, Ser. A), 2000, pp. 411-424.

Ben-Tal, A. and A. Nemirovski, A., Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications, 2 MPS/ SIAM Series on Optimization, 2001.

Ben-Tal, A., and Nemirovski, A., Robust Optimization–methodology and Applications. Mathematical Programming, 92(3, Ser. B), 2002, pp. 453–480.

Ben-Tal, A., Nemirovski, A., and Roos, C.,Robust Solutions of Uncertain Quadratic and Conic Quadratic Problems. SIAM Journal on Optimization, 13(2), 2002, pp. 535-560.[CrossRef]

Ben-Tal, A., El Ghaoui, L., and Nemirovski, A., Robust Optimization, Princeton University Press, Princeton Series in Applied Mathematics, 2009.

Bertsimas, D., Pachamanova, D., and Sim, M., Robust Linear Optimization under General Norms. Operations Research Letters, 32(6), 2004, pp. 510–516.[CrossRef]

Bertsimas, D., and Sim, M., Robust Discrete Optimization and Network Flows. Mathematical Programming, 98(1-3, Ser. B), 2003, pp. 49–71.

Bertsimas, D., and Sim, M., The Price of Robustness. Operations Research, 52(1), 2004, pp. 35–53.[CrossRef]

Bertsimas, D. and Thiele, A., A Robust Optimization Approach to Supply Chain Management. In Integer Programming and Combinatorial Optimizationof LectureNotes in Computer Sciences, 3064, 2004, pp 86–100. Springer-Verlag, Berlin.

Boyd, S.E. and Vandenberghe, L., Semidefinite Programming. SIAM Review, 38(1), 1996, pp. 49-96.[CrossRef]

Chen, X., Sim, M., and Sun, P., A Robust Optimization Perspective on Stochastic Programming, Operations Research, 55(6), November–December 2007, pp. 1058–1071.[CrossRef]

Costa, O. L. V.,and Nabholz, R. B., A Linear Matrix Inequalities Approach to Robust Mean Semivariance Portfolio Optimization. In Kontoghiorghes, E.J., Rustam, B., and Siokos, S., editors, Computational Methods in Decision-making, Economic and Finance, 2002, pp. 87–105.[CrossRef]

Costa, O. L. V., and Paiva,A. C.,Robust Portfolio Selection Using Linear-matrix Inequalities. Journal of Economic Dynamics and Control, 26(6), 2002, pp. 889–909.[CrossRef]

El Ghaoui, L., and Lebret, H., Robust Solutions to Least-squares Problems with Uncertain Data. SIAM Journal on Matrix Analysis and Applications, 18(4), 1997, pp. 1035–1064.[CrossRef]

Gabrel, V., Murat,C., and Thiele, A., Recent Advances in Robust Optimization: An Overview, Optimization Online, http://www.optimization-online.org/DB_HTML/2012/07/3537.html, 2013.

Goldfarb, D., and Iyengar, G., Robust Portfolio Se-lection Problems. Mathematics ofOperations Research, 28(1), 2003, pp. 1–38.

Ito, T., Multiperiod Portfolio Selection with Second-order Cone Constraints. In 1999 Graduate Course Department of Applied Mathematics and Physics, Graduate school of Informatics, Kyoto University, 2001

Iyengar, G., Robust Dynamic Programming. Mathematics of Operations Research, 30(2), 2005, pp. 257–280.[CrossRef]

Jarre, F., 1996., Interior Point Methods for Classes of Convex Programs. In T. Terlaky, editor, Interior Point Methods of Mathematical Programming, Applied Optimization, 5, 1996, pp. 255-296.

Karasan, O.E., Pinar, M.C., and Yaman, H., The Robust Shortest Path Problem with Interval Data. http://www.optimization−online.org/ DBHTML/2001/08/361.html, 2001.

Karmarkar, N.K., A New Polynomial-time Algorithm for Linear Programming. Combinatorica, 4(4), 1984, pp. 373-395.[CrossRef]

Lutgents, F., and Strum, J., Robust One Period Option Modelling. Technical Report, 11/2002, University of Maastricht.

Malcolm, S. A., and Zenios, S. A., Robust Optimization of Power System Capacity Expansion under Uncertainty. Journal of Operational Research Society, 45, 1994, pp.1040–1049.

Mehrotra, S., 1992., On the Implementation of a (Primal-dual) Interior Point Method. SIAM Journal on Optimization, 2(4), 1992, pp. 575-601

Mulvey, J. M., Vanderbei, R. J.,and Zenios,S. A., Robust Optimization of Large-ScaleSystems. Operations Research, 43(2), 1995, pp. 264–281.[CrossRef]

Nesterov, Y., and Nemirovskii, A., 1994., Interiorpoint Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, 13, 1994.

Nilim, A., and El Ghaoui, L., Robust Control of Markov Decision Processes with Uncertain Transition Matrices. Operations Research, 53(5),2005, pp. 780–798.[CrossRef]

Peng, J., Roos, C., and Terlaky, T., Self-Regularity. A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002.

Renegar, J., A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, 1, 2001.

Roos, C., Terlaky, T., and Vial,J.-Ph.,Theory and Algorithms for Linear Optimization. An Interior Point Approach. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Ltd., Chichester, 1997.

Sturm, J. F., and Zhang,S., An Interior Point Method based on Rank-1 Updates for Linear Programming. Mathematical Programming, 81 (1, Ser. A), 1998, pp.77–87.

Thiele., A., A robust optimization approach to supply chains and revenue management. PhD thesis, School of Management and Operations Research Center, Massachusetts Institute of Technology, 2004.

Takriti, S.,and Ahmed,S., On Robust Optimization of Two-stage Systems. Mathematical Programming, 99(1, Ser. A), 2004, pp. 109–126.

Yanez, J.,and Ramirez,J.,The Robust Coloring Problem. European Journal of Operational Research, 148(3), 2003, pp. 546–558.[CrossRef]

Downloads

Published

2013-12-04