×

Robust quadratic programming with mixed-integer uncertainty. (English) Zbl 1474.90312

Summary: We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate \(S\)-lemma method – which is valid only in the case of continuous uncertainty – is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
The online companion is available at https://doi.org/10.1287/ijoc.2019.0901.

MSC:

90C17 Robustness in mathematical programming
90C20 Quadratic programming
90C22 Semidefinite programming
90C25 Convex programming

Software:

RanGen; ROME; YALMIP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahipasaoglu SD, Natarajan K, Shi D (2019) Distributionally robust project crashing with partial or no correlation information. Networks. Forthcoming.Google Scholar · Zbl 1418.90132
[2] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · Zbl 1221.90001 · doi:10.1515/9781400831050
[3] Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming Ser. A 99(2):351-376.Crossref, Google Scholar · Zbl 1089.90037 · doi:10.1007/s10107-003-0454-y
[4] Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769-805.Link, Google Scholar · Zbl 0977.90052
[5] Ben-Tal A, Nemirovski A, Roos C (2002) Robust solutions of uncertain quadratic and conic-quadratic problems. SIAM J. Optim. 13(2):535-560.Crossref, Google Scholar · Zbl 1026.90065 · doi:10.1137/S1052623401392354
[6] Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464-501.Crossref, Google Scholar · Zbl 1233.90259 · doi:10.1137/080734510
[7] Bertsimas D, Sim M (2006) Tractable approximations to robust conic optimization problems. Math. Programming Ser. B 107(1-2):5-36.Crossref, Google Scholar · Zbl 1134.90026 · doi:10.1007/s10107-005-0677-1
[8] Blankenship J, Falk JE (1976) Infinitely constrained optimization problems. J. Optim. Theory Appl. 19(2):261-281.Crossref, Google Scholar · Zbl 0307.90071 · doi:10.1007/BF00934096
[9] Bomze IM, Cheng J, Dickinson PJC, Abdel L (2017) A fresh CP look at mixed-binary QPs: New formulations and relaxations. Math. Programming 166(1-2):159-184.Crossref, Google Scholar · Zbl 1386.90097 · doi:10.1007/s10107-017-1109-8
[10] Bomze IM, de Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2):163-185.Crossref, Google Scholar · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[11] Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming Ser. A 120(2):479-495.Crossref, Google Scholar · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[12] Burer S (2012) Copositive programming. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 201-218.Crossref, Google Scholar · Zbl 1334.90098 · doi:10.1007/978-1-4614-0769-0_8
[13] Caramanis C, Mannor S, Xu H (2011) Robust optimization in machine learning. Optimization for Machine Learning, Neural Information Processing Series (MIT Press, Cambridge), 369-402.Google Scholar
[14] Chen X, Sim M, Sun P (2007) A robust optimization perspective on stochastic programming. Oper. Res. 55(6):1058-1071.Link, Google Scholar · Zbl 1167.90608
[15] Cortes C, Vapnik V (1995) Support-vector networks. Machine Learn. 20(3):273-297.Crossref, Google Scholar · Zbl 0831.68098 · doi:10.1007/BF00994018
[16] de Klerk E, Pasechnik DV (2002) Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4):875-892.Crossref, Google Scholar · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[17] Delage E, Iancu DA (2015) Robust multistage decision making. Aleman DM, Thiele AC, eds. The Operations Research Revolution, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 20-46.Link, Google Scholar
[18] Demeulemeester E, Vanhoucke M, Herroelen W (2003) RanGen: A random network generator for activity-on-the-node networks. J. Scheduling 6(1):17-38.Crossref, Google Scholar · Zbl 1154.90440 · doi:10.1023/A:1022283403119
[19] Diananda PH (1962) On non-negative forms in real variables some or all of which are non-negative. Math. Proc. Cambridge Philos. Soc. 58(1):17-25.Crossref, Google Scholar · Zbl 0108.04803 · doi:10.1017/S0305004100036185
[20] El Ghaoui L, Lebret H (1997) Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18(4):1035-1064.Crossref, Google Scholar · Zbl 0891.65039 · doi:10.1137/S0895479896298130
[21] Eldén L (1980) Perturbation theory for the least squares problem with linear equality constraints. SIAM J. Numer. Anal. 17(3):338-350.Crossref, Google Scholar · Zbl 0469.65023 · doi:10.1137/0717028
[22] Gao S, Simchi-Levi D, Teo CP, Yan Z (2018) Disruption risk mitigation in supply chains—The risk exposure index revisited. Oper. Res. 152(1-2):301-338.Google Scholar
[23] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, New York).Google Scholar · Zbl 0411.68039
[24] Georghiou A, Wiesemann W, Kuhn D (2015) Generalized decision rule approximations for stochastic programming via liftings. Math. Programming 152(1-2):301-338.Crossref, Google Scholar · Zbl 1327.90152 · doi:10.1007/s10107-014-0789-6
[25] Goh J, Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4-part-1):902-917.Google Scholar · Zbl 1228.90067
[26] Goldfarb D, Iyengar G (2003) Robust convex quadratically constrained programs. Math. Programming 97(3):495-515.Crossref, Google Scholar · Zbl 1106.90365 · doi:10.1007/s10107-003-0425-3
[27] Golub GH, Loan CV (2012) Matrix Computations (Johns Hopkins Press, Baltimore).Google Scholar
[28] Gorissen BL, Yanıkoğlu I, den Hertog D (2015) A practical guide to robust optimization. Omega 53:124-137.Crossref, Google Scholar · doi:10.1016/j.omega.2014.12.006
[29] Hadjiyiannis MJ, Goulart PJ, Kuhn D (2011) A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. IEEE Conf. Decision Control Eur. Control Conf. (IEEE, New York), 7386-7391.Google Scholar
[30] Hanasusanto GA, Kuhn D (2018) Conic programming reformulations of two-stage distributionally robust linear programs over wasserstein balls. Oper. Res. 66(3):849-869.Link, Google Scholar · Zbl 1455.90121
[31] Hay GA (1970) Production, price, and inventory theory. Amer. Econom. Rev. 60(4):531-545.Google Scholar
[32] Kleywegt AJ, Shapiro A, de Mello TH (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479-502.Crossref, Google Scholar · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[33] Kong Q, Lee CY, Teo CP, Zheng Z (2013) Scheduling arrivals to a stochastic service delivery system using copositive cones. Oper. Res. 61(3):711-726.Link, Google Scholar · Zbl 1273.90090
[34] Lasserre JB (2009) Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4):1995-2014.Crossref, Google Scholar · Zbl 1181.90216 · doi:10.1137/080728214
[35] Li X, Natarajan K, Teo CP, Zheng Z (2014) Distributionally robust mixed integer linear programs: Persistency models with applications. Eur. J. Oper. Res. 233(3):459-473.Crossref, Google Scholar · Zbl 1339.90248 · doi:10.1016/j.ejor.2013.07.009
[36] Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. IEEE International Symposium on Computer Aided Control Systems Design (IEEE, New York), 284-289.Google Scholar
[37] Marandi A, Ben-Tal A, den Hertog D, Melenberg B (2017) Extending the scope of robust quadratic optimization. Optim. Online. http://www.optimization-online.org/DB_FILE/2017/05/6017.pdf.Google Scholar
[38] Markowitz H (1952) Portfolio selection. J. Finance 7(1):77-91.Google Scholar
[39] Natarajan K, Teo CP (2017) On reduced semidefinite programs for second order moment bounds with applications. Math. Programming 161(1-2):487-518.Crossref, Google Scholar · Zbl 1360.90191 · doi:10.1007/s10107-016-1019-1
[40] Natarajan K, Teo CP, Zheng Z (2011) Mixed 0-1 linear programs under objective uncertainty: A completely positive representation. Oper. Res. 59(3):713-728.Link, Google Scholar · Zbl 1231.90304
[41] Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, Pasadena.Google Scholar
[42] Rockafellar RT, Wets RJB (1990) Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time. SIAM J. Control Optim. 28(4):810-822.Crossref, Google Scholar · Zbl 0714.49036 · doi:10.1137/0328046
[43] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Chichester, UK).Google Scholar · Zbl 0970.90052
[44] Shafieezadeh-Abadeh S, Esfahani PM, Kuhn D (2015) Distributionally robust logistic regression. Proc. 28th Internat. Conf. Neural Inform. Process. Systems (MIT Press, Cambridge) 1576-1584.Google Scholar
[45] Shaked-Monderer N, Berman A, Bomze IM, Jarre F, Schachinger W (2015) New results on the cp-rank and related properties of co(mpletely) positive matrices. Linear Multilinear Algebra 63(2):384-396.Crossref, Google Scholar · Zbl 1310.15064 · doi:10.1080/03081087.2013.869591
[46] Shapiro A (2003) Monte Carlo sampling methods. Ruszczyński A, Shapiro A, eds. Stochastic Programming, Handbook in Operations Research and Management Science, vol. 10 (North-Holland, Amsterdam), 353-425.Crossref, Google Scholar · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10006-0
[47] Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar · Zbl 1302.90003 · doi:10.1137/1.9781611973433
[48] Watters LJ (1967) Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15(6):1171-1174.Link, Google Scholar
[49] Wiesemann W, Kuhn D, Rustem B (2012) Robust resource allocations in temporal networks. Math. Programming 135(1-2):437-471.Crossref, Google Scholar · Zbl 1262.90031 · doi:10.1007/s10107-011-0478-7
[50] Xia Y, Yang MH, Golany B, Gilbert S, Yu G (2004) Real-time disruption management in a two-stage production and inventory system. IIE Trans. 36(2):111-125.Crossref, Google Scholar · doi:10.1080/07408170490245379
[51] Xu G, Burer S (2018) A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides. Comput. Optim. Appl. 70(1):33-59.Crossref, Google Scholar · Zbl 1417.90150 · doi:10.1007/s10589-017-9974-x
[52] Xu H, · Zbl 1235.68209
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.