×

An approximation scheme for distributionally robust nonlinear optimization. (English) Zbl 1448.90068

Summary: We consider distributionally robust optimization problems (DROPs) with nonlinear and nonconcave dependence on uncertain parameters. The DROP can be written as a nonsmooth, nonlinear program with a bilevel structure; the objective function and each of the constraint functions are suprema of expected values of parametric functions taken over an ambiguity set of probability distributions. We define ambiguity sets through moment constraints, and to make the computation of first order stationary points tractable, we approximate nonlinear functions using quadratic expansions w.r.t. parameters, resulting in lower-level problems defined by trust-region problems and semidefinite programs. Subsequently, we construct smoothing functions for the approximate lower level functions which are computationally tractable, employing strong duality for trust-region problems, and show that gradient consistency holds. We formulate smoothed DROPs and apply a homotopy method that dynamically decreases smoothing parameters and establish its convergence to stationary points of the approximate DROP under mild assumptions. Through our scheme, we provide a new approach to robust nonlinear optimization as well. We perform numerical experiments and comparisons to other methods on a well-known test set, assuming design variables are subject to implementation errors, which provides a representative set of numerical examples.

MSC:

90C17 Robustness in mathematical programming
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
49M37 Numerical methods based on nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Andreani, G. Haeser, and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization, 60 (2011), pp. 627-641, https://doi.org/10.1080/02331930903578700. · Zbl 1225.90123
[2] A. Ben-Tal, D. den Hertog, and J.-P. Vial, Deriving robust counterparts of nonlinear uncertain inequalities, Math. Program., 149 (2015), pp. 265-299, https://doi.org/10.1007/s10107-014-0750-8. · Zbl 1308.65089
[3] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization, Princeton Ser. Appl. Math., Princeton University Press, Princeton, NJ, 2009. · Zbl 1221.90001
[4] A. Ben-Tal and A. Nemirovski, Robust solutions of linear programming problems contaminated with uncertain data, Math. Program., 88 (2000), pp. 411-424, https://doi.org/10.1007/PL00011380. · Zbl 0964.90025
[5] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, MPS-SIAM Ser. Optim. 2, SIAM, Philadelphia, 2001, https://doi.org/10.1137/1.9780898718829. · Zbl 0986.90032
[6] A. Ben-Tal and M. Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72 (1996), pp. 51-63, https://doi.org/10.1007/BF02592331. · Zbl 0851.90087
[7] D. Bertsimas, D. B. Brown, and C. Caramanis, Theory and applications of robust optimization, SIAM Rev., 53 (2011), pp. 464-501, https://doi.org/10.1137/080734510. · Zbl 1233.90259
[8] D. Bertsimas, O. Nohadani, and K. M. Teo, Nonconvex robust optimization for problems with constraints, INFORMS J. Comput., 22 (2010), pp. 44-58, https://doi.org/10.1287/ijoc.1090.0319. · Zbl 1243.90176
[9] D. Bertsimas, O. Nohadani, and K. M. Teo, Robust optimization for unconstrained simulation-based problems, Oper. Res., 58 (2010), pp. 161-178, https://doi.org/10.1287/opre.1090.0715. · Zbl 1226.90074
[10] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM Rev., 59 (2017), pp. 65-98, https://doi.org/10.1137/141000671. · Zbl 1356.68030
[11] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Ser. Oper. Res., Springer Science & Business Media, New York, 2000, https://doi.org/10.1007/978-1-4612-1394-9. · Zbl 0966.49001
[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004, https://doi.org/10.1017/CBO9780511804441. · Zbl 1058.90049
[13] V. V. Buldygin and Y. V. Kozachenko, Metric Characterization of Random Variables and Random Processes, Transl. Math. Monogr. 188, American Mathematical Society, Providence, RI, 2000. · Zbl 0998.60503
[14] J. V. Burke and T. Hoheisel, Epi-convergent smoothing with applications to convex composite functions, SIAM J. Optim., 23 (2013), pp. 1457-1479, https://doi.org/10.1137/120889812. · Zbl 1278.49018
[15] J. V. Burke and T. Hoheisel, Epi-convergence properties of smoothing by infimal convolution, Set-Valued Var. Anal., 25 (2017), pp. 1-23, https://doi.org/10.1007/s11228-016-0362-y. · Zbl 1365.49015
[16] J. V. Burke, T. Hoheisel, and C. Kanzow, Gradient consistency for integral-convolution smoothing functions, Set-Valued Var. Anal., 21 (2013), pp. 359-376, https://doi.org/10.1007/s11228-013-0235-6. · Zbl 1321.49027
[17] J. V. Burke, A. S. Lewis, and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15 (2005), pp. 751-779, https://doi.org/10.1137/030601296. · Zbl 1078.65048
[18] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134 (2012), pp. 71-99, https://doi.org/10.1007/s10107-012-0569-0. · Zbl 1266.90145
[19] X. Chen, H. Qi, L. Qi, and K.-L. Teo, Smooth convex approximation to the maximum eigenvalue function, J. Global Optim., 30 (2004), pp. 253-270, https://doi.org/10.1007/s10898-004-8271-2. · Zbl 1066.90081
[20] Z. Chen, M. Sim, and H. Xu, Distributionally robust optimization with infinitely constrained ambiguity sets, Oper. Res., 67 (2019), pp. 1328-1344, https://doi.org/10.1287/opre.2018.1799. · Zbl 1455.90117
[21] F. H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc., 205 (1975), pp. 247-262, https://doi.org/10.1090/S0002-9947-1975-0367131-6. · Zbl 0307.26012
[22] F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990, https://doi.org/10.1137/1.9781611971309. · Zbl 0696.49002
[23] E. Delage and Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58 (2010), pp. 595-612, https://doi.org/10.1287/opre.1090.0741. · Zbl 1228.90064
[24] M. Diehl, H. G. Bock, and E. Kostina, An approximation technique for robust nonlinear optimization, Math. Program., 107 (2006), pp. 213-230, https://doi.org/10.1007/s10107-005-0685-1. · Zbl 1134.90039
[25] J. Dutta, K. Deb, R. Tulshyan, and R. Arora, Approximate KKT points and a proximity measure for termination, J. Global Optim., 56 (2013), pp. 1463-1499, https://doi.org/10.1007/s10898-012-9920-5. · Zbl 1297.90150
[26] P. M. Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), pp. 115-166, https://doi.org/10.1007/s10107-017-1172-1. · Zbl 1433.90095
[27] A. V. Fiacco and Y. Ishizuka, Sensitivity and stability analysis for nonlinear programming, Ann. Oper. Res., 27 (1990), pp. 215-235, https://doi.org/10.1007/BF02055196. · Zbl 0718.90086
[28] J. Fiala, M. Kočvara, and M. Stingl, PENLAB: A MATLAB Solver for Nonlinear Semidefinite Optimization, preprint, https://arxiv.org/abs/1311.5240, 2013.
[29] A. Forsgren, P. E. Gill, and M. H. Wright, Interior methods for nonlinear optimization, SIAM Rev., 44 (2002), pp. 525-597, https://doi.org/10.1137/S0036144502414942. · Zbl 1028.90060
[30] R. Gao and A. J. Kleywegt, Distributionally Robust Stochastic Optimization with Wasserstein Distance, preprint, https://arxiv.org/abs/1604.02199, 2016.
[31] J. Goh and M. Sim, Distributionally robust optimization and its tractable approximations, Oper. Res., 58 (2010), pp. 902-917, https://doi.org/10.1287/opre.1090.0795. · Zbl 1228.90067
[32] W. W. Hogan, Point-to-set maps in mathematical programming, SIAM Rev., 15 (1973), pp. 591-603, https://doi.org/10.1137/1015073. · Zbl 0256.90042
[33] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013, https://doi.org/10.1017/9781139020411. · Zbl 1267.15001
[34] B. Houska and M. Diehl, Nonlinear robust optimization via sequential convex bilevel programming, Math. Program., 142 (2013), pp. 539-577, https://doi.org/10.1007/s10107-012-0591-2. · Zbl 1282.90240
[35] C. Kanzow and A. Schwartz, The price of inexactness: Convergence properties of relaxation methods for mathematical programs with complementarity constraints revisited, Math. Oper. Res., 40 (2014), pp. 253-275, https://doi.org/10.1287/moor.2014.0667. · Zbl 1344.90058
[36] N. Karmitsa, Solver-o-matic, http://napsu.karmitsa.fi/solveromatic/, 2012, accessed September 12, 2019.
[37] N. Karmitsa, A. Bagirov, and M. M. Mäkelä, Comparing different nonsmooth minimization methods and software, Optim. Methods Softw., 27 (2012), pp. 131-153, https://doi.org/10.1080/10556788.2010.526116. · Zbl 1242.90233
[38] P. Kolvenbach, O. Lass, and S. Ulbrich, An approach for robust PDE-constrained optimization with application to shape optimization of electrical engines and of dynamic elastic structures under uncertainty, Optim. Eng., 19 (2018), pp. 697-731, https://doi.org/10.1007/s11081-018-9388-3. · Zbl 1507.49020
[39] O. Lass and S. Ulbrich, Model order reduction techniques with a posteriori error control for nonlinear robust optimization governed by partial differential equations, SIAM J. Sci. Comput., 39 (2017), pp. S112-S139, https://doi.org/10.1137/16M108269X. · Zbl 1428.35644
[40] A. S. Lewis, Derivatives of spectral functions, Math. Oper. Res., 21 (1996), pp. 576-588, https://doi.org/10.1287/moor.21.3.576. · Zbl 0860.49017
[41] A. S. Lewis, Nonsmooth analysis of eigenvalues, Math. Program., 84 (1999), pp. 1-24, https://doi.org/10.1007/s10107980004a. · Zbl 0969.49006
[42] A. S. Lewis and M. L. Overton, Nonsmooth optimization via quasi-Newton methods, Math. Program., 141 (2013), pp. 135-163, https://doi.org/10.1007/s10107-012-0514-2. · Zbl 1280.90118
[43] M. M. Mäkelä, Multiobjective Proximal Bundle Method for Nonconvex Nonsmooth Optimization: Fortran Subroutine MPBNGC 2.0, Reports of the Department of Mathematical Information Technology, Series B, Scientific Computing B 13/2003, University of Jyväskylä, Jyväskylä, 2003.
[44] M. M. Mäkelä, N. Karmitsa, and O. Wilppu, Proximal bundle method for nonsmooth and nonconvex multiobjective optimization, in Mathematical Modeling and Optimization of Complex Structures, P. Neittaanmäki, S. Repin, and T. Tuovinen, eds., Comput. Methods Appl. Sci. 40, Springer, Cham, 2016, pp. 191-204, https://doi.org/10.1007/978-3-319-23564-6_12.
[45] M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Singapore, Singapore, 1992, https://doi.org/10.1142/1493. · Zbl 0757.49017
[46] J. J. Moré, B. S. Garbow, and K. E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Softw., 7 (1981), pp. 17-41. · Zbl 0454.65049
[47] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput., 4 (1983), pp. 553-572, https://doi.org/10.1137/0904038. · Zbl 0551.65042
[48] Yu. Nesterov, Smoothing technique and its applications in semidefinite optimization, Math. Program., 110 (2007), pp. 245-259, https://doi.org/10.1007/s10107-006-0001-8. · Zbl 1126.90058
[49] Yu. Nesterov and A. Nemirovski, Interior-Point Polynomial Algorithms in Convex Programming, SIAM Stud. Appl. Math. 13, SIAM, Philadelphia, 1994, https://doi.org/10.1137/1.9781611970791. · Zbl 0824.90112
[50] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, J. Optim. Theory Appl., 169 (2016), pp. 1042-1068, https://doi.org/10.1007/s10957-016-0892-3. · Zbl 1342.90136
[51] E. Polak, J. O. Royset, and R. Womersley, Algorithms with adaptive smoothing for finite minimax problems, J. Optim. Theory Appl., 119 (2003), pp. 459-484, https://doi.org/10.1023/B:JOTA.0000006685.60019.3e. · Zbl 1061.90117
[52] J. Revels, M. Lubin, and T. Papamarkou, Forward-Mode Automatic Differentiation in Julia, preprint, https://arxiv.org/abs/1607.07892, 2016.
[53] A. Shapiro, Distributionally robust stochastic programming, SIAM J. Optim., 27 (2017), pp. 2258-2275, https://doi.org/10.1137/16M1058297. · Zbl 1373.90089
[54] A. Shapiro and A. Kleywegt, Minimax analysis of stochastic problems, Optim. Methods Softw., 17 (2002), pp. 523-542, https://doi.org/10.1080/1055678021000034008. · Zbl 1040.90030
[55] A. M.-C. So, Moment inequalities for sums of random matrices and their applications in optimization, Math. Program., 130 (2011), pp. 125-151, https://doi.org/10.1007/s10107-009-0330-5. · Zbl 1231.60007
[56] D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19 (1982), pp. 409-426, https://doi.org/10.1137/0719026. · Zbl 0483.65039
[57] S. Steffensen and M. Ulbrich, A new relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 20 (2010), pp. 2504-2539, https://doi.org/10.1137/090748883. · Zbl 1231.90350
[58] R. J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5 (1995), pp. 286-313, https://doi.org/10.1137/0805016. · Zbl 0846.49017
[59] P. D. Tao and L. T. H. An, Lagrangian stability and global optimality in nonconvex quadratic minimization over Euclidean balls and spheres, J. Convex Anal., 2 (1995), pp. 263-276. · Zbl 0848.49022
[60] N.-K. Tsing, M. K. Fan, and E. I. Verriest, On analyticity of functions involving eigenvalues, Linear Algebra Appl., 207 (1994), pp. 159-180, https://doi.org/10.1016/0024-3795(94)90009-4. · Zbl 0805.15022
[61] A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25-57, https://doi.org/10.1007/s10107-004-0559-y. · Zbl 1134.90542
[62] M. J. Weinstein and A. V. Rao, Algorithm 984: ADiGator, a toolbox for the algorithmic differentiation of mathematical functions in MATLAB using source transformation via operator overloading, ACM Trans. Math. Softw., 44 (2017), 21, https://doi.org/10.1145/3104990. · Zbl 1484.65363
[63] W. Wiesemann, D. Kuhn, and M. Sim, Distributionally robust convex optimization, Oper. Res., 62 (2014), pp. 1358-1376, https://doi.org/10.1287/opre.2014.1314. · Zbl 1327.90158
[64] M. Xu, J. J. Ye, and L. Zhang, Smoothing SQP methods for solving degenerate nonsmooth constrained optimization problems with applications to bilevel programs, SIAM J. Optim., 25 (2015), pp. 1388-1410, https://doi.org/10.1137/140971580. · Zbl 1317.65148
[65] Y. Xu, W. Sun, and L. Qi, A feasible direction method for the semidefinite program with box constraints, Appl. Math. Lett., 24 (2011), pp. 1874-1881, https://doi.org/10.1016/j.aml.2011.05.010. · Zbl 1231.65108
[66] H. Yamashita and H. Yabe, A survey of numerical methods for nonlinear semidefinite programming, J. Oper. Res. Soc. Japan, 58 (2015), pp. 24-60, https://doi.org/10.15807/jorsj.58.24. · Zbl 1367.65092
[67] Y. Zhang, General robust-optimization formulation for nonlinear programming, J. Optim. Theory Appl., 132 (2007), pp. 111-124, https://doi.org/10.1007/s10957-006-9082-z. · Zbl 1138.90483
[68] C. Zhao and Y. Guan, Data-driven risk-averse stochastic optimization with Wasserstein metric, Oper. Res. Lett., 46 (2018), pp. 262-267, https://doi.org/10.1016/j.orl.2018.01.011. · Zbl 1525.90316
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.