Abstract
In this paper, we give some existence theorems of solutions to \(\Gamma \)-robust counterparts of gap function formulations of uncertain linear complementarity problems, in which \(\Gamma \) plays a role in adjusting the robustness of the model against the level of conservatism of solutions. If the \(\Gamma \)-robust uncertainty set is nonconvex, it is hard to prove the existence of solutions to the corresponding robust counterpart. Using techniques of asymptotic functions, we establish existence theorems of solutions to the corresponding robust counterpart. For the case of nonconvex \(\Gamma \)-robust ellipsoidal uncertainty sets, these existence results are not proved in the paper [Krebs et al., Int. Trans. Oper. Res. 29 (2022), pp. 417–441]; for the case of convex \(\Gamma \)-robust ellipsoidal uncertainty sets, our existence theorems are obtained under the conditions which are much weaker than those in Krebs’ paper. Finally, a case study for the uncertain traffic equilibrium problem is considered to illustrate the effects of nonconvex uncertainty sets on the level of conservatism of robust solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
Enquiries about data availability should be directed to the authors.
References
Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer-Verlag, New York (2002)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. 99, 351–376 (2004)
Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Bertsekas, D.: Convex Optimization Theory. Athena Scientific, Belmont (2009)
Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98, 49–71 (2003)
Bertsimas, D., Sim, M.: The price of robustness. Op. Res. 52, 35–53 (2004)
Biefel, C., Liers, F., Rolfes, J., Schmidt, M.: Affinely adjustable robust linear complementarity problems. SIAM J. Optim. 32, 152–172 (2022)
Çelebi, E., Krebs, V., Schmidt, M.: \(\Gamma \)-robust electricity market equilibrium models with transmission and generation investments. http://www.optimizationonline.org/DB$_$HTML/2020/01/7586.html.Tech.Rep (2020)
Chen, X., Fukushima, M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022–1038 (2005)
Chen, X., Wets, R.J.B., Zhang, Y.: Stochastic variational inequalities: residual minimization smoothing sample average approximations. SIAM J. Optim. 22, 649–673 (2012)
Chen, X., Zhang, C., Fukushima, M.: Robust solution of monotone stochastic linear complementarity problems. Mathe. Program. 117, 51–80 (2009)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
Fischetti, M., Monaci, M.: Light Robustness, pp. 61–84. Springer, Berlin (2009)
Krebs, V., Müller, M., Schmidt, M.: \(\Gamma \)-robust linear complementarity problems with ellipsoidal uncertainty sets. Int. Trans. Oper. Res. 29, 417–441 (2022)
Krebs, V., Schmidt, M.: \(\Gamma \)-robust linear complementarity problems. Optim. Methods Softw. 37, 658–691 (2022)
Lin, G.H., Fukushima, M.: New reformulations for stochastic nonlinear complementarity problems. Optim. Methods Softw. 21, 551–564 (2006)
Schöbel, A.: Generalized light robustness and the trade-off between robustness and nominal quality. Math. Methods Oper. Res. 80, 161–191 (2014)
Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21, 1154–1157 (1973)
Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. 1, 325–362 (1952)
Wardrop, J.G., Whitehead, J.I.: Correspondence. Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. 1, 767–768 (1952)
Wu, D., Han, J.Y., Zhu, J.H.: Robust solutions to uncertain linear complementarity problems. Acta Math. Appl. Sin. Engl. Ser. 27, 339–352 (2011)
Xie, Y., Shanbhag, U.V.: On robust solutions to uncertain monotone linear complementarity problems (LCPs) and their variants. In: Proceedings of the 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), IEEE, Washington, DC, 2834–2839 (2014)
Xie, Y., Shanbhag, U.V.: On robust solutions to uncertain linear complementarity problems and their variants. SIAM J. Optim. 26, 2120–2159 (2016)
Yanıkoğlu, İ, Gorissen, B., den Hertog, D.: A survey of adjustable robust optimization. European J. Oper. Res. 277, 799–813 (2019)
Acknowledgements
This work was supported by the National Natural Science Foundation of China NSFC-11971118 and NSFC-12071157. The authors are grateful to the associate editor and the two anonymous referees for their valuable comments and suggestions. Their comments and suggestions have improved the presentation of the paper significantly.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Tan, L., Yang, W.H. & Pan, J. Existence of solutions to \(\Gamma \)-robust counterparts of gap function formulations of uncertain LCPs with ellipsoidal uncertainty sets. J Glob Optim 89, 73–92 (2024). https://doi.org/10.1007/s10898-023-01340-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-023-01340-6
Keywords
- Robust optimization
- Linear complementarity problems
- Ellipsoidal uncertainty sets
- Traffic equilibrium problems