Abstract

We propose a combined approach with second-order optimality conditions of the lower level problem to study constraint qualifications and optimality conditions for bilevel programming problems. The new method is inspired by the combined approach developed by Ye and Zhu in 2010, where the authors combined the classical first-order and the value function approaches to derive new necessary optimality conditions. In our approach, we add a second-order optimality condition to the combined program as a new constraint. We show that when all known approaches fail, adding the second-order optimality condition as a constraint makes the corresponding partial calmness condition and the resulting necessary optimality condition easier to hold. We also give some discussions on advantages and disadvantages of the combined approaches with the first-order and the second-order information.

Author information

Contact details are reproduced from the original publication and may be historical.

Xiaoxiao Ma

Dept. of Mathematics and Statistics, University of Victoria, Canada

xiaoxiaoma@uvic.ca

Wei Yao

Dept. of Mathematics, Southern University of Science and Technology, and: National Center for Applied Mathematics, Shenzhen, Guangdong, China

yaow@sustech.edu.cn

Jane J. Ye

Dept. of Mathematics and Statistics, University of Victoria, Canada

janeye@uvic.ca

Jin Zhang

Dept. of Mathematics and SUSTech International Center for Mathematics, Southern University of Science and Technology, and: National Center for Applied Mathematics, Shenzhen, Guangdong, China

zhangj9@sustech.edu.cn

Keywords

  • Partial calmness
  • bilevel program
  • optimality condition
  • second-order optimality condition

Mathematics Subject Classification

90C26, 90C30, 90C31, 90C33, 90C46, 49J52, 91A65

References

  1. L. Adam, R. Henrion, J. V. Outrata: On M-stationarity conditions in MPECs and the associated qualification conditions, Math. Programming 168 (2018) 229–259.https://doi.org/10.1007/s10107-017-1146-3Google Scholar
  2. G. Allende, G. Still: Solving bilevel programs with the KKT-approach, Math. Programming 138 (2013) 309–332.https://doi.org/10.1007/s10107-012-0535-xGoogle Scholar
  3. A. V. Arutyunov: Perturbations of extremum problems with constraints and necessary optimality conditions, J. Sov. Math. 54 (1991) 1342–1400.https://doi.org/10.1007/BF01373649Google Scholar
  4. K. Bai, J. J. Ye: Directional necessary optimality conditions for bilevel programs, Math. Oper. Res. 47 (2022) 1169–1191.https://doi.org/10.1287/moor.2021.1164Google Scholar
  5. J. Bard: Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic, Dordrecht (1998).https://doi.org/10.1007/978-1-4757-2836-1Google Scholar
  6. R. Behling, G. Haeser, A. Ramos, D. S. Viana: On a conjecture in second-order optimality conditions, J. Optim. Theory Appl. 176 (2018) 625–633.https://doi.org/10.1007/s10957-018-1229-1Google Scholar
  7. M. Benko, H. Gfrerer, J. V. Outrata: Calculus for directional limiting normal cones and subdifferentials, Set-Valued Var. Analysis 27 (2019) 713–745.https://doi.org/10.1007/s11228-018-0492-5Google Scholar
  8. M. Benko, P. Mehlitz: On implicit variables in optimization theory, J. Nonsmooth Anal. Optim. 2 (2021), art. no. 7215.https://doi.org/10.46298/jnsao-2021-7215Google Scholar
  9. J. F. Bonnans, A. Shapiro: Pertubation Analysis of Optimization Problems, Springer, Berlin (2000).https://doi.org/10.1007/978-1-4612-1394-9Google Scholar
  10. S. Burer, H. Dong: Representing quadratically constrained quadratic programs as generalized copositive programs, Oper. Res. Letters 40 (2012) 203–206.https://doi.org/10.1016/j.orl.2012.02.001Google Scholar
  11. J. V. Burke: Calmness and exact penalization, SIAM J. Control Optimiztion 29 (1991) 493–497.https://doi.org/10.1137/0329027Google Scholar
  12. F. H. Clarke: Optimization and Nonsmooth Analysis, Wiley Interscience, New York (1983).Google Scholar
  13. S. Dempe: Foundations of Bilevel Programming, Kluwer Academic Publishers, Dordrecht (2002).Google Scholar
  14. S. Dempe, J. Dutta: Is bilevel programming a special case of a mathematical program with complementarity constraints?, Math. Programming 131 (2012) 37–48.https://doi.org/10.1007/s10107-010-0342-1Google Scholar
  15. S. Dempe, V. Kalashnikov, G. Prez-Valds, N. Kalashnykova: Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Systems, Springer, Berlin (2015).https://doi.org/10.1007/978-3-662-45827-3Google Scholar
  16. S. Dempe, A. B. Zemkoho: The bilevel programming problems: reformulations, constraint qualifications and optimality conditions, Math. Programming 138 (2013) 447–473.https://doi.org/10.1007/s10107-011-0508-5Google Scholar
  17. S. Dempe, A. B. Zemkoho (eds.): Bilevel Optimization: Advances and Next Challenges, Springer Optimization and Applications Vol. 161, Springer, Cham (2020).https://doi.org/10.1007/978-3-030-52119-6Google Scholar
  18. C. Ding, D. F. Sun, J. J. Ye: First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints, Math. Programming 147 (2014) 539–579.https://doi.org/10.1007/s10107-013-0735-zGoogle Scholar
  19. G. Eichfelder, J. Jahn: Set-semidefinite optimization, J. Convex Analysis 15 (2008) 767–801.https://doi.org/10.68381/jca15051Google Scholar
  20. L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, M. Pontil: Bilevel programming for hyperparameter optimization, ICML (2018) 1563–1572.Google Scholar
  21. E. H. Fukuda, M. Fukushima, A note on the squared slack variables technique for nonlinear optimization, J. Oper. Res. Soc. Japan 60 (2017) 262–270.https://doi.org/10.15807/jorsj.60.262Google Scholar
  22. J. Gauvin: A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming, Math. Programming 12 (1977), 136–138.https://doi.org/10.1007/BF01593777Google Scholar
  23. J. Gauvin, F. Dubeau: Differential properties of the marginal function in mathematical programming, Math. Programming Study 18 (1982) 101–119.https://doi.org/10.1007/BFb0120984Google Scholar
  24. H. Gfrerer: On directional metric subregularity and second-order optimality conditions for a class of nonsmooth mathematical programs, SIAM J. Optimization 23 (2013) 632–665.https://doi.org/10.1137/120891216Google Scholar
  25. H. Gfrerer, J. J. Ye: New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis, SIAM J. Optimization 27 (2017) 842–865.https://doi.org/10.1137/16M1088752Google Scholar
  26. H. Gfrerer, J. J. Ye: New sharp necessary optimality conditions for mathematical programs with equilibrium constraints, Set-Valued Var. Analysis 28 (2020) 395–426.https://doi.org/10.1007/s11228-019-00519-yGoogle Scholar
  27. H. Gfrerer, J. J. Ye, J. C. Zhou: Second-order optimality conditions for non-convex set-constrained optimization problems, Math. Oper. Res. 47 (2022) 2344–2365.https://doi.org/10.1287/moor.2021.1211Google Scholar
  28. L. Guo, G. H. Lin, J. J. Ye, J. Zhang: Sensitivity analysis of the value function for parametric mathematical programs with equilibrium constraints, SIAM J. Optimization 24 (2014) 1206–1237.https://doi.org/10.1137/130929783Google Scholar
  29. R. Henrion, T. M. Surowiec: On calmness conditions in convex bilevel programming, Appl. Analysis 90 (2011) 951–970.https://doi.org/10.1080/00036811.2010.495339Google Scholar
  30. R. Z. Ke, W. Yao, J. J. Ye, J. Zhang: Generic property of the partial calmness condition for bilevel programming problems, SIAM J. Optimization 32 (2022) 604–634.https://doi.org/10.1137/20M1371403Google Scholar
  31. G. Kunapuli, K. Bennett, J. Hu, J. S. Pang: Classification model selection via bilevel programming, Optim. Meth. Software 23 (2008) 475–489.https://doi.org/10.1080/10556780802102586Google Scholar
  32. Y. C. Liang, J. J. Ye: Optimality conditions and exact penalty for mathematical programs with switching constraints, J. Optim. Theory Appl. 190 (2021) 1–31.https://doi.org/10.1007/s10957-021-01879-yGoogle Scholar
  33. R. Liu, P. Mu, X. Yuan, S. Z. Zeng, J. Zhang: A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton, ICML (2020) 6305–6315.Google Scholar
  34. P. Mehlitz: Stationarity conditions and constraint qualifications for mathematical programs with switching constraints, Math. Programming 181 (2020) 149–186.https://doi.org/10.1007/s10107-019-01380-5Google Scholar
  35. P. Mehlitz: On the linear independence constraint qualification in disjunctive programming, Optimization 69 (2020) 2241–2277.https://doi.org/10.1080/02331934.2019.1679811Google Scholar
  36. P. Mehlitz, L. I. Minchenko: R-regularity of set-valued mappings under the relaxed constant positive linear dependence constraint qualification with applications to parametric and bilevel optimization, Set-Valued Analysis 30 (2022) 179–205.https://doi.org/10.1007/s11228-021-00578-0Google Scholar
  37. P. Mehlitz, L. I. Minchenko, A. B. Zemkoho: A note on partial calmness for bilevel optimization problems with linearly structured lower level, Optimization Letters 15 (2021) 1277–1291.https://doi.org/10.1007/s11590-020-01636-6Google Scholar
  38. L. Minchenko, A. Leschov: On strong and weak second-order necessary optimality conditions for nonlinear programming, Optimization 65 (2016) 1693–1702.https://doi.org/10.1080/02331934.2016.1179300Google Scholar
  39. L. Minchenko, S. Stakhovski: Parametric nonlinear programming problems under the relaxed constant rank condition, SIAM J. Optimization 21 (2011) 314–332.https://doi.org/10.1137/090761318Google Scholar
  40. J. Mirrlees: The theory of moral hazard and unobservable behaviour. Part I, Rev. Econ. Studies 66 (1999) 3–22.https://doi.org/10.1111/1467-937X.00075Google Scholar
  41. B. S. Mordukhovich: Variational Analysis and Applications, Springer, Cham (2018).https://doi.org/10.1007/978-3-319-92775-6Google Scholar
  42. B. S. Mordukhovich, N. M. Nam, H. M. Phan: Variational analysis of marginal functions with applications to bilevel programming, J. Optim. Theory Appl. 152 (2012) 557–586.https://doi.org/10.1007/s10957-011-9940-1Google Scholar
  43. J. V. Outrata: On the numerical solution of a class of Stackelberg problems, ZOR Math. Methods Oper. Res. 34 (1990) 255–277.https://doi.org/10.1007/BF01416737Google Scholar
  44. K. Shimizu, Y. Ishizuka, J. Bard: Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic Publishers, Dordrecht (1997).https://doi.org/10.1007/978-1-4615-6305-1Google Scholar
  45. O. Stein: Bi-Level Strategies in Semi-Infinite Programming, Springer, Cham (2013).Google Scholar
  46. M. W. Xu, J. J. Ye: Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs, J. Global Optimization 78 (2020) 181–205.https://doi.org/10.1007/s10898-020-00907-xGoogle Scholar
  47. J. J. Ye: Necessary optimality conditions for multiobjective bilevel programming problems, Math. Oper. Res. 36 (2011) 165–184.https://doi.org/10.1287/moor.1100.0480Google Scholar
  48. J. J. Ye: Constraint qualifications and optimality conditions in bilevel optimization, in: Bilevel Optimization: Advances and Next Challenges, S. Dempe et al. (eds.), Springer Optimization and its Applications Vol. 161, Springer, Cham (2020) 227–251.https://doi.org/10.1007/978-3-030-52119-6_8Google Scholar
  49. J. J. Ye, S. Y. Wu: First order optimality conditions for generalized semi-infinite programming problems, J. Optim. Theory Appl. 137 (2008) 419–434.https://doi.org/10.1007/s10957-008-9352-zGoogle Scholar
  50. J. J. Ye, X. M. Yuan, S. Z. Zeng, J. Zhang: Difference of convex algorithms for bilevel programs with applications in hyperparameter selection, Math. Programming B 198/2 (2023) 1583–1616.https://doi.org/10.1007/s10107-022-01888-3Google Scholar
  51. J. J. Ye, D. L. Zhu: New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches, SIAM J. Optimization 20 (2010) 1885–1905.https://doi.org/10.1137/080725088Google Scholar
  52. J. J. Ye, D. L. Zhu: Optimality conditions for bilevel programming problems, Optimization 33 (1995) 9–27.https://doi.org/10.1080/02331939508844060Google Scholar

Suggested citation

X. Ma, W. Yao, J. J. Ye, J. Zhang. “Combined Approach with Second-Order Optimality Conditions for Bilevel Programming Problems.” Journal of Convex Analysis 30 (2023), No. 4, 1173–1201. https://doi.org/10.68381/jca30053

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press LLC.