Solving Bilevel Programs Based on Lower-Level Mond-Weir Duality
Authors: 
Yu-Wei Li, Gui-Hua Lin, Xide ZhuAuthors Info & Claims
Pages 1225 - 1241
Abstract
This paper focuses on developing effective algorithms for solving a bilevel program. The most popular approach is to replace the lower-level problem with its Karush-Kuhn-Tucker conditions to generate a mathematical program with complementarity constraints (MPCC). However, MPCC does not satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ) at any feasible point. In this paper, inspired by a recent work using the lower-level Wolfe duality (WDP), we apply the lower-level Mond-Weir duality to present a new reformulation, called MDP, for bilevel program. It is shown that, under mild assumptions, they are equivalent in globally or locally optimal sense. An example is given to show that, different from MPCC, MDP may satisfy the MFCQ at its feasible points. Relations among MDP, WDP, and MPCC are investigated. On this basis, we extend the MDP reformulation to present another new reformulation (called eMDP), which has similar properties to MDP. Furthermore, to compare two new reformulations with the MPCC and WDP approaches, we design a procedure to generate 150 tested problems randomly and comprehensive numerical experiments show that MDP has quite evident advantages over MPCC and WDP in terms of feasibility to the original bilevel programs, success efficiency, and average CPU time, whereas eMDP is far superior to all other three reformulations.
History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.
Funding: This work was supported by the National Natural Science Foundation of China [Grants 12071280 and 11901380].
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (Supplementary Material) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0108). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.
References
[1]
Bard JF (1998) Practical Bilevel Optimization: Algorithms and Applications (Kluwer, Dordrecht, Germany).
[2]
Bracken J, McGill JT (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1):37–44.
[3]
Byeon G, Van Hentenryck P (2022) Benders subproblem decomposition for bilevel problems with convex follower. INFORMS J. Comput. 34(3):1749–1767.
[4]
Caprara A, Carvalho M, Lodi A, Woeginger GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.
[5]
Clarke FH (1990) Optimization and Nonsmooth Analysis (SIAM, Philadelphia).
[6]
Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153:235–256.
[7]
Dempe S, Zemkoho AB (2013) The bilevel programming problem: Reformulations, constraint qualifications and optimality conditions. Math. Programming 138:447–473.
[8]
Egudo R, Mond B (1986) Duality with generalized convexity. J. Australian Math. Soc. 28(1):10–21.
[9]
Fukushima M, Luo ZQ, Pang JS (1998) A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Comput. Optim. Appl. 10:5–34.
[10]
Guo L, Lin GH, Ye JJ (2015) Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166:234–256.
[11]
Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Statist. Comput. 13(5):1194–1217.
[12]
Hoheisel T, Kanzow C, Schwartz A (2013) Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Programming 137:257–288.
[13]
Izmailov AF, Pogosyan A, Solodov MV (2012) Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Comput. Optim. Appl. 51(1):199–221.
[14]
Kleinert T, Schmidt M (2021) Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. 33(1):198–215.
[15]
Kunapuli G, Bennett KP, Hu J, Pang JS (2008) Classification model selection via bilevel programming. Optim. Methods Software 23(4):475–489.
[16]
Lachhwani K, Dwivedi A (2018) Bi-level and multi-level programming problems: Taxonomy of literature review and research issues. Arch. Comput. Methods Engrg. 25:847–877.
[17]
Li YW, Lin GH, Zhu X (2023) Github repository: Solving bilevel programs based on lower-level Mond-Weir duality. https://doi.org/10.1287/ijoc.2023.0108.cd, https://github.com/INFORMSJoC/2023.0108.
[18]
Li YW, Lin GH, Zhang J, Zhu X (2022) A novel approach for bilevel programs based on Wolfe duality. Preprint, submitted February 14, https://arxiv.org/abs/2302.06838.
[19]
Lin GH, Fukushima M (2006) Hybrid approach with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128(1):1–28.
[20]
Lin GH, Chen X, Fukushima M (2009) Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization. Math. Programming 116:343–368.
[21]
Lin GH, Xu M, Ye JJ (2014) On solving simple bilevel programs with a nonconvex lower level program. Math. Programming 144:277–305.
[22]
Liu R, Liu X, Zeng S, Zhang J, Zhang Y (2023a) Hierarchical optimization-derived learning. IEEE Trans. Pattern Anal. Machine Intelligence 45(12):14693–14708.
[23]
Liu R, Liu X, Zeng S, Zhang J, Zhang Y (2023b) Value-function-based sequential minimization for bi-level optimization. IEEE Trans. Pattern Anal. Machine Intelligence 45(12):15930–15948.
[24]
Lu Z, Mei S (2023) First-order penalty methods for bilevel optimization. Preprint, submitted January 4, https://arxiv.org/abs/2301.01716.
[25]
Luo ZQ, Pang JS, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK).
[26]
Ma X, Yao W, Ye JJ, Zhang J (2021) Combined approach with second-order optimality conditions for bilevel programming problems. Preprint, submitted July 31, https://arxiv.org/abs/2108.00179.
[27]
Mond B, Weir T (1981) Generalized concavity and duality. Generalized Concavity in Optimization and Economics (Academic Press, San Diego).
[28]
Scholtes S (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11(4):918–936.
[29]
Stackelberg HV (1952) Theory of the Market Economy (Oxford University Press, Oxford, UK).
[30]
Xu M, Ye JJ (2014) A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput. Optim. Appl. 59:353–377.
[31]
Ye JJ, Zhu D (1995) Optimality conditions for bilevel programming problems. Optimization 33(1):9–27.
[32]
Ye JJ, Zhu D (2010) New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J. Optim. 20(4):1885–1905.
[33]
Ye JJ, Yuan X, Zeng S, Zhang J (2023) Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Math. Programming 198(2):1583–1616.
[34]
Zeng B (2020) A practical scheme to compute the pessimistic bilevel optimization problem. INFORMS J. Comput. 32(4):1128–1142.
Index Terms
- Solving Bilevel Programs Based on Lower-Level Mond-Weir Duality
Index terms have been assigned to the content through auto-classification.
Recommendations
On solving simple bilevel programs with a nonconvex lower level program
In this paper, we consider a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint and the upper level program has a convex set constraint. By using the value function of the lower level ...
Higher-order Mond-Weir duality for set-valued optimization
In this paper, we introduce a higher-order Mond-Weir dual for a set-valued optimization problem by virtue of higher-order contingent derivatives and discuss their weak duality, strong duality and converse duality properties.
Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs
AbstractRelaxed constant positive linear dependence constraint qualification (RCPLD) for a system of smooth equalities and inequalities is a constraint qualification that is weaker than the usual constraint qualifications such as Mangasarian Fromovitz ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024, INFORMS.
Publisher
INFORMS
Linthicum, MD, United States
Publication History
Published: 01 September 2024
Accepted: 18 December 2023
Received: 31 March 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025