Nonconvex robust programming via value-function optimization
Tóm tắt
Convex programming based robust optimization is an active research topic in the past two decades, partially because of its computational tractability for many classes of optimization problems and uncertainty sets. However, many problems arising from modern operations research and statistical learning applications are nonconvex even in the nominal case, let alone their robust counterpart. In this paper, we introduce a systematic approach for tackling the nonconvexity of the robust optimization problems that is usually coupled with the nonsmoothness of the objective function brought by the worst-case value function. A majorization-minimization algorithm is presented to solve the penalized min-max formulation of the robustified problem that deterministically generates a “better” solution compared with the starting point (that is usually chosen as an unrobustfied optimal solution). A generalized saddle-point theorem regarding the directional stationarity is established and a game-theoretic interpretation of the computed solutions is provided. Numerical experiments show that the computed solutions of the nonconvex robust optimization problems are less sensitive to the data perturbation compared with the unrobustfied ones.
Tài liệu tham khảo
Ang, M., Sun, J., Yao, Q.: On the dual representation of coherent risk measures. Ann. Oper. Res. 262(1), 29–46 (2018)
Ba, Q., Pang, J.S.: Exact penalization of generalized Nash equilibrium problems. Oper. Res. (2020). https://doi.org/10.1287/opre.2019.1942
Ben-Tal, A., El-Ghoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464–501 (2011)
Bertsimas, D., Nohadani, O., Teo, K.M.: Robust optimization for unconstrained simulation-based problems. Oper. Res. 58(1), 161–178 (2010)
Bertsimas, D., Nohadani, O., Teo, K.M.: Nonconvex robust optimization for problems with constraints. INFORMS J. Comput. 22(1), 44–58 (2010)
Chen, X., Fukushima, M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30(4), 1022–1038 (2005)
Chen, X., Zhang, C., Fukushima, M.: Robust solution of monotone stochastic linear complementarity problems. Math. Progr. 117, 51–80 (2009)
Clarke, F.H.: Generalized gradients and applications. Trans. Am. Math. Soc. 205, 247–262 (1975)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Classics in Applied Mathematics, Volume 5, Society for Industrial and Applied Mathematics (1990) (Reprint from John Wiley Publishers, New York 1983)
Cui, Y., He, Z., Pang, J.S.: Multi-composite nonconvex optimization for training deep neural networks. SIAM J. Optim. 30(2), 1693–1723 (2020)
Cui, Y., Pang, J.S., Sen, B.: Composite difference-max programs for modern statistical estimation problems. SIAM J. Optim. 28(4), 3344–3374 (2018)
Danskin Jr., J.M.: The theory of max-min with applications. SIAM J. Appl. Math. 14(4), 641–664 (1966)
Demyanov, V.F., Di Pillo, G., Facchinei, F.: Exact penalization via Dini and Hadamard conditional derivatives. Optim. Methods Softw. 9(1–3), 19–36 (1998)
Di Pillo, G., Facchinei, F.: Exact penalty functions for nondifferentiable programming problems. In: Clarke, F.H., Demyanov, V.F., Giannessi, F. (eds.) Nonsmooth Optimization and Related Topics. Ettore Majorana International Science Serie, vol. 43, pp. 89–107. Springer, New York (1989)
Di Pillo, G., Facchinei, F.: Regularity conditions and exact penalty functions in Lipschitz programming problems. In: Giannessi, F. (ed.) Nonsmooth Optimization Methods and Applications, pp. 107–120. Gordon and Breach, New York (1992)
Di Pillo, G., Grippo, L.: Exact penalty functions in constrained optimization. SIAM J. Control Optim. 27(6), 1333–1360 (1988)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003)
Facchinei, F., Pang, J.S., Scutari, G.: Non-cooperative games with minmax objectives. Comput. Optim. Appl. 59(1–2), 85–112 (2014)
Goldfarb, D., Iyengar, G.: Robust portfolio selection problems. Math. Oper. Res. 28(1), 1–38 (2003)
Goodfellow, I., Shlens, J., Szegedy, C.: Explaining and harnessing adversarial examples. In: International Conference on Learning Representations (2015)
Gorissen, B., Yanıkoǧlu, I., den Hertog, D.: A practical guide to robust optimization. Omega 53, 124–137 (2015)
Hu, J., Mitchell, J., Pang, J.S., Yu, B.: On linear programs with linear complementarity constraints. J. Glob. Optim. 53(1), 29–51 (2012)
Lange, K.: MM Optimization Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (2016)
Leyffer, S., Menickelly, M., Munson, T., Vanaret, C., Wild, S.M.: Nonlinear robust optimization. Preprint ANL/MCS-P9040-0218, Mathematics and Computer Science Division, Argonne National Laboratory (2018)
Li, W., Singer, I.: Global error bounds for convex multifunctions and applications. Math. Oper. Res. 23(2), 443–462 (1998)
Lu, Z., Sun, Z., Zhou, Z.: Enhanced proximal DC algorithms with extrapolation for a class of structured nonsmooth DC minimization. Math. Progr., Ser. B 176(1–2), 369–401 (2019)
Luo, Z.Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
Luo, Z.Q., Tseng, P.: Perturbation analysis of a condition number for linear systems. SIAM J. Matrix Anal. Appl. 15(2), 636–660 (1994)
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A.: Towards deep learning models resistant to adversarial attacks. In: International Conference on Learning Representations (2018)
Nesterov, Y.: A method of solving a convex programming problem with convergence rate \(O(1/k^2)\). Sov. Math. Dokl. 27, 372–376 (1983)
Ng, K.F., Zheng, X.Y.: Error bounds for lower semicontinuous functions in normed spaces. SIAM J. Optim. 12(1), 1–17 (2001)
Pang, J.S.: Error bounds in mathematical programming. Math. Progr., Ser. B 79(1–3), 299–332 (1997)
Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth dc programs. Math. Oper. Res. 42(1), 95–118 (2016)
Pang, J.S., Scutari, G.: Nonconvex games with side constraints. SIAM J. Optim. 21(4), 1491–1522 (2011)
Papernot, N., McDaniel, P., Jha, S., Fredrikson, M., Celik, Z.B., Z. B., Swami, A.: The limitations of deep learning in adversarial settings. In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 372–387 (2016)
Qi, Z., Cui, Y., Liu, Y., Pang, J.S.: Asymptotic analysis of stationary solutions of coupled nonconvex nonsmooth empirical risk minimization. arXiv:1910.02488 (October 2019)
Rockafellar, R.T.: Coherent approaches to risk in optimization under uncertainty. In: Tutorials in Operations Research, pp. 38–61. INFORMS (2007)
Scholtes, S.: Introduction to Piecewise Differentiable Equations. Springer Briefs in Optimization (2002)
Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154–1157 (1973)
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., Fergus, R.: Intriguing properties of neural networks. In: International Conference on Learning Representations (2014)
Tütüncü, R., Koenig, M.: Robust asset allocation. Ann. Oper. Res. 132, 157–187 (2004)
Xie, Y., Shanbhag, U.: On robust solutions to uncertain linear complementarity problems and their variants. SIAM J. Optim. 26(4), 2120–2159 (2016)
Xu, H., Caramanis, C., Mannor, S.: Robust regression and lasso. Trans. Inf. Theory 56(7), 3561–3574 (2010)