|
|
基于Mangasarian函数的松弛方法的收敛性研究
|
Abstract:
本文讨论互补约束优化问题(MPCC)。MPCC在金融经济，交通规划，网络设计等领域有着重要的应用。由于MPCC的特殊结构，MPCC在可行点处不满足大多数的约束规范。因此，MPCC问题在理论分析和算法设计上都是较难处理的。本文基于Mangasarian互补函数构造出的松弛问题，证明在MPCC-rCPLD约束规范条件下，松弛问题的稳定点列收敛于MPCC的M-稳定点。并且证明如果增强假设条件，松弛问题的稳定点列收敛于MPCC的强稳定点。
This paper discusses mathematical programs with complementarity constraints (MPCC for short). MPCC plays an important role in many fields, such as finance and economics, transportation planning, and network design. Due to the unique structure of MPCC, MPCC does not satisfy most of the constraint qualifications at feasible points. Therefore, MPCC is rather difficult to handle both in theoretical analysis and algorithm design. This paper is based on the relaxed problem constructed by Mangasarian complementary functions, and proves that under the MPCC-rCPLD constraint qualifications, the sequence of stationary points of the relaxed problem converges to M-stationary point of MPCC. Moreover, it is proved that the sequence of stationary points of the relaxed problem converges to the strongly stationary points of the MPCC if some additional conditions hold.
| [1] | Scheel, H. and Scholtes, S. (2000) Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity. Mathematics of Operations Research, 25, 1-22. https://doi.org/10.1287/moor.25.1.1.15213 |
| [2] | Scholtes, S. (2001) Convergence Properties of a Regularization Scheme for Mathematical Programs with Complementarity Constraints. SIAM Journal on Optimization, 11, 918-936. https://doi.org/10.1137/s1052623499361233 |
| [3] | 刘水霞, 陈国庆. 互补约束优化问题的乘子序列部分罚函数算法[J]. 运筹学学报, 2011, 15(4): 55-64. |
| [4] | Bard, J.F. (1988) Convex Two-Level Optimization. Mathematical Programming, 40, 15-27. https://doi.org/10.1007/bf01580720 |
| [5] | Luo, Z., Pang, J. and Ralph, D. (1996) Mathematical Programs with Equilibrium Constraints. Cambridge University Press. https://doi.org/10.1017/cbo9780511983658 |
| [6] | Lin, G. and Fukushima, M. (2005) A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints. Annals of Operations Research, 133, 63-84. https://doi.org/10.1007/s10479-004-5024-z |
| [7] | Kadrani, A., Dussault, J. and Benchakroun, A. (2009) A New Regularization Scheme for Mathematical Programs with Complementarity Constraints. SIAM Journal on Optimization, 20, 78-103. https://doi.org/10.1137/070705490 |
| [8] | Steffensen, S. and Ulbrich, M. (2010) A New Relaxation Scheme for Mathematical Programs with Equilibrium Constraints. SIAM Journal on Optimization, 20, 2504-2539. https://doi.org/10.1137/090748883 |
| [9] | Hoheisel, T., Kanzow, C. and Schwartz, A. (2011) 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 |
| [10] | Mangasarian, O.L. (1976) Equivalence of the Complementarity Problem to a System of Nonlinear Equations. SIAM Journal on Applied Mathematics, 31, 89-92. https://doi.org/10.1137/0131009 |
| [11] | 黄小津. 互补约束优化一个新的松弛方法[D]: [硕士学位论文]. 南宁: 广西大学, 2014. |
| [12] | Bazaraa, M.S., Sherali, H. and Shetty, C.M. (1993) Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, Inc. |
| [13] | Xu, N., Zhu, X., Pang, L. and Lv, J. (2018) Improved Convergence Properties of the Relaxation Schemes of Kadrani et al. and Kanzow and Schwartz for MPEC. Asia-Pacific Journal of Operational Research, 35, Article ID: 1850008. https://doi.org/10.1142/s0217595918500082 |
| [14] | Qi, L. and Wei, Z. (2000) On the Constant Positive Linear Dependence Condition and Its Application to SQP Methods. SIAM Journal on Optimization, 10, 963-981. https://doi.org/10.1137/s1052623497326629 |
