Abstract
This paper concentrates on solving bilevel programming problems where the lower level programs are max–min optimization problems and the upper level programs have max–max or max–min objective functions. Because these bilevel programming problems include nonconvex and nonsmooth lower level program problems, it is a challenging undone work. Giving some assumptions, we translate these problems into general single level optimization problems or min–max optimization problems. To deal with these equivalent min–max optimization problems, we propose a class of regularization methods which approximate the maximum function by using a family of maximum entropy functions. In addition, we examine the limit situations of the proposed regularization methods and show that any limit points of the global optimal solutions obtained by the approximation methods are the same as the ones of the original problems. Finally, we apply the proposed methods to newsvendor problems and use a numerical example to show their effectiveness.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allende GB, Still G (2013) Solving bilevel programs with the KKT-approach. Math Program 138(1–2):309–332
Bard JF (1998) Practical bilevel optimization: algorithms and applications, vol 30. Springer, Berlin
Colson B, Marcotte P, Savard G (2005) Bilevel programming: a survey. 4OR-Q J Oper Res 3(2):87–107
Dempe S (2002) Foundations of bilevel programming. Springer, Berlin
Dempe S, Zemkoho AB (2013) The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math Program 138(1–2):447–473
Dempe S, Zemkoho AB (2014) KKT reformulation and necessary conditions for optimality in nonsmooth bilevel optimization. SIAM J Optim 24(4):1639–1669
Dempe S, Mordukhovich BS, Zemkoho AB (2012) Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J Optim 22(4):1309–1343
Facchinei F, Jiang H, Qi L (1999) A smoothing method for mathematical programs with equilibrium constraints. Math Program 85(1):107–134
Fletcher R, Leyffer S, Ralph D, Scholtes S (2006) Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J Optim 17(1):259–286
Guo P (2010a) One-shot decision approach and its application to duopoly market. Int J Inf Decis Sci 2(3):213–232
Guo P (2010b) Private real estate investment analysis within one-shot decision framework. Int Real Estate Rev 13(3):238–260
Guo P (2011) One-shot decision theory. IEEE Trans On Syst Man Cybern A Syst Hum 41(5):917–926
Guo P, Li Y (2014) Approaches to multistage one-shot decision making. Eur J Oper Res 236(2):612–623
Guo P, Ma X (2014) Newsvendor models for innovative products with one-shot decision theory. Eur J Oper Res 239(2):523–536
Guo L, Lin GH, Ye JJ (2015) Solving mathematical programs with equilibrium constraints. J Optim Theory Appl 166(1):234–256
Li XS, Fang SC (1997) On the entropic regularization method for solving min–max problems with applications. Math Methods Oper Res 46(1):119–130
Li Y, Guo P (2015) Possibilistic individual multi-period consumption-investment models. Fuzzy Sets Syst 274:47–61
Lin GH, Fukushima M (2005) A modified relaxation scheme for mathematical programs with complementarity constraints. Ann Oper Res 133(1–4):63–84
Lin GH, Xu M, Ye JJ (2014) On solving simple bilevel programs with a nonconvex lower level program. Math Program 144(1–2):277–305
Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints. Cambridge University Press, Cambridge
Outrata JV (1990) On the numerical solution of a class of Stackelberg problems. Z Oper Res 34(4):255–277
Rockafellar RT, Wets RJB (1998) Variational analysis. Springer, Berlin
Scholtes S (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J Optim 11(4):918–936
Stephen B, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge
Vicente LN, Calamai PH (1994) Bilevel and multilevel programming: a bibliography review. J Global Optim 5(3):291–306
Von Stackelberg H (1952) The theory of the market economy. Oxford University Press, Oxford
Wang C, Guo P (2017) Behavioral models for first-price sealed-bid auctions with the one-shot decision theory. Eur J Oper Res 261(3):994–1000
Xu M, Ye JJ (2014) A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput Optim Appl 59(1–2):353–377
Ye JJ (2005) Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J Math Anal Appl 307(1):350–369
Ye JJ, Zhu DL (1995) Optimality conditions for bilevel programming problems. Optimization 33(1):9–27
Ye JJ, Zhu DL (2010) New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J Optim 20(4):1885–1905
Zhu X, Lin GH (2016) Improved convergence results for a modified Levenberg–Marquardt method for nonlinear equations and applications in MPCC. Optim Methods Softw 31(4):791–804
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by JSPS KAKENHI under Grant Number 15K03599.
Rights and permissions
About this article
Cite this article
Zhu, X., Guo, P. Approaches to four types of bilevel programming problems with nonconvex nonsmooth lower level programs and their applications to newsvendor problems. Math Meth Oper Res 86, 255–275 (2017). https://doi.org/10.1007/s00186-017-0592-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-017-0592-2