Minkowski Centers via Robust Optimization: Computation and Applications

References

• Bandi C, Bertsimas D (2012) Tractable stochastic analysis in high dimensions via robust optimization. Math. Programming 134(1):23–70.Crossref, Google Scholar
• Barnes ER, Moretti AC (2005) Some results on centers of polytopes. Optim. Methods Software 20(1):9–24.Crossref, Google Scholar
• Bélisle C, Boneh A, Caron RJ (1998) Convergence properties of hit–and–run samplers. Stochastic Models 14(4):767–800.Crossref, Google Scholar
• Bélisle CJP, Romeijn HE, Smith RL (1993) Hit-and-run algorithms for generating multivariate distributions. Math. Oper. Res. 18(2):255–266.Link, Google Scholar
• Belloni A, Freund RM (2007) On the symmetry function of a convex set. Math. Programming 111(1–2):57–93.Crossref, Google Scholar
• Ben-Ameur W, Ouorou A, Wang G, Żotkiewicz M (2018) Multipolar robust optimization. EURO J. Comput. Optim. 6(4):395–434.Crossref, Google Scholar
• Ben-Tal A, den Hertog D (2014) Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Programming 143(1):1–29.Crossref, Google Scholar
• Ben-Tal A, den Hertog D, Vial JP (2015) Deriving robust counterparts of nonlinear uncertain inequalities. Math. Programming 149(1):265–299.Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351–376.Crossref, Google Scholar
• Bertsimas D, Goyal V (2012) On the power and limitations of affine policies in two-stage adaptive optimization. Math. Programming 134(2):491–531.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011a) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Dunning I, Lubin M (2016) Reformulation vs. cutting-planes for robust optimization. Comput. Management Sci. 13(2):195–217.Crossref, Google Scholar
• Bertsimas D, Goyal V, Lu BY (2015) A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization. Math. Programming 150(2):281–319.Crossref, Google Scholar
• Bertsimas D, Goyal V, Sun XA (2011b) A geometric characterization of the power of finite adaptability in multistage stochastic and adaptive optimization. Math. Oper. Res. 36(1):24–54.Link, Google Scholar
• Bertsimas D, Iancu DA, Parrilo PA (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Bertsimas D, Hertog DD, Pauphilet J, Zhen J (2022) Robust convex optimization: A new perspective that unifies and extends. Math. Programming 1–42. https://link.springer.com/article/10.1007/s10107-022-01881-w.Crossref, Google Scholar
• Bertsimas D, Litvinov E, Sun XA, Zhao J, Zheng T (2012) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans. Power Systems 28(1):52–63.Crossref, Google Scholar
• Bland RG, Goldfarb D, Todd MJ (1981) The ellipsoid method: A survey. Oper. Res. 29(6):1039–1091.Link, Google Scholar
• Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Boyd SP, Vandenberghe L, Skaf J (2008) Analytic Center Cutting-Plane Method. Lecture Notes from Stanford University (Stanford University, Stanford, CA).Google Scholar
• Caron RJ, Greenberg HJ, Holder AG (2002) Analytic centers and repelling inequalities. Eur. J. Oper. Res. 143(2):268–290.Crossref, Google Scholar
• Chen MH, Schmeiser B (1993) Performance of the Gibbs, hit-and-run, and metropolis samplers. J. Comput. Graphics Statist. 2:251–272.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48.Crossref, Google Scholar
• Díaz J, Cuevas A, Grande F (2006) Testing multivariate uniformity: The distance-to-boundary method. Canadian J. Statist. 34(4):693–707.Google Scholar
• Eldar YC, Beck A, Teboulle M (2008) A minimax Chebyshev estimator for bounded error estimation. IEEE Trans. Signal Processing 56(4):1388–1397.Crossref, Google Scholar
• Elhedhli S, Goffin JL, Vial JP (2009) Nondifferentiable Optimization: Cutting Plane Methods (Springer, Boston).Google Scholar
• Gay DM (1985) Electronic mail distribution of linear programming test problems. Math. Programming Soc. COAL Newsletter 13:10–12.Google Scholar
• Gounaris CE, Repoussis PP, Tarantilis CD, Wiesemann W, Floudas CA (2016) An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Sci. 50(4):1239–1260.Link, Google Scholar
• Grimus W, Ecker G (1986) On the simultaneous diagonalizability of matrices. Technical report, Vienna University, Vienna.Google Scholar
• Güler O, Gürtuna F (2012) Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies. Optim. Methods Software 27(4–5):735–759.Crossref, Google Scholar
• Guslitser E (2002) Uncertainty-immunized solutions in linear programming. MS thesis, Technion, Israeli Institute of Technology, IE&M Faculty, Haifa, Israel.Google Scholar
• Hadjiyiannis MJ, Goulart PJ, Kuhn D (2011) A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. Proc. 50th IEEE Conf. on Decision and Control and Eur. Control Conf. (IEEE, Piscataway, NJ), 7386–7391.Google Scholar
• Hammer PC (1951) The centroid of a convex body. Proc. Amer. Math. Soc. 2(4):522–525.Crossref, Google Scholar
• Housni OE, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• Huard P (1967) Resolution of mathematical programming with nonlinear constraints by the method of centers. Abadie J, ed. Nonlinear Programming (Springer, Basel), 207–219.Google Scholar
• Iancu DA, Trichakis N (2014) Pareto efficiency in robust optimization. Management Sci. 60(1):130–147.Link, Google Scholar
• Jarre F (1989) On the method of analytic centers for solving smooth convex programs. Optim. - Fifth French-German Conf. Caster Novel 1988, Lecture Notes in Mathematics 1405 (Springer Verlag, Berlin), 69–85.Google Scholar
• John F (1948) Extreme problems with inequalities as subsidiary conditions, studies and essays. Traces and Emergence of Nonlinear Programming (Springer, Basel), 187–204.Google Scholar
• Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2002) An efficient k-means clustering algorithm: Analysis and implementation. IEEE Trans. Pattern Anal. Machine Intelligence 24(7):881–892.Crossref, Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Proc. 16th Annual ACM Sympos. on Theory of Comput. (Association for Computing Machinery, New York), 302–311.Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Klee V (1963) Convexity. Proc. 7th Sympos. in Pure Mathematics of the Amer. Math. Soc., vol. 7 (American Mathematical Society, Providence, RI).Google Scholar
• Lovász L (1999) Hit-and-run mixes fast. Math. Programming 86(3):443–461.Crossref, Google Scholar
• Minkowski H (1911) Allegemeine lehzätze über konvexe polyeder. Gesellschaft Abhandlungen Leipzog-Berlin 1:103–121.Google Scholar
• Motzkin TS (1936) Beiträge zur Theorie der Linearen Ungleichungen (Azriel Press, New York).Google Scholar
• Rademacher LA (2007) Approximating the centroid is hard. Proc. 23rd Annual Sympos. on Comput. Geometry (Association for Computing Machinery, New York), 302–305.Google Scholar
• Renegar J (1988) A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Programming 40(1):59–93.Crossref, Google Scholar
• Roos C, Terlaky T, Vial JP (2005) Interior Point Methods for Linear Optimization (Springer Science & Business Media, Boston).Google Scholar
• Schwartz JT, Sharir M (1988) A survey of motion planning and related geometric algorithms. Artificial Intelligence 37(1–3):157–169.Crossref, Google Scholar
• Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6):1296–1308.Link, Google Scholar
• Sonnevend G (1986) An “analytical center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. System Modelling and Optimization (Springer, Berlin), 866–875.Crossref, Google Scholar
• Tarasov SP, Khachiyan LG, Erlikh II (1988) The method of inscribed ellipsoids. Soviet Math. Doklady 37(1):226–230.Google Scholar
• Todd MJ (1982) On minimum volume ellipsoids containing part of a given ellipsoid. Math. Oper. Res. 7(2):253–261.Link, Google Scholar
• Uhlig F (1973) Definite and semidefinite matrices in a real symmetric matrix pencil. Pacific J. Math. 49(2):561–568.Crossref, Google Scholar
• Vaidya PM (1996) A new algorithm for minimizing convex functions over convex sets. Math. Programming 73(3):291–341.Crossref, Google Scholar
• Xia Y, Yang M, Wang S (2021) Chebyshev center of the intersection of balls: Complexity, relaxation and approximation. Math. Programming 187(1–2):287–315.Crossref, Google Scholar
• Yudin DB, Nemirovskii AS (1976) Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13(2):22–45.Google Scholar
• Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5):457–461.Crossref, Google Scholar
• Zhen J, den Hertog D (2018) Computing the maximum volume inscribed ellipsoid of a polytopic projection. INFORMS J. Comput. 30(1):31–42.Link, Google Scholar
• Zhen J, den Hertog D, Sim M (2018) Adjustable robust optimization via Fourier-Motzkin elimination. Oper. Res. 66(4):1086–1100.Link, Google Scholar