运筹学学报 ›› 2014, Vol. 18 ›› Issue (1): 113-133.
黄正海1, 林贵华2, 修乃华3,*
出版日期:2014-03-15
发布日期:2014-03-15
通讯作者:
修乃华
E-mail:nhxiu@bjtu.edu.cn
基金资助:国家自然科学基金~(Nos. 10571112, 11071028, 11101248, 71271021)
HUANG Zhenghai1, LIN Guihua2, XIU Naihua3,*
Online:2014-03-15
Published:2014-03-15
摘要： 考虑有限维变分不等式与互补问题、双层规划以及均衡约束的数学规划问题. 在简单介绍这些问题之后，重点介绍近年来这些领域中发展迅速的几个研究方向，包括对称锥互补问题的理论与算法、变分不等式的投影收缩算法、随机变分不等式与随机互补问题的模型与方法、双层规划以及均衡约束数学规划问题的新方法. 最后提出几个进一步研究的方向.
中图分类号:
黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18(1): 113-133.
HUANG Zhenghai, LIN Guihua, XIU Naihua. Several developments of variational inequalities and complementarity problems, bilevel programming and MPEC[J]. Operations Research Transactions, 2014, 18(1): 113-133.
| Val P Du. The unloading problem for plane curves [J]. American Journal of Mathematics, 1940, 62: 307-311. Cottle R W. Nonlinear programs with positively bounded jacobians [D]. California: University of California, 1964. Hartman P, Stampacchia G. On some nonlinear elliptic differential functional equations [J]. Acta Mathematica, 1966, 115: 153-188. Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem [M]. Boston: Academic Press, 1992. Harker P T, Pang J S. Finite-dimensional variational inequalities and complementarity problems: a survey of theorey, algorithms and applications [J]. Mathematical Programming, 1990, 48: 161-220. Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems [M]. New York: Springer-Verlag, 2003. Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem [M]. Boston: Academic Press, 1992. 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法 [M]. 上海: 上海科技出版社, 2006. Smith T E. A solution condition for complementarity problem: with application to spatial price equilibrium [J]. Applied Mathematics and Computation, 1984, 15: 61-69. Stackelberg H V. The Theory of the Market Economy [M]. Oxford: Oxford University Press, 1952. Bracken J, McGill J. Mathematical programs with optimization problems in the constraints [J]. Operations Research, 1973, 21: 37-44. Luo Z Q, Pang J S, Ralph D. Mathematical Programs with Equilibrium Constraints [M]. Cambridge: Cambridge University Press, 1996. Outrata J, Kocvara M, Zowe J. Nonsmooth Approach to Optimization Problems with Equlilibrium Constraints: Theory, Applications, and Numerical Results [M]. Dordrect: Kluwer Academic Publisher, 1998. Fukushima M, Lin G H. Smoothing methods for mathematical programs with equilibrium constraints [J]. Proceedings of Informatics Research for Development of Knowledge Society Infrastructure, 2004, 206-213. Faraut J, Kor\'anyi A. Analysis on Symmetric Cones [M]. Oxford: Oxford University Press, 1994. Faybusovich L. Euclidean Jordan algebras and interior-point algorithms [J]. Positivity, 1997, 1: 331-357. Faybusovich L. Linear systens in Jordan algebras and primal-dual interior algorithms [J]. Journal of Computational and Applied Mathematics, 1997, 86: 149-175. 修乃华, 韩继业. 对称锥互补问题 [J]. 数学进展，2007, 36(1): 1-12. Yoshise A. Complementarity problems over symmetric cones: a survey of recent developments in several aspects [M]//Anjos M F, Lasserre J B (eds.). Handbook on Semidefinite, Conic and Polynomial Optimization, NewYork: Springer-Verlag, 2012, 166: 339-375. Sun D, Sun J. L\"owner’s operator and spectral functions in Euclidean Jordan algebras [J]. Mathematics of Operations Research, 2008, 33: 421-445. Kong L, Tun\ccel L, Xiu N. Clarke generalized Jacobian of the projection onto symmetric cones [J]. Set-Valued and Variational Analysis, 2009, 17: 135-151. Kong L, Tun\ccel L, Xiu N. Monotonicity of L\"owner operators and its applications to symmetric cone complementarity problems [J]. Mathematical Programming, 2012, 133: 327-336. Tao J, Gowda M S. Some P-properties for nonlinear transformulation on Euclidean Jordan algebras [J]. Mathematics of Operations Research. 2005, 30: 985-1004. Lu N, Huang Z H, Han J. Properties of a class of nonlinear transformations over Euclidean Jordan algebras with applications to complementarity problems [J]. Numerical Functional Analysis and Optimization, 2009, 30: 799-821. Chang Y L, Chen J S, Pan S H. Strong semismoothness of Fischer-Burmeister complementarity function associated with symmetric cones [J]. Journal of Nonlinear and Convex Analysis, 2012, 13: 799-806. Han D. On the coerciveness of some merit functions for complementarity problems over symmetric cones [J]. Journal of Mathematical Analysis and Applications, 2007, 336: 727-737. Kum S H, Lim Y D. Coercivity and strong semismoothness of the penalized Fischer-Burmeister function for the symmetric cone complementarity problem [J]. Journal of Optimization Theory and Applications, 2009, 142: 377-383. Kong L, Xiu N. New smooth C-functions for symmetric cone complementarity problems [J]. Optimization Letters, 2007, 1: 391-400. Liu Y, Zhang L, Wang Y. Some properties of a class of merit functions for symmetric cone complementarity problems [J]. Asia-Pacfic Journal of Operations Research, 2006, 23: 473-496. Miao X H, Chen J S. Error bounds for symmetric cone complementarity problems [J]. Numerical Algebra, Control and Optimization, 2013, 3: 627-641. Pan S, Chen J S. Growth behavior of two classes of merit functions for symmetric cone complementarity problems [J]. Journal of Optimization Theory and Applications, 2009, 141: 167-191. Gowda M S, Sznajder R, Tao J. Some P-properties for linear transformations on Euclidean Jordan algebras [J]. Linear Algebra and its Applications, 2004, 393: 203-232. Gowda M S, Tao J. Some P-properties for nonlinear transformations on Euclidean Jordan algebras [J]. Mathematics of Operations Research, 2005, 30: 985-1004. Gowda M S, Sznajder R. Automorphism invariance of P and GUS properties of linear transformations on Euclidean Jordan algebras [J]. Mathematics of Operations Research, 2006, 31: 109-123. Gowda M S, Sznajder R. Some global uniqueness and solvability results for linear complementarity problems over symmetric cones [J]. SIAM Journal on Optimization, 2007, 18: 461-481. Tao J. Strict semimonotonicity property of linear transformations on Euclidean Jordan algebras [J]. Journal of Optimization Theory and Applications, 2010, 144: 575-596. Rangarajan B K. Polynomial convergence of infeasible-interior-point methods over symmetric cones [J]. SIAM Journal on Optimization, 2006, 16: 1211-1229. Schmieta S H, Alizadeh F. Associative and Jordan algebras, and polynonial time interior-point algorithms for symmetrc cones [J]. Mathematics of Operations Research, 2001, 26: 543-564. Schmieta S H, Alizadeh F. Extension of primal-dual interior-point algorithm to symmetric cones [J]. Mathematical Programming, 2003, 96: 409-438. Yoshise A. Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones [J]. SIAM Journal on Optimization, 2006, 17: 1129-1153. Yoshise A. Homogeneous algorithms for monotone complementarity problems over symmetric cones [J]. Pacific Journal of Optimization, 2009, 5: 313-337. Huang Z H, Ni T. Smoothing algorithms for complementarity problems over symmetric cones [J]. Computational Optimization and Applications, 2010, 45: 557-579. Kong L, Sun J, Xiu N. A regularized smoothing Newton method for symmetric cone complementarity problems [J]. SIAM Journal on Optimization, 2008, 19: 1028-1047. Huang Z H, Hu S L, Han J. Global convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search [J]. Science in China Series A: Mathematics, 2009, 52: 833-848. Pan S, Chen J S. A one-parametric class of merit functions for the symmetric cone complementarity problem [J]. Journal of Mathematical Analysis and Applications, 2009, 355: 195-215. Luo Z, Xiu N. Path-following interior point algorithms for the Cartesian P_*(\kappa) LCP over symmetric cones [J]. Science in China Series A: Mathematics, 2009, 52: 1769-1784. Wang G Q, Bai Y Q. A class of polynomial interior point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones [J]. Journal of Optimization Theory and Applications, 2012, 152: 739-772. Huang Z H, Lu N. Global and global linear convergence of a smoothing algorithm for the Cartesian P_*(\kappa)-SCLCP [J]. Journal of Industrial and Management Optimization, 2012, 8: 67-86. Lu N, Huang Z H. A smoothing Newton algorithm for a class of non-monotonic symmetric cone linear complementarity problems [J]. Journal of Optimization Theory and Applications, Doi: 10.1007/s10957-013-0436-z. Chua C B, Yi P. A continuation method for nonlinear complementarity problems over symmetric cones [J]. SIAM Journal on Optimization, 2010, 20: 2560-2583. Yan T, Fukushima M. Smoothing method for mathematical programs with symmetric cone complementarity constraints [J]. Optimization, 2011, 60: 113-128. Goldstein A A. Convex programming in Hilbert space [J]. Bulletin of the American Mathematical Society, 1976, 70: 709-710. Levitin E S, Polyak B T. Constrained minimization problems [J]. USSR Computational Mathematics and Mathematical Physics, 1966, 6: 1-50. Goldstein A A. Convex programming in Hilbert space [J]. Bulletin of the American Mathematical Society, 1976, 70: 709-710. 何炳生. 凸优化和单调变分不等式的收缩算法 [EB/OL]. [2013-11-13]. http://math.nju.edu.cn/hebma/. Xiu N H, Zhang J Z. Some recent advances in projection-type methods for variational inequalities [J]. Journal of Computational and Applied Mathematics, 2003, 152: 559-585. He B S. A new method for a class of linear variational inequalities [J]. Mathematical Programming, 1994, 66: 137-144. He B S, Liao L Z, Wang X. Proximal-like contraction methods for monotone variational inequalitiesin a unified framework I: effective quadruplet and primary methods [J]. Computational Optimization and Applications, 2012, 51: 649-679. He B S, Liao L Z, Wang X. Proximal-like contraction methods for monotone variational inequalities in a unified framework II: General methods and numerical experiments [J]. Computational Optimization and Applications, 2012, 51: 681-708. Xiu N H, Zhang J Z. Some recent advances in projection-type methods for variational inequalities [J]. Journal of Computational and Applied Mathematics, 2003, 152: 559-585. He B S, Yuan X M. A contraction method with implementable proximal regularization for linearly constrained convex programming [EB/OL]. [2013-10-25]. http://www.optimization-online.org/DB HTML/2010/11/2817.html. He B S, Yuan X M. Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective [J]. SIAM Journal on Imaging Sciences, 2012, 5: 119-149. Ye C H, Yuan X M. A descent method for structured monotone variational inequalities [J]. Optimization Methods and Software, 2007, 22: 329-338. He B S, Yuan X M. Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective [J]. SIAM Journal on Imaging Sciences, 2012, 5: 119-149. Cai X J, Gu G Y, He B S, et al. A relaxed customized proximal point algorithm for separable convex programming [EB/OL]. [2013-10-20]. http://www.optimization-online.org/DB HTML/2011/08/3141.html. He B S, Tao M, Yuan X M. Alternating direction method with Gaussian back substitution for separable convex programming [J]. SIAM Journal on Optimization, 2012, 22: 313-340. He B S, Yuan X M. On the O(1/t) convergence rate of the alternating direction method [J]. SIAM Journal on Numerical Analysis, 2012, 50: 700-709. Chen X, Fukushima M. Expected residual minimization method for stochastic linear complementarity problems [J]. Mathematics of Operations Research, 2005, 30: 1022-1038. He B S, Yuan X M. Linearized Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming [EB/OL]. [2013-10-23]. http://www.optimization-online.org/DB HTML/2011/10/3192.html. G\"urkan G, \"Ozge A Y, Robinson S M. Sample-path solution of stochastic variational inequalities [J]. Mathematical Programming, 1999, 84: 313-333. Chen X, Fukushima M. Expected residual minimization method for stochastic linear complementarity problems [J]. Mathematics of Operations Research, 2005, 30: 1022-1038. Luo M J, Lin G H. Expected residual minimization method for stochastic variational inequality problems [J]. Journal of Optimization Theory and Applications, 2009, 140: 103-116. Chen X, Lin G H. CVaR-based formulation and approximation method for stochastic variational inequalities [J]. Numerical Algebra, Control and Optimization, 2011, 1: 35-48. Lin G H, Fukushima M. New reformulations and smoothed penalty method for stochastic nonlinear complementarity problems [J]. Optimization Methods and Software, 2006, 21: 551-564. Lin G H, Fukushima M. Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: a survey [J]. Pacific Journal of Optimization, 2010, 6: 455-482. Ye J J, Zhu D L. New necessary optimality conditions for bilevel programs by combining MPEC and the value function approach [J]. SIAM Journal on Optimization, 2010, 20: 1885-1905. Lin G H, Xu M, Ye J J. On solving simple bilevel programs with a nonconvex lower level program [J]. Mathematical Programming, Doi: 10.1007/s10107-013-0633-4. Mersha A G, Dempe S. Direct search algorithm for bilievel programming problems [J]. Computational Optimization and Applications, 2011, 49: 1-15. Zhang D, Lin G H. Bilevel direct search method for leader-follower problems and application in health insurance [J]. Computers and Operations Research, 2014, 41: 359-373. Bard J F. Practical Bilevel Optimization, Nonconvex Optimization and its Applications [M]. Dordrecht: Kluwer Academic, 1998. Colson B, Marcotte P, Savard G. An overview of bilevel programming [J]. Annals of Operations Research, 2007, 153: 235-256. Dempe S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints [J]. Optimization, 2003, 52: 333-359. Dempe S. Foundations of Bilevel Programming, Nonconvex Optimization and its Applications [M]. Dordrecht: Kluwer Academic, 2002. Shimizu K, Ishizuka Y, Bard J F. Nondifferentiable and Two-level Mathematical Programming [M]. Dordrecht: Kluwer Academic, 1997. Scheel H S, Scholtes S. Mathematical programs with complementarity constraints: Stationarity, optimality and sensitivity [J]. Mathematics of Operations Research, 2000, 25: 1-22. Ye J J. Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints [J]. Journal of Mathematical Analysis and Applications, 2005, 307: 350-369. Guo L, Lin G H. Notes on some constraint qualifications for mathematical programs with equilibrium constraints [J]. Journal of Optimization Theory and Applications, 2013, 156: 600-616. Kanzow C, Schwartz A. Mathematical programs with equilibrium constraints: Enhanced Fritz John conditions, new constraint qualifications and improved exact penalty results [J]. SIAM Journal on Optimization, 2010, 20: 2730-2753. Ye J J, Ye X Y. Necessary optimality conditions for optimization problems with variational inequality constraints [J]. Mathematics of Operations Research, 1997, 22: 977-997. Guo L, Lin G H, Ye J J. Second order optimality conditions for mathematical programs with equilibrium constraints [J]. Journal of Optimization Theory and Applications, 2013, 158: 33-64. Izmailov A F. Mathematical programs with complementarity constraints: regularity, optimality conditions and sensitivity [J]. Computational Mathematics and Mathematical Physics, 2004, 44: 1145-1164. Guo L, Lin G H, Ye J J. Stability analysis for parametric mathematical programs with geometric constraints and its applications [J]. SIAM Journal on Optimization, 2012, 22: 1151-1176. Jongen H Th, Shikhman V, Steffensen S. Characterization of strong stability for C-stationary points in MPCC [J]. Mathematical Programming, 2012, 132: 295-308. Facchinei F, Jiang H, Qi L. A smoothing method for mathematical programs with equilibrium constraints [J]. Mathematical Programming, 1999, 85: 107-134. Fukushima M, Pang J S. Convergence of a smoothing continuation method for mathematical problems with complementarity constraints [M]//Théra M, Tichatschke R (eds.). Ill-posed Variational Problems and Regularization Techniques, Berlin: Springer-Verlag, 1999, 477: 99-110. Scholtes S. Convergence properties of a regularization scheme for mathematical programs with complementarity constraints [J]. SIAM Journal on Optimization, 2001, 11: 918-936. Izmailov A F, Solodov M V. An active-set Newton method for mathematical programs with complementarity constraints [J]. SIAM Journal on Optimization, 2008, 19: 1003-1027. Lin G H, Fukushima M. A modified relaxation scheme for mathematical programs with complementarity constraints [J]. Annals of Operations Research, 2005, 133: 63-84. Hu X, Ralph D. Convergence of a penalty method for mathematical programming with equilibrium constraints [J]. Journal of Optimization Theory and Applications, 2004, 123: 365-390. Huang X X, Yang X Q, Zhu D L. A sequential smooth penalization approach to mathematical programs with complementarity constraints [J]. Numerical Functional Analysis and Optimization, 2006, 27: 71-98. Chen X, Fukushima M. A smoothing method for a mathematical program with P-matrix linear complementarity constraints [J]. Computational Optimization and Applications, 2004, 27: 223-246. Fletcher R, Leyffer S, Ralph D, et al. Local convergence of SQP methods for mathematical programs with equilibrium constraints [J]. SIAM Journal on Optimization, 2006, 17: 259-286. Fukushima M, Luo Z Q, Pang J S. A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints [J]. Computational Optimization and Applications, 1998, 10: 5-34. Jiang H, Ralph D. Smooth methods for mathematical programs with nonlinear complementarity constraints [J]. SIAM Journal on Optimization, 2000, 10: 779-808. Liu X, Sun J. Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints [J]. Mathematical Programming, 2004, 101: 231-261. Lin G H, Fukushima M. Hybrid approach with active set identification for mathematical programs with complementarity constraints [J]. Journal of Optimization Theory and Applications, 2006, 128: 1-28. Guo L, Lin G H. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations [J]. Journal of Industrial and Management Optimization, 2013, 9: 305-322. Patriksson M, Wynter L. Stochastic mathematical programs with equilibrium constraints [J]. Operations Research Letters, 1999, 25: 159-167. Lin G H, Chen X, Fukushima M. Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization [J]. Mathematical Programming, 2009, 116: 343-368. Birbil S I, G\"urkan G, Listes O. Solving stochastic mathematical programs with complementarity constraints using simulation [J]. Mathematics of Operations Research, 2006, 31: 739-760. Liu Y, Zhang J, Lin G H. Stochastic mathematical programs with hybrid equilibrium constraints [J]. Journal of Computational and Applied Mathematics, 2011, 235: 3870-3882. |
| [1] | 黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114. |
| [2] | 侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108. |
| [3] | 高雷阜, 张亚红. 对称锥互补问题的一类惩罚FB函数[J]. 运筹学学报, 2018, 22(3): 125-131. |
| [4] | 冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30. |
| [5] | 何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31. |
| [6] | 郑跃, 庄道元, 万仲平. 求解弱线性双层规划问题的一种全局优化方法[J]. 运筹学学报, 2017, 21(3): 86-94. |
| [7] | 王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112. |
| [8] | 刘长河, 尚有林, 李锦睿. 基于一类新方向的宽邻域路径跟踪内点算法[J]. 运筹学学报, 2016, 20(1): 43-53. |
| [9] | 孟志青, 沈瑞, 徐新生, 蒋敏. 一种双层规划的光滑化目标罚函数算法[J]. 运筹学学报, 2015, 19(3): 26-33. |
| [10] | 何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70. |
| [11] | 杨赟, 彭拯. 可分离凸优化问题的非精确平行分裂算法[J]. 运筹学学报, 2014, 18(3): 33-46. |
| [12] | 高岩. 非光滑非线性互补问题的牛顿法[J]. 运筹学学报, 2011, 15(2): 53-58. |
| [13] | 张杰, 徐成贤, 芮绍平. 线性二阶锥互补问题的一种非精确光滑算法[J]. 运筹学学报, 2011, 15(2): 95-102. |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||
