Optimality conditions for bilevel optimization with variational inequality constraints using approximations

Dardour, Zakarya; Idrissi, Rachid El; Kalmoun, El Mostafa; Lafhim, Lahoussine

doi:10.2478/candc-2025-0005

Abstract

We use first- and second-order approximations to establish necessary and suffcient optimality conditions for nonsmooth generalized bilevel optimization problems with variational inequality constraints. To transform the hierarchical problem into a single-level optimization problem, we employ two approaches: the gap function reformulation and the KKT reformulation. We compare these approaches and provide examples to illustrate the applicability of the results.

References

Allali, K. and Amahroq, T. (1997) Second order approximations and dual necessary optimality conditions. Optimization 40, 3, 229–246.
Search in Google Scholar Back to article
Amahroq, T. and Gadhi, N. (2001) On the regularity condition for vector programming problems. J. Global Optim. 21, 433–441.
Search in Google Scholar Back to article
Amahroq, T. and Gadhi, N. (2003) Second order optimality conditions for the extremal problem under inclusion constraints. J. Math. Anal. Appl. 285, 1, 74–85.
Search in Google Scholar Back to article
Auslender, A. (1976) Optimisation: Méthodes Numériques. Masson, Paris.
Search in Google Scholar Back to article
Ben-Ayed, O., Boyce, D. E. and Blair, C. E. (1988) A general bilevel linear programming formulation of the network design problem. Transp. Res. 21, 37–44.
Search in Google Scholar Back to article
Bonnans, J. F. and Shapiro, A. (2000) Perturbation Analysis of Optimization Problems. Springer Series in Operations Research 117, Springer, New York.
Search in Google Scholar Back to article
Bracken, J. and McGill, J. T. (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21, 37–44.
Search in Google Scholar Back to article
Chen, Y. and Florian, M. (1995) The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions. Optimization 32, 3, 193–209.
Search in Google Scholar Back to article
Clarke, F. H. (1990) Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics.
Search in Google Scholar Back to article
Danskin, J. (1967) The theory of max-min, with applications. SIAM J. Appl. Math. 14, 641-664.
Search in Google Scholar Back to article
Dardour, Z., Lafhim, L. and Kalmoun, E. M. (2024) Primal and dual second-order necessary optimality conditions in bilevel programming. J. Appl. Numer. Optim. 6, 153-175.
Search in Google Scholar Back to article
Dardour, Z., El Idrissi, R., Kalmoun, E. M. and Lafhim, L. (2025) Second-order necessary conditions for bilevel programs via KKT reformulation. Carpa-thian J. Math. 41, 3, 597–618.
Search in Google Scholar Back to article
Dempe, S. and Dutta, J. (2012) Is bilevel programming a special case of a mathematical program with complementarity constraints?. Mathematical Programming. 131 37-48.
Search in Google Scholar Back to article
Dempe, S. and Gadhi, N. (2010) Second order optimality conditions for bilevel set optimization problems. J. Global Optim. 47, 233-245.
Search in Google Scholar Back to article
Dempe, S. and Zemkoho, A. B. (2013) The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math. Program. 138, 1-2, 447-473.
Search in Google Scholar Back to article
El Idrissi, R., Lafhim, L. and Ouakrim, Y. (2024) Pontryagin optimality conditions for generalized bilevel optimal control problems with pure state inequality constraints. J. Appl. Numer. Optim. 6, 229–248.
Search in Google Scholar Back to article
El Idrissi, R., Lafhim, L., Kalmoun, E. M. and Ouakrim, Y. (2024) Optimality conditions for bilevel optimal control problems with non-convex quasi-variational inequalities. RAIRO Oper. Res. 58, 2, 1789–1805.
Search in Google Scholar Back to article
Falk, J. E. and Liu, J. M. (1995) On bilevel programming, Part I: General nonlinear cases. Math. Program. 70, 47-72.
Search in Google Scholar Back to article
Fiacco, A.V. and McCormick, G.P. (1990) Nonlinear Programming: Sequential Unconstrained Minimization Techniques. SIAM Classics in Applied Mathematics 4, Philadelphia.
Search in Google Scholar Back to article
Fukushima, M. (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99–110.
Search in Google Scholar Back to article
Gauvin, J. and Dubeau, F. (1982) Differential properties of the marginal function in mathematical programming. Math. Program. Stud. 19, 101–119.
Search in Google Scholar Back to article
Hansen, P., Jaumard, B. and Savard, G. (1992) New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13, 1194–1217.
Search in Google Scholar Back to article
Hearn, D. W. (1982) The gap function of a convex program. Oper. Res. Lett. 1, 2, 67–71.
Search in Google Scholar Back to article
Hiriart-Urruty, J. B., Strodiot, J. J. and Nguyen, V. (1984) Generalized Hessian matrix and second order optimality conditions for problems with C1,1 data. Appl. Math. Optim. 11, 43–56.
Search in Google Scholar Back to article
Huang, Z., Lin, G. and Xiu, N. (2014) Several developments of variational inequalities and complementarity problems, bilevel programming and MPEC. Oper. Res. 18, 1.
Search in Google Scholar Back to article
Ioffe, A. D. (1989) Approximate subdifferential and applications. III: The metric theory. Mathematika 36, 1–38.
Search in Google Scholar Back to article
Jeyakumar, V. and Luc, D. T. (1998) Approximate Jacobian matrices for nonsmooth continuous maps and C1-optimization. SIAM J. Control Optim. 36, 1815–1832.
Search in Google Scholar Back to article
Jourani, A. and Thibault, L. (1993) Approximations and metric regularity in mathematical programming in Banach spaces. Math. Oper. Res. 18, 1, 199–224.
Search in Google Scholar Back to article
Khanh, P. Q. and Tuan, N. D. (2006) First and second order optimality conditions using approximations for nonsmooth vector optimization in Banach spaces. J. Optim. Theory Appl. 130, 2, 289–308.
Search in Google Scholar Back to article
Khanh, P. Q. and Tung, L. T. (2013) First and second-order optimality conditions using approximations for vector equilibrium problems with constraints. J. Global Optim. 55, 901–920.
Search in Google Scholar Back to article
Khanh, P. Q. and Tung, L. T. (2015) First- and second-order optimality conditions for multiobjective fractional programming. TOP 23, 419–440.
Search in Google Scholar Back to article
Khanh, P. Q. and Tung, N. M. (2015) First and second-order optimality conditions without differentiability in multivalued vector optimization. Positivity 19, 817–841.
Search in Google Scholar Back to article
Lafhim, L. (2024) First and Second Order Optimality Conditions using Approximations for Fractional Multiobjective Bilevel Problems under Fractional Constraints. Iran. J. Math. Sci. Inform. 19, 1, 211–232.
Search in Google Scholar Back to article
Loewen, P. D. (1992) Limits of Fréchet normals in nonsmooth analysis. Optimization and Nonlinear Analysis, Pitman Res. Notes Math. Ser. 244, 178–188.
Search in Google Scholar Back to article
Marcotte, P. and Dussault, J.-P. (1987) A note on a globally convergent method for solving monotone variational inequalities. Oper. Res. Lett. 6, 35–42.
Search in Google Scholar Back to article
Marcotte, P. and Dussault, J.-P. (1989) A sequential linear programming algorithm for solving monotone variational inequalities. SIAM J. Control Optim. 27: 1260–1278.
Search in Google Scholar Back to article
Mordukhovich, B. S., Nghia, T. T. A. and Rockafellar, R. T. (2013) Full stability in finite-dimensional optimization. Math. Oper. Res. 38, 4, 768–783.
Search in Google Scholar Back to article
Mordukhovich, B. S. and Shao, Y. (1995) On nonconvex subdifferential calculus in Banach spaces. J. Convex Anal. 2, 211–227.
Search in Google Scholar Back to article
Outrata, J. V. (1994) On optimization problems with variational inequality constraints. SIAM J. Optim. 4, 2, 340–357.
Search in Google Scholar Back to article
Rockafellar, R. T. (1970) Convex Analysis. Princeton University Press, Princeton, NJ.
Search in Google Scholar Back to article
Rockafellar, R. T. and Wets, R. J.-B. (1998) Variational Analysis. Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin.
Search in Google Scholar Back to article
Stackelberg, H. (1952) The Theory of the Market Economy. Oxford University Press, Oxford, UK.
Search in Google Scholar Back to article
Stampacchia, G. (1964) Formes bilinéaires coercitives sur les ensembles convexes. C. R. Math. Acad. Sci. Paris 258, 4413–4416.
Search in Google Scholar Back to article
Sweetser, T. H. (1977) A minimal set-valued strong derivative for set-valued Lipschitz functions. J. Optim. Theory Appl. 23, 539–562.
Search in Google Scholar Back to article
Thibault, L. (1980) Subdifferentials of compactly Lipschitzian vector-valued functions. Ann. Mat. Pura Appl. 4, 125, 157–192.
Search in Google Scholar Back to article
Wan, Z. and Chen, J. W. (2013) On bilevel variational inequalities. J. Oper. Res. Soc. China 1, 4, 483–510.
Search in Google Scholar Back to article
Ye, J. J. (2000) Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM J. Optim. 10, 4, 943–962.
Search in Google Scholar Back to article
Ye, J. J. (1999) Optimality conditions for optimization problems with complementarity constraints. SIAM J. Optim. 9, 374–387.
Search in Google Scholar Back to article
Ye, J. J. and Ye, X. Y. (1997) Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22, 977–997.
Search in Google Scholar Back to article
Ye, J. J., Zhu, D. L. and Zhu, Q. J. (1997) Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7, 481–507.
Search in Google Scholar Back to article
Zemkoho, A. B. and Zhou, S. (2021) Theoretical and numerical comparison of the Karush–Kuhn–Tucker and value function reformulations in bilevel optimization. Comput. Optim. Appl. 78(2), 625-674.
Search in Google Scholar Back to article
Zhang, H. (2014) Clarke directional derivatives of regularized gap functions for nonsmooth quasi-variational inequalities. Math. Control Relat. Fields 4, 3, 365–379.
Search in Google Scholar Back to article

Optimality conditions for bilevel optimization with variational inequality constraints using approximations

Abstract

Paradigm

My account