|
|
基于值函数内点罚方法的双层规划问题研究
|
Abstract:
本文考虑了一个在实际中有很多应用的双层规划问题，其下层问题带有多个不等式约束。为了开发有效的数值算法，通常需要将双层规划转化为单层优化问题。本文首先提出了罚函数，然后利用罚函数将下层问题的约束函数罚到目标函数得到逼近下层问题的无约束优化问题，并证明该无约束优化问题的最优值函数逼近于原下层问题的最优值函数，从而利用该逼近最优值函数将双层规划问题近似为一系列单层优化问题，并证明该一系列单层优化问题的解收敛于原双层规划的最优解。
In this paper, we consider a bi-level programming with many applications in practice, where the lower-level problem comes with multiple inequality constraints. In order to develop efficient nu-merical algorithms, it is often necessary to transform the bi-level programming into a single-level optimization problem. In this paper, we first propose a penalty function, and then use the penalty function to penalize the constraint function of the lower-level problem to the objective function to obtain an unconstrained optimization problem that approximates the lower-level problem. And we prove that the optimal value function of this unconstrained optimization problem approximates the optimal value function of the original lower-level problem. The bi-level programming problem is approximated to a series of single-level optimization problems by using the approximate optimal value function, and the solutions of the series of single-level optimization problems are proved to converge to the optimal solutions of the original bi-level programming.
| [1] | Stackelberg, H.V. (1952) The Theory of the Market Economy. Oxford University Press, Oxford. |
| [2] | Bracken, J. and McGill, J.T. (1973) Mathematical Programs with Optimization Problems in the Constraints. Operations Research, 21, 37-44. https://doi.org/10.1287/opre.21.1.37 |
| [3] | Candler, W. and Norton, R. (1977) Multi-Level Programming. Technical Report 20, World Bank Development Research Center, Washington DC. |
| [4] | Migdalas, A. (1995) Bilevel Programming in Traffic Planning: Models, Methods and Challenge. Journal of Global Optimization, 7, 381-405. https://doi.org/10.1007/BF01099649 |
| [5] | Zhang, J. and Zhu, D. (1996) A Bilevel Programming Method for Pipe Network Optimization. SIAM Journal on Optimization, 6, 838-857. https://doi.org/10.1137/S1052623493260696 |
| [6] | Marcotte, P. (1986) Network Design Problem with Congestion Effects: A Case of Bilevel Programming. Mathematical Programming, 34, 142-162. https://doi.org/10.1007/BF01580580 |
| [7] | Cecchini, M., Ecker, J., Kupferschmid, M. and Leitch, R. (2013) Solving Nonlinear Principal-Agent Problems Using Bilevel Programming. European Journal of Operational Research, 230, 364-373.
https://doi.org/10.1016/j.ejor.2013.04.014 |
| [8] | Pang, J.S. and Trinkle, J.C. (1996) Complementarity Formulations and Existence of Solutions of Dynamic Multi-Rigid-Body Contact Problems with Coulomb Friction. Mathematical Pro-gramming, 73, 199-226.
https://doi.org/10.1007/BF02592103 |
| [9] | Ko？vara, M. and Outrata, J.V. (2006) Effective Reformulations of the Truss Topology Design Problem. Optimization and Engineering, 7, 201-219. https://doi.org/10.1007/s11081-006-6839-z |
| [10] | Du, G. and Wang, J. (2009) Product Family Hierarchical Associ-ated Design and Its Hierarchical Optimization. 2009 IEEE International Conference on Industrial Engineering and Engi-neering Management, Beijing, 21-23 October 2009, 1642-1645. https://doi.org/10.1109/IEEM.2009.5373123 |
| [11] | Miller, T., Friesz, T.L. and Tobin, R.L. (1992) Heuristic Algo-rithms for Delivered Price Spatially Competitive Network Facility Location Problems. Annals of Operations Research, 34, 177-202. https://doi.org/10.1007/BF02098179 |
| [12] | Bj？rndal, M. and J？rnsten, K. (2005) The Deregulated Electric-ity Market Viewed as a Bilevel Programming Problem. Journal of Global Optimization, 33, 465-475. https://doi.org/10.1007/s10898-004-1939-9 |
| [13] | Hobbs, B.F. and Nelson, S.K. (1992) A Nonlinear Bilevel Model for Analysis of Electric Utility Demand-Side Planning Issues. Annals of Operations Research, 34, 255-274. https://doi.org/10.1007/BF02098182 |
| [14] | 纪晓颖, 李云岗, 钟磊钢. 双层规划模型在供应链中的应用[J]. 冶金经济与管理, 2006(1): 44-45. |
| [15] | Bard, J.F. (2013) Practical Bilevel Optimization: Algorithms and Applications. Springer Science & Business Media, Berlin. |
| [16] | Dempe, S. (2002) Foundations of Bilevel Programming. Springer Science & Business Media, Berlin. |
| [17] | Chen, Y. (1995) Bilevel Programming Problems: Analysis, Algorithms and Applications. Université de Montréal, Montréal. |
| [18] | Colson, B., Marcotte, P. and Savard, G. (2005) Bilevel Program-ming: A Survey. A Quarterly Journal of Operations Research (4OR), 3, 87-107. https://doi.org/10.1007/s10288-005-0071-0 |
| [19] | Dempe, S. (2003) Annotated Bibliography on Bilevel Program-ming and Mathematical Programs with Equilibrium Constraints. Optimization, 52, 333-359. https://doi.org/10.1080/0233193031000149894 |
| [20] | 王广民, 万仲平, 王先甲. 二(双)层规划综述[J]. 数学进展, 2007, 36(5): 513-529. |
| [21] | Dempe, S. and Zemkoho, A.B. (2013) The Bilevel Programming Problem: Reformula-tions, Constraint Qualifications and Optimality Conditions. Mathematical Programming, 138, 447-473. https://doi.org/10.1007/s10107-011-0508-5 |
| [22] | Hansen, P., Jaumard, B. and Savard, G. (1992) New Branch-and-Bound Rules for Linear Bilevel Programming. SIAM Journal on Scientific and Statistical Computing, 13, 1194-1217. https://doi.org/10.1137/0913069 |
| [23] | Kunapuli, G., Bennett, K.P., Hu, J. and Pang, J.S. (2008) Classi-fication Model Selection via Bilevel Programming. Optimization Methods & Software, 23, 475-489. https://doi.org/10.1080/10556780802102586 |
| [24] | Lampariello, L. and Sagratella, S. (2020) Numerically Tractable Optimistic Bilevel Problems. Computational Optimization and Applications, 76, 277-303. https://doi.org/10.1007/s10589-020-00178-y |
| [25] | Loridan, P. and Morgan, J. (1996) Weak via Strong Stackelberg Problem: New Results. Journal of Global Optimization, 8, 263-287. https://doi.org/10.1007/BF00121269 |
| [26] | Dempe, S. and Dutta, J. (2012) Is Bilevel Programming a Special Case of a Mathematical Program with Complementarity Constraints? Mathematical Programming, 131, 37-48. https://doi.org/10.1007/s10107-010-0342-1 |
| [27] | Ye, J.J. (2011) Necessary Optimality Conditions for Multiobjec-tive Bilevel Programs. Mathematics of Operations Research, 36, 165-184. https://doi.org/10.1287/moor.1100.0480 |
| [28] | Dempe, S. and Franke, S. (2019) Solution of Bilevel Optimization Problems Using the KKT Approach. Optimization, 68, 1471-1489. https://doi.org/10.1080/02331934.2019.1581192 |
| [29] | Izmailov, A.F., Pogosyan, A.L. and Solodov, M.V. (2012) Semismooth Newton Method for the Lifted Reformulation of Mathematical Programs with Complementarity Constraints. Computational Optimization and Applications, 51, 199-221. https://doi.org/10.1007/s10589-010-9341-7 |
| [30] | Guo, L., Lin, G.H. and Ye, J.J. (2015) Solving Mathematical Programs with Equilibrium Constraints. Journal of Optimization Theory and Applications, 166, 234-256. https://doi.org/10.1007/s10957-014-0699-z |
| [31] | Hoheisel, T., Kanzow, C. and Schwartz, A. (2013) Theoretical and Numerical Comparison of Relaxation Methods for Mathematical Programs with Complementarity Constraints. Mathematical Programming, 137, 257-288.
https://doi.org/10.1007/s10107-011-0488-5 |
| [32] | Pang, J.S. and Fukushima, M. (1999) Complementarity Constraint Qualifications and Simplified B-Stationarity Conditions for Mathematical Programs with Equilibrium Constraints. Com-putational Optimization and Applications, 13, 111-136. https://doi.org/10.1023/A:1008656806889 |
| [33] | Scheel, H. and Scholtes, S. (2000) Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensi-tivity. Mathematics of Operations Research, 25, 1-22. https://doi.org/10.1287/moor.25.1.1.15213 |
| [34] | Outrata, J.V. (1990) On the Numerical Solution of a Class of Stackelberg Problems. Zeitschriftfür Operations Research, 34, 255-277. https://doi.org/10.1007/BF01416737 |
| [35] | Mordukhovich, B.S. (2018) Variational Analysis and Applications. Springer International Publishing, Berlin.
https://doi.org/10.1007/978-3-319-92775-6 |
| [36] | Ye, J.J. and Zhu, D. (1995) Optimality Conditions for Bilevel Programming Problems. Optimization, 33, 9-27.
https://doi.org/10.1080/02331939508844060 |
| [37] | Dempe, S. and Zemkoho, A.B. (2011) The Generalized Manga-sarian-Fromowitz Constraint Qualification and Optimality Conditions for Bilevel Programs. Journal of Optimization Theory and Applications, 148, 46-68.
https://doi.org/10.1007/s10957-010-9744-8 |
| [38] | Lin, G.H., Xu, M. and Ye, J.J. (2014) On Solving Simple Bilevel Programs with a Nonconvex Lower Level Program. Mathematical Programming, 144, 277-305. https://doi.org/10.1007/s10107-013-0633-4 |
| [39] | Xu, M.W. and Ye, J.J. (2014) A Smoothing Augmented Lagran-gian Method for Solving Simple Bilevel Programs. Computational Optimization and Applications, 59, 353-377. https://doi.org/10.1007/s10589-013-9627-7 |
| [40] | Ye, J.J. and Zhu, D. (2010) New Necessary Optimality Condi-tions for Bilevel Programs by Combining the MPEC and Value Function Approaches. SIAM Journal on Optimization, 20, 1885-1905. https://doi.org/10.1137/080725088 |
| [41] | Ouattara, A. and Aswani, A. (2018) Duality Approach to Bilevel Programs with a Convex Lower Level. Proceedings of the Annual American Control Conference IEEE, Milwau-kee, 27-29 June 2018, 1388-1395.
https://doi.org/10.23919/ACC.2018.8431802 |
| [42] | Li, Y.W., lin, G.H., Zhang, J. and Zhu, X.D. (2021) A Novel Approach for Bilevel Programs Based on Wolfe Duality. Optimization Online. |
| [43] | Clarke, F.H. (1990) Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, University City. https://doi.org/10.1137/1.9781611971309 |
| [44] | Guo, L., Lin, G.H., Ye, J.J. and Zhang, J. (2014) Sensitivity Anal-ysis of the Value Function for Parametric Mathematical Programs with Equilibrium Constraints. SIAM Journal on Opti-mization, 24, 1206-1237.
https://doi.org/10.1137/130929783 |
