Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models. (English) Zbl 1430.90557
Summary: We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric and can account for a bounded support. We show that this class of DRO problems can be reformulated as decomposable semi-infinite programs. We use a cutting-surface method to solve the reformulated problem for the general nonlinear model, assuming that we have a separation oracle. As examples, we consider the problems arising from the machine learning models where variables couple with data in a bilinear form in the loss function. We present a branch-and-bound algorithm to solve the separation problem for this case using an iterative piece-wise linear approximation scheme. We use a distributionally robust generalization of the logistic regression model to test our algorithm. We also show that it is possible to approximate the logistic-loss function with significantly less linear pieces than those needed for a general loss function to achieve a given accuracy when generating a cutting surface. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20-50 to achieve 5-digit precision. The solution found by the model has better predicting power than classical logistic regression when the sample size is small.
MSC:
| 90C47 | Minimax problems in mathematical programming |
| 90C15 | Stochastic programming |
| 60B10 | Convergence of probability measures |
| 62J02 | General nonlinear regression |
| 90C34 | Semi-infinite programming |
Keywords:
robustness and sensitivity analysis; distributionally robust optimization; Wasserstein metric; semi-infinite programming; logistic regressionReferences:
| [1] | Adjiman, C. S.; Dallwig, S.; Floudas, C. A.; Neumaier, A., A global optimization method, \(α\) BB, for general twice-differentiable NLPs-I. theoretical advances, Computers Chemical Engineering, 22, 9, 1137-1158 (1998) |
| [2] | Adjiman, C. S.; Dallwig, S.; Floudas, C. A.; Neumaier, A., A global optimization method, \(α\) BB, for general twice-differentiable NLPs-II. implementation and computational results, Computers Chemical Engineering, 22, 9, 1159-1179 (1998) |
| [3] | Bansal, M., Huang, K., & Mehrotra, S. (2017). Decomposition algorithms for two-stage distributionally robust mixed binary programs. http://www.optimization-online.org/DB_FILE/2017/02/5849.pdf; Bansal, M., Huang, K., & Mehrotra, S. (2017). Decomposition algorithms for two-stage distributionally robust mixed binary programs. http://www.optimization-online.org/DB_FILE/2017/02/5849.pdf · Zbl 1401.90126 |
| [4] | Barrio, E. D.; Gine, E.; Matran, C., Central limit theorems for the Wasserstein distance between the empirical and the true distributions, The Annals of Probability, 27, 2, 1009-1071 (1999) · Zbl 0958.60012 |
| [5] | Ben-Tal, A.; Hertog, D.; Waegenaere, A. D.; Melenberg, B.; Rennen, G., Robust solutions of optimization problems affected by uncertain probabilities, Management Science, 59, 341-357 (2013) |
| [6] | Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Mathematics of Operations Research, 23, 769-805 (1998) · Zbl 0977.90052 |
| [7] | Ben-Tal, A.; Nemirovski, A., Robust solutions to uncertain linear programs, Operations Research Letters, 25, 1-13 (1999) · Zbl 0941.90053 |
| [8] | Ben-Tal, A.; Nemirovski, A.; Roos, C., Robust solutions of uncertain quadratic and conic-quadratic problems, SIAM Journal on Optimization, 13, 2, 535-560 (2002) · Zbl 1026.90065 |
| [9] | Benson, H. P., Fractional programming with convex quadratic forms and functions, European Journal of Operational Research, 173, 351-369 (2006) · Zbl 1113.90122 |
| [10] | Benson, H. P., A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, European Journal of Operational Research, 182, 2, 597-611 (2007) · Zbl 1121.90102 |
| [11] | Benson, H. P., Solving sum of ratios fractional programs via concave minimization, Journal of Optimization Theory and Applications, 135, 1-17 (2007) · Zbl 1145.90089 |
| [12] | Bertsimas, D.; Doan, X. V.; Natarajan, K.; Teo, C., Models for minimax stochastic linear optimization problems with risk aversion, Mathematics of Operations Research, 35, 3, 580-602 (2010) · Zbl 1218.90215 |
| [13] | Bertsimas, D., Gupta, V., & Kallus, N. (2013). Data-driven robust optimization. https://arxiv.org/pdf/1401.0212v2.pdf; Bertsimas, D., Gupta, V., & Kallus, N. (2013). Data-driven robust optimization. https://arxiv.org/pdf/1401.0212v2.pdf · Zbl 1397.90298 |
| [14] | Bertsimas, D.; Popescu, I., Optimal inequalities in probability theory: A convex optimization approach, SIAM Journal on Optimization, 15, 780-804 (2005) · Zbl 1077.60020 |
| [15] | Bertsimas, D.; Sim, M., Tractable approximations to robust conic optimization problems, Mathematical Programming, 107, 5-36 (2006) · Zbl 1134.90026 |
| [16] | Birge, J. R.; Wets, R. J.-B., Computing bounds for stochastic programming problems by means of a generalized moment problem, Mathematics of Operations Research, 12(1), 149-162 (1987) · Zbl 0619.90053 |
| [17] | Blanchet, J., & Murthy, K. (2017). Quantifying distributional model via optimal transport. https://arxiv.org/pdf/1604.01446.pdf; Blanchet, J., & Murthy, K. (2017). Quantifying distributional model via optimal transport. https://arxiv.org/pdf/1604.01446.pdf |
| [18] | Bolley, F.; Guillin, A.; Villani, C., Quantitative concentration inequalities for empirical measures on non-compact spaces, Probability Theory and Related Fields, 137, 3, 541-593 (2007) · Zbl 1113.60093 |
| [19] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press · Zbl 1058.90049 |
| [20] | Burkard, R. E.; Hamacher, H. W.; Rote, G., Sandwich approximation of univariate convex functions with an application to separable convex programming, Naval Research Logistics, 38, 911-924 (1991) · Zbl 0755.90066 |
| [21] | Calafiore, G. C., Ambiguous risk measures and optimal robust portfolios, SIAM Journal on Optimization, 18, 3, 853-877 (2007) · Zbl 1154.91022 |
| [22] | Delage, E.; Ye, Y., Distributional robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58, 3, 595-612 (2010) · Zbl 1228.90064 |
| [23] | Dupačová, J., The minimax approach to stochastic programming and an illustrative application, Stochastics, 20, 73-88 (1987) · Zbl 0616.90046 |
| [24] | Erdoğan, E.; Iyengar, G., Ambiguous chance constrained problems and robust optimization, Mathematical Programming, 107, 37-61 (2006) · Zbl 1134.90028 |
| [25] | Esfahani, P. M., & Kuhn, D. (2015). Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulatioins. https://arxiv.org/pdf/1505.05116.pdf; Esfahani, P. M., & Kuhn, D. (2015). Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulatioins. https://arxiv.org/pdf/1505.05116.pdf · Zbl 1433.90095 |
| [26] | Fournier, N.; Guillin, A., On the rate of convergence in Wasserstein distance of the empirical measure, Probability Theory and Related Fields, 162, 3, 707-738 (2015) · Zbl 1325.60042 |
| [27] | Gao, R., & Kleywegt, A. J. (2016). Distributionally robust stochastic optimization with Wasserstein distance. https://arxiv.org/pdf/1604.02199.pdf; Gao, R., & Kleywegt, A. J. (2016). Distributionally robust stochastic optimization with Wasserstein distance. https://arxiv.org/pdf/1604.02199.pdf |
| [28] | Givens, C. R.; Shortt, R. M., A class of Wasserstein metrics for probability distributions, Michigan Mathematical Journal, 31, 2, 231-240 (1984) · Zbl 0582.60002 |
| [29] | Goh, J.; Sim, M., Distributionally robust optimization and its tractable approximations, Operations Research, 58, 4, 902-917 (2010) · Zbl 1228.90067 |
| [30] | Hettich, R.; Kortanek, K. O., Semi-infinite programming: Theory, methods, and applications, SIAM Review, 35, 3, 380-429 (1993) · Zbl 0784.90090 |
| [31] | Jiang, R., & Guan, Y. (2015). Risk-averse two-stage stochastic program with distributional ambiguity. https://www.optimization-online.org/DB_FILE/2015/05/4908.pdf; Jiang, R., & Guan, Y. (2015). Risk-averse two-stage stochastic program with distributional ambiguity. https://www.optimization-online.org/DB_FILE/2015/05/4908.pdf |
| [32] | Jiang, R.; Guan, Y., Data-driven chance constrained stochastic program, Mathematical Programming, 158, 291-327 (2016) · Zbl 1346.90640 |
| [33] | Jiao, H.; Guo, Y.; Shen, P., Global optimization of generalized linear fractional programming with nonlinear constraints, Applied Mathematics and Computation, 183, 717-728 (2006) · Zbl 1111.65052 |
| [34] | Kortanek, K. O.; No, H., A central cutting plane algorithm for convex semi-infinite programming problems, SIAM Journal on Optimization, 3, 4, 901-918 (1993) · Zbl 0790.90070 |
| [35] | Li, J.; Stoica, P.; Wang, Z., On robust capon beam forming and diagonal loading, IEEE Transactions on Signal Processing, 51, 7, 1702-1715 (2003) |
| [36] | Lin, Q.; Loxton, R.; Teo, K. L.; Wu, Y. H.; Yu, C. J., A new exact penalty method for semi-infinite programming problems, Journal of Computational and Applied Mathematics, 261, 271-286 (2014) · Zbl 1278.90410 |
| [37] | Lorenz, R.; Boyd, S., Robust minimum variance beamforming, IEEE Transactions on Signal Processings, 53, 1684-1696 (2005) · Zbl 1370.78279 |
| [38] | Love, D. K., & Bayraksan, G. (2016). Phi-divergence constrained ambiguous stochastic programs for data-driven optimization. http://www.optimization-online.org/DB_HTML/2016/03/5350.html; Love, D. K., & Bayraksan, G. (2016). Phi-divergence constrained ambiguous stochastic programs for data-driven optimization. http://www.optimization-online.org/DB_HTML/2016/03/5350.html |
| [39] | Mehrotra, S.; Papp, D., Generating moment matching scenarios using optimization techniques, SIAM Journal on Optimization, 23, 2, 963-999 (2013) · Zbl 1273.90137 |
| [40] | Mehrotra, S.; Papp, D., A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization, SIAM Journal on Optimization, 24, 4, 1670-1697 (2015) · Zbl 1330.90119 |
| [41] | Mehrotra, S.; Zhang, H., Models and algorithms for distributionally robust least squares problems, Mathematical Programming, 146, 123-141 (2014) · Zbl 1293.93790 |
| [42] | Mutapcic, A.; Boyd, S., Cutting-set methods for robust convex optimization with pessimizing oracles, Optimization Methods & Software, 24, 3, 381-406 (2009) · Zbl 1173.90502 |
| [43] | Nesterov, Y.; Nemirovski, A., Interior-point polynomial algorithms in convex programming (1994), Society of Industrial and Applied Mathematics · Zbl 0824.90112 |
| [44] | Pflug, G. C.; Pichler, A.; Wozabal, D., Then 1/n investment strategy is optimal under high model ambiguity, Journal of Banking and Finance, 36, 410-417 (2012) |
| [45] | Plug, G.; Wozabal, D., Ambiguity in portfolio selection, Quantitative Finance, 7, 4, 435-442 (2007) · Zbl 1190.91138 |
| [46] | Popescu, I., Robust mean-covariance solutions for stochastic optimization, Operations Research, 55, 1, 98-112 (2007) · Zbl 1167.90611 |
| [47] | Prékopa, A., Stochastic programming. Stochastic programming, Mathematics and Its Applications, 324 (1995), Springer Netherlands · Zbl 0834.90098 |
| [48] | Scarf, H., A min-max solution of an inventory problem, (Arrow, K.; Karlin, S.; Scarf, H., Studies in the mathematical theory of inventory and production (1958), Stanford University Press), 201-209 · Zbl 0079.36003 |
| [49] | Shafieezadeh-Abadeh, S.; Esfahani, P. M.; Kuhn, D., Distributionally robust logistic regression, Proceedings of the advances in neural information processing system (nips) (2015) |
| [50] | Shapiro, A.; Ahmed, S., On a class of minimax stochastic programs, SIAM Journal on Optimization, 14, 4, 1237-1249 (2004) · Zbl 1073.90027 |
| [51] | Shapiro, A.; Kleywegt, A., Minimax analysis of stochastic problems, Optimization Methods and Software, 17, 523-542 (2002) · Zbl 1040.90030 |
| [52] | Shen, P. P.; Yuan, G. X., Global optimization for the sum of generalized polynomial fractional functions, Mathematical Methods of Operational Research, 65, 3, 445-459 (2007) · Zbl 1180.90331 |
| [53] | Sherali, H. D., Global optimization of nonconvex polynomial programming problems having rational exponents, The Journal of Global Optimization, 12, 3, 267-283 (1998) · Zbl 0905.90146 |
| [54] | Vorobyov, S.; Gershman, A.; Luo, Z. Q., Robust adaptive beam forming using worst-case performance optimization: a solution to the signal mismatch problem, IEEE Transactions on Signal Processing, 51, 2, 313-324 (2003) |
| [55] | Wächter, A.; Biegler, L. T., On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57 (2006) · Zbl 1134.90542 |
| [56] | Wang, S.; Yuan, Y., Feasible method for semi-infinite programs, SIAM Journal on Optimization, 25, 4, 2537-2560 (2015) · Zbl 1329.90148 |
| [57] | Wang, Y.; Shen, P.; Zhian, L., A branch-and-bound algorithm to globally solve the sum of several linear ratios, Applied Mathematics and Computation, 168, 89-101 (2005) · Zbl 1079.65071 |
| [58] | Wang, Y. J.; Liang, Z., A deterministic global optimization algorithm for generalized geometric programming, Applied Mathematics and Computation, 168, 722-737 (2005) · Zbl 1105.65335 |
| [59] | Wang, Z.; Glynn, P. W.; Ye, Y., Likelihood robust optimization for data-driven problems, Computational Management Science, 13, 241-261 (2016) · Zbl 1397.90225 |
| [60] | Wiesemann, W.; Kuhn, D.; Sim, M., Distributional robust convex optimization, Operations Research, 62, 1358-1376 (2015) · Zbl 1327.90158 |
| [61] | Wozabal, D., A framework for optimization under ambiguity, Annals of Operations Research, 193, 21-47 (2012) · Zbl 1255.91454 |
| [62] | Xu, H.; Caramanis, C.; Mannor, S., A distributional interpretation of robust optimization, Mathematics of Operations Research, 37, 1, 95-110 (2012) · Zbl 1243.90167 |
| [63] | Xu, M.; Wu, S. Y.; Ye, J. J., Solving semi-infinite programs by smoothing projected gradient method, Computational Optimization and Applications, 59, 591-616 (2014) · Zbl 1308.65101 |
| [64] | Yang, X. Q., Chen, Z. Y., & Zhou, J. C. (2015). Optimality conditions for semi-infinite and generalized semi-infinite programs via \(l_p\)http://www.mypolyuweb.hk/ mayangxq/2015YCZ.pdf; Yang, X. Q., Chen, Z. Y., & Zhou, J. C. (2015). Optimality conditions for semi-infinite and generalized semi-infinite programs via \(l_p\)http://www.mypolyuweb.hk/ mayangxq/2015YCZ.pdf |
| [65] | Yanıkoğlu, İ.; Hertog, D., Safe approximations of ambiguous chance constraints using historical data, INFORMS Journal on Computing, 25, 4, 666-681 (2013) |
| [66] | Zamora, J. M.; Grossmann, I. E., Continuous global optimization of structured process systems models, Computers and Chemical Engineering, 22, 12, 1749-1770 (1998) |
| [67] | Zymler, S.; Kuhn, D.; Rustem, B., Distributional robust joint chance constraints with second-order moment information, Mathematical Programming, 137, 167-198 (2013) · Zbl 1286.90103 |
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.
