On bilevel programming. I: General nonlinear cases. (English) Zbl 0841.90112
Summary: This paper is concerned with general nonlinear nonconvex (BLPP) bilevel programming problems. We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.
MSC:
| 90C30 | Nonlinear programming |
| 49J52 | Nonsmooth analysis |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
bilevel programming; nondifferentiable optimization; economic planning; sensitivity analysis; nonlinear nonconvex bilevel programmingReferences:
| [1] | G. Anandalingam and T.L. Friesz, ”Hierarchical optimization: an introduction,”Annals of Operations Research 34 (1992) 1–11. · Zbl 0751.90067 · doi:10.1007/BF02098169 |
| [2] | J.F. Bard, ”Optimality conditions for the bi-level programming problem,”Naval Research Logistics Quarterly 13 (1984) 13–26. · Zbl 0537.90087 · doi:10.1002/nav.3800310104 |
| [3] | J.F. Bard, ”An algorithm for solving the general bilevel programming program,”Mathematics of Operations Research 8 (1983) 260–272. · Zbl 0516.90061 · doi:10.1287/moor.8.2.260 |
| [4] | J.F. Bard and J.E. Falk, ”An explicit solution to the multi-level programming problem,”Computers & Operations Research 9 (1982) 77–100. · doi:10.1016/0305-0548(82)90007-7 |
| [5] | W.F. Bialas and M.H. Karwan, ”On two-level optimization,”IEEE Transactions on Automatic Control AC-27 (1982) 211–214. · Zbl 0487.90005 |
| [6] | F.H. Clarke,Nonsmooth Analysis and Optimization (Wiley-Interscience, New York, 1983). · Zbl 0582.49001 |
| [7] | J.E. Dennis Jr and R.B. Schnabel, ”A view of unconstrained optimization,” in: G.L. Nemhauser, ed.,Handbooks in Operations Research and Management Sciences, Vol. 1 (North-Holland, Amsterdam, 1989) pp. 1–72. |
| [8] | A.H. De Silva, ”Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production,” Dissertation, George Washington University, Washington, DC (1978). |
| [9] | A.H. De Silva and G.P. McCormick, ”Implicitly defined optimization problems,”Annals of Operations Research 34 (1992) 107–124. · Zbl 0756.90080 · doi:10.1007/BF02098175 |
| [10] | T.A. Edmunds and J.F. Bard, ”Algorithm for nonlinear bilevel mathematical programs,”IEEE Transactions on Systems, Man, and Cybernetics 21 (1991) 83–89. · doi:10.1109/21.101139 |
| [11] | U. Felgenhauer, ”On the stable global convergence of particular quasi-Newton-methods,”Optimization 26 (1992) 97–113. · Zbl 0817.90107 · doi:10.1080/02331939208843845 |
| [12] | A.V. Fiacco,Introduction to Sensitivity and Stability Analysis in Nonlinear Programming (Academic Press, New York, 1983). · Zbl 0543.90075 |
| [13] | A.V. Fiacco and J. Liu, ”Degeneracy in NLP and the development of results motivated by its presence,”Annals of Operations Research 46 (1993) 61–80. · Zbl 0786.90065 · doi:10.1007/BF02096257 |
| [14] | A.V. Fiacco and J. Liu, ”Post-optimality analysis by sequential methods, Part I: asymptotic behavior of regularity conditions,” preprint. |
| [15] | A.V. Fiacco and J. Liu, ”Post-optimality analysis by sequential methods, Part II: algorithmic approximation of sensitivity information,” preprint. |
| [16] | R. Fletcher,Practical Methods of Optimization (Wiley, New York, 1987). · Zbl 0905.65002 |
| [17] | J. Fortuny-Amat and B. McCarl, ”A representation of a two-level programming problem,”Journal of the Operational Research Society 32 (1981) 783–792. · Zbl 0459.90067 |
| [18] | W.W. Hager, ”Lipschitz continuity for constrained process,”SIAM Journal on Control and Optimization (1979) 321–338. · Zbl 0426.90083 |
| [19] | Y. Ishizuka and E. Aiyoshi, ”Double penalty method for bilevel optimization problems,”Annals of Operations Research 34 (1992) 73–88. · Zbl 0756.90083 · doi:10.1007/BF02098173 |
| [20] | R.H.F. Jackson and G.P. McCormick, ”Second-order sensitivity analysis in factorable programming: Theory and applications,”Mathematical Programming 41 (1988) 1–27. · Zbl 0647.90090 · doi:10.1007/BF01580751 |
| [21] | K. Jittorntrum, ”Solution point differentiability without strict complementarity in nonlinear programming,”Mathematical Programming Study 21 (1984) 127–138. · Zbl 0571.90080 · doi:10.1007/BFb0121215 |
| [22] | K.C. Kiwiel,Methods of Descent For Nondifferentiable Optimization (Springer, Berlin, 1985). · Zbl 0561.90059 |
| [23] | M. Kojima, ”Strongly stable stationary solutions in nonlinear programs,” in: S.M. Robinson, ed.,Analysis and Computation of Fixed Points (Academic Press, New York, 1980) pp. 93–138. |
| [24] | C.D. Kolstad and L.S. Lasdon, ”Derivative evaluation and computational experience with large bilevel mathematical programs,”Journal of Optimization Theory and Applications 65 (1990) 485–499. · Zbl 0676.90101 · doi:10.1007/BF00939562 |
| [25] | C. Lemaréchal, ”Nondifferentiable optimization,” in: G.L. Nemhauser, A.H.G. Rinnooy Kan, and M.J. Todd, eds.,Handbooks in Operations Research and Management Science, Vol. 1, Optimization (North-Holland, Amsterdam, 1989) pp. 529–572. |
| [26] | J. Liu, ”Sensitivity analysis in nonlinear programs and variational inequalities via continuous selections,”Journal on Control and Optimization 33 (1995) 1040–1060. · Zbl 0839.49017 · doi:10.1137/S0363012993248876 |
| [27] | P. Loridan and J. Morgan, ”Quasiconvex lower level problems and applications in two-level optimization,” Technical Report CRM-1578, University of Montreal (1988). · Zbl 0662.90090 |
| [28] | R. Mifflin, ”Semismooth and semiconvex functions in constrained optimization,”SIAM Journal Control and Optimization 15 (1977) 957–972. · Zbl 0376.90081 |
| [29] | J.S. Pang, ”Solution differentiability and continuation of Newton’s method for variational inequality problems over polyhedral sets,”Journal of Optimization Theory and Applications 66 (1990) 121–135. · Zbl 0681.49011 · doi:10.1007/BF00940536 |
| [30] | J.S. Pang and D. Ralph, ”Piecewise smoothness, local invertibility, and parametric analysis of normal maps,” Preprint Series No. 26, Department of Mathematics, University of Melbourne, Australia (1993). · Zbl 0857.90122 |
| [31] | L. Qi, ”Convergence analysis of some algorithms for solving nonsmooth equations,”Mathematics of Operations Research 18 (1993) 227–253. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227 |
| [32] | S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094 · doi:10.1287/moor.5.1.43 |
| [33] | S.M. Robinson, ”Local structure of feasible sets in nonlinear programming, Part III: Stability and Sensitivity,”Mathematical Programming Study 30 (1987) 45–66. · Zbl 0629.90079 · doi:10.1007/BFb0121154 |
| [34] | S.M. Robinson, ”Normal maps induced by linear transformations,”Mathematics of Operations Research 17 (1992) 691–714. · Zbl 0777.90063 · doi:10.1287/moor.17.3.691 |
| [35] | H. Schramm and J. Zowe, ”A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,”SIAM Journal on Optimization 2 (1992) 121–152. · Zbl 0761.90090 · doi:10.1137/0802008 |
| [36] | K. Shimizu and E. Aiyoshi, ”A new computational method for Stackelberg and min–max problems by use of a penalty method,”IEEE Transactions on Automatic Control AC-26 (1981) 460–466. · Zbl 0472.93004 |
| [37] | J.E. Spingarn, ”Second-order conditions that are necessary with probability one,” in: A.V. Fiacco, ed.Mathematical Programming with Data Perturbations, Vol. 1 (Marcel Dekker, New York, 1983) pp. 3–15. |
| [38] | Ph. Wolfe, ”A method of conjugate subgradients for minimizing nondifferentiable functions,”Mathematical Programming Study 3 (1975) 145–173. · doi:10.1007/BFb0120703 |
| [39] | K. Zheng and A. Estache, ”Pollution control in a decentralized economy,” Working Paper WPS-1066, The World Bank (1993). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
